CSE 486/586 Distributed Systems

Programming Assignment 2

Totally and Causally Ordered Group Messenger with a Local Persistent Key-Value Table

Update 2

1. One of the requirements for your content provider is that other apps (not just your app) should be able to access your content provider. In order to you test this, please do the following:

1. Download ContentProviderTester.apk
2. Install it on one of your AVDs where you want to test your content provider. If you’re installing on the first emulator instance (emulator-5554), then the command is: “adb -s emulator-5554 install ContentProviderTester.apk”
3. If you start it, it’ll have “PTest” button, which implements the exact same logic as in the GroupMessenger template.
4. If it doesn’t work, then you must fix it because it is a requirement for your content provider ;-)

2. This is just a clarification, but your app should total-causal multicast all messages entered in the EditText as well.
3. Another clarification is that your total-causal multicast mechanism should be an underlying component used by your test cases. This means that all your total-causal multicast logic should be implemented as a separate component, not as part of your test cases.

Update 1

If you want to use Amazon EC2 for this assignment, here’s the instructions on how to set it up: http://goo.gl/lfhCz

Introduction

The teaching staff hopes you had fun working on PA1! If you got frustrated, we feel for you and believe us, we were there too. While it is expected to be frustrated in the beginning, we promise you, it will get better and you will enjoy more and more as you do it. You might even start enjoying reading the Android documentation because it *is* actually the single best place to get great information about Android. We do hope, though, that you now understand a bit more about what it means to write networked applications on Android.

Now back to the assignment: this assignment builds on the previous simple messenger and points to the next assignment. You will design a group messenger that preserves total ordering as well as causal ordering of all messages. In addition, you will implement a key-value table that each device uses to individually store all messages on its local storage, which should prep you for the next assignment. Once again, please follow everything exactly. Otherwise, it might result in getting no point for this assignment.

The rest of the description can be long. Please don’t “tl;dr”! Please read to the end first and get the overall picture. Then please revisit as you go!

Step 0: Importing the project template

Unlike the previous assignment, we will have strict requirements for the UI as well as a few other components. In order to provide you more help in meeting these requirements, we have a project template you can import to Eclipse.

1. Download the project template zip file to a directory.
2. Import it to your Eclipse workspace.

1. Open Eclipse.
2. Go to “File” -> “Import”
3. Select “General/Existing Projects into Workspace” (Caution: this is not “Android/Existing Android Code into Workspace”).
4. In the next screen (which should be “Import Projects”), do the following:

1. Choose “Select archive file:” and select the project template zip file that you downloaded.
2. Click “Finish.”

5. At this point, the project template should have been imported to your workspace.

1. You might get an error saying “Android requires compiler compliance level...” If so, right click on “GroupMessenger” from the Package Explorer, choose “Android Tools” -> “Fix Project Properties” which will fix the error.

6. Try running it on an AVD and verify that it’s working.

3. Use the project template for implementing all the components for this assignment.

Step 1: Implementing the main Activity

Just like group chatting, your main Activity should display all messages regardless of which AVD the messages come from. For example, if there are three AVDs running your app, all messages from all three app instances should be displayed in each and every app instance’s TextView. Unlike PA1, we have strict UI requirements to simplify this assignment:

1. There has to be one (and only one) EditText where a user can enter messages.
2. There has to be one (and only one) “Send” button that a user can click to send a message. This should be the only way to send a message. For example, pressing enter is not a signal to send a message anymore.
3. There has to be one (and only one) TextView that displays all the message in the total-causal order.
4. There has to be three buttons, one for testing your content provider, one for the first test case, and one for the second test case. The details on the test cases are in the final step “Step 3: Implementing Total-Causal Ordering”.
5. At least for the layout, the template gives you a starting point to meet the above requirements. Please do not change the layout, but implement the necessary components starting from the layout.
6. Your app should display all the messages exchanged while a user is using the app. However, if the user closes the app and restarts it, it is not required to display the message exchanges in the previous run.

Step 2: Writing a Content Provider

Along with the main Activity, your app should have a content provider. This provider should be used to store all messages, but the abstraction it provides should be a general key-value table. The following are the requirements for your provider:

1. Any app (not just your app) should be able to access (read and write) your provider. This means that you should not set any permission to access your provider.
2. Your provider’s URI should be “content://edu.buffalo.cse.cse486586.groupmessenger.provider”, which means that any app should be able to access your provider using that URI. To simplify your implementation, your provider does not need to match/support any other URI pattern.
3. Your provider should have two columns.

1. The first column should be named as “key” (an all lowercase string without the quotation marks). This column is used to store all keys.
2. The second column should be named as “value” (an all lowercase string without the quotation marks). This column is used to store all values.
3. All keys and values that your provider stores should use the string data type.

4. Your provider should only implement insert() and query(). All other operations are not necessary.
5. Since the column names are “key” and “value”, any app should be able to insert a <key, value> pair as in the following example:

6. Similarly, any app should be able to read a <key, value> pair from your provider with query(). Since your provider is a simple <key, value> table, we are not going to follow the Android convention; your provider should be able to answer queries as in the following example:

Thus, your query() implementation should read the selection parameter and use it as the key to retrieve from your table. In turn, the Cursor returned by your query() implementation should include only one row with two columns using your provider’s column names, i.e., “key” and “value”. You probably want to use android.database.MatrixCursor instead of implementing your own Cursor.

7. Your provider should store the <key, value> pairs using one of the data storage options. The details of possible data storage options are in http://developer.android.com/guide/topics/data/data-storage.html. You can choose any option; however, the easiest way to do this is probably use the internal storage with the key as the file name and the value stored in the file.
8. After implementing your provider, you can verify whether or not you are meeting the requirements by clicking “PTest” provided in the template. You can take a look at OnPTestClickListener.java to see what tests it does.
9. If your provider does not pass PTest, there will be no point for this portion of the assignment.

Step 3: Implementing Total-Causal Ordering

The final step is supporting both total and causal ordering. You will need to design an algorithm that does this and implement it. You will probably need to spend most of your time on this part. The requirements are:

1. Your app should multicast every user-entered message to all app instances (including the one that is sending the message). In the rest of the description, “multicast” always means sending a message to all app instances.
2. Your app should use B-multicast. It should not implement R-multicast.
3. You need to come up with an algorithm that provides total-causal ordering. After all, this is the main point of this assignment!
4. As with PA1, we have fixed the ports & sockets.

1. Your app should open one server socket that listens on 10000.
2. You need to use run_avd.py and set_redir.py to set up the testing environment.
3. The grading will use up to 3 AVDs. The redirection ports are 11108, 11112, and 11116.
4. You should just hard-code the above 3 ports and use them to set up connections.
5. Please use the code snippet provided in the PA1 description on how to determine your local AVD.

1. avd0: “5554”
2. avd1: “5556”
3. avd2: “5558”

5. Every message should be stored in your provider individually by all app instances. Each message should be stored as a <key, value> pair. The key should be the final delivery sequence number for the message (as a string); the value should be the actual message (again, as a string). The delivery sequence number should start from 0 and increase by 1 for each message.
6. You need to write two test cases. Manually testing the correctness of your app is going to be difficult since you need to verify the ordering with concurrent events. A better way is to write test cases that can automatically generate messages. This is still not perfect, but it can assist you when you debug your app. The next two points detail the test cases.
7. Test case 1

1. Your main Activity should have “Test1” button that triggers the test case. (This is already provided by the template.)
2. When the button is clicked, it should create a thread that multicasts 5 messages in sequence. Multicasting of one message should be followed by 3 seconds sleep of the thread. This is just to make sure that we can spread messages from different emulator instances.
3. The message format should be “<AVD name>:<sequence number>”. <AVD name> is the emulator instance’s name, e.g., avd0, avd1, and avd2. <sequence number> is a number starting from 0 and increasing by 1 for each message. For example, if your first emulator instance multicasts 5 messages, then the messages should be “avd0:0”, “avd0:1”, “avd0:2”, “avd0:3”, and “avd0:4”.
4. With this test case, at least the following two ordering guarantees can be verified by just looking at the sequence of messages on each instance.

1. Total ordering: every emulator instance should display the same order of message
2. FIFO ordering: all messages from the same instance should preserve the local order. This should be preserved because causal ordering implies FIFO ordering.

8. Test case 2

1. Your main Activity should have “Test2” button that triggers the test case. (This is already provided by the template.)
2. When the button is clicked, your app should multicast one message. The message format should be the same as the above test case.
3. Receiving of this first message should trigger all app instances to multicast exactly two more messages. Unlike the test case 1, you should not introduce any extra delay between the messages.
4. Thus, in total with 3 AVDs, there should be 1 + 3 + 3 = 7 multicast messages.
5. What this means is that your code should recognize the first message of this test case and react accordingly when it receives the message.

Design Document

You need to write a design document of up to 2 pages (12 pt font in .pdf). Please discuss the following questions:

• What components have you written?
• What does each component do? Please include figures if necessary when describing each component.
• What is your total-causal ordering algorithm? Why does it provide both ordering guarantees at the same time?
• How do you handle the first message in your test case 2? Why did you choose that way?
• What have you learned in this assignment?

Submission

We use the CSE submit script. You need to use either “submit_cse486” or “submit_cse586”, depending on your registration status. If you haven’t used it, the instructions on how to use it is here: https://wiki.cse.buffalo.edu/services/content/submit-script

One again, you need to submit three separate files described below. You must follow everything below exactly. Otherwise, you will get no point on this assignment.

• Your app’s .apk: The name should be GroupMessenger.apk.
• Your design document in .pdf: The name should be GroupMessenger.pdf. Please do not submit a .docx or .txt file.
• Your entire Eclipse project source code tree zipped up in .zip: The name should be GroupMessenger.zip. To do this, please go to your Eclipse workspace directory, find your app, and zip it. Please do not use any other compression tool other than zip, i.e., no 7-Zip, no RAR, etc. Please make sure to zip the top-level directory that contains all the source, i.e., unzipping should create one “GroupMessenger” directory that contains all the source files.

Deadline: 3/1/12 (Friday) 2:59pm

This is right before class @ 3pm. The deadline is firm; if your timestamp is 3pm, it is a late submission.

Grading

This assignment is 15% of your final grade. The breakdown for this assignment is:

• 10%: your app

• 2% if the content provider behaves correctly
• 3% if total ordering is preserved
• 3% if causal ordering is preserved
• 2% if you write test cases correctly

• 5%: your design document

• 2% for the overall clarity of the description
• 3% for the correct total-causal ordering algorithm description