CSE533: Network Programming
Fall 2001
Scott Stoller

Project Description

[CMR01] G. Chokler, D. Malkhi, and M. Reiter. Backoff Protocols for Distributed Mutual Exclusion and Ordering. In Proceedings of the 21st IEEE International Conference on Distributed Computing Systems (ICDCS 2001).

Sample Code for interface between replication protocol and service


Additional Comments

28 Nov

Demo: We plan to increase the demo timeslots to 40 min. We are considering scheduling two demos concurrently, so that, while one team's testcase is executing, Fanglu can talk to the other team. If you have comments on whether this is a good or bad idea, please send them to me in the next few days.

Testcases: The earlier comments about testcases apply to proj2 as well, namely: "Your test.txt should describe testcases with zero, one, and two faulty servers. You should use a quorum system with b=2 for the testcase with 2 faulty servers. You are expected to demonstrate these testcases during the demo." With 0 faulty servers, it suffices to have 1 or 2 testcases showing that each of the operations (create, read, etc.) works correctly in the absence of failures. With 1 or 2 faulty servers, there are so many possible testcases that comprehensive testing is infeasible. You need to choose (say) 3 to 6 representative testcases for each value of b and include them in your test.txt. For example, a set of representative testcases should contain all of the following situations: a client receives b RankException's, a client receives b+1 RankException's and re-tries with higher rank, each of the three branches in lines 2.18-24 is executed, if possible (it's not clear to me whether line 2.21 is reachable). During the demo, there probably won't be time to show all of these testcases; the T.A. will select a few for you to demo.

25 Oct

Demo Location: You should look for the T.A. in the standard T.A. location (Room 2110). Then you can go to a lab of your choice for the demo. (It's best if some team member is already logged in and ready to start the demo when you get the T.A..)

22 Oct

Demo Length: With sufficient advance preparation, you should be able to finish your demo in half an hour. After rehearsing your demo, if you find that you can't finish in half an hour, send a message to Fanglu requesting a longer (40 min) timeslot. Please try to avoid this: it complicates scheduling.

21 Oct

Demo: Please rehearse your demo once before your appointment with the T.A. Otherwise, it will be difficult to finish the demo in half an hour.

Testcases/Demo: Recall from the announcement below (20 Sep and earlier): Your test.txt should describe testcases with zero, one, and two faulty servers. You should use a quorum system with b=2 for the testcase with 2 faulty servers. You are expected to demonstrate these testcases during the demo.

Demo: An essential aspect of testing a mutual exclusion algorithm is to show that it ensures mutual exclusion. Therefore, during the demo, you should be prepared to show, based on the output of your program (on the screen or in log files), that mutual exclusion held in each testcase---or, at least in testcases in which all processes run on the same host, since the easiest approach is to output a real-time timestamp for each relevant event. If your code does not currently do this, you may (if you want) add code to produce such timestamps and submit a new .zip file. (Don't make other changes to the code; we will keep your original submission for comparison.)

19 Oct

Demo: It is not required that all team members be present during the demo. On the other hand, the people at the demo should be able to answer all of the T.A.'s questions about the project; "Sorry, we have no clue; Bob implemented that method, and he's not here." is not a good answer.

Demo Deadline: Proj1 demos must be done on or before Thursday, Oct 25.

18 Oct

Demo: Here is a more detailed procedure for demos.
  1. Copy your submission (.zip file) from the cse533 account to your account. (Or, if you kept a copy of the zip file, we'll use md5 to compare your copy to the file you submitted.)
  2. unzip, remove *.class, and compile.
  3. run testcases

Demo Sign-up: I will bring a sign-up sheet for demos to class tomorrow.

Testcases: As stated in class, your system must allow different processes to run on different hosts. During the demo, you will be expected to run at least one testcase in which clients run on one host, some servers run on another host, and the remaining servers run on a third host. Remember that it is your responsibility to thoroughly test your system and thereby demonstrate to the grader through your testcases that your system works correctly. Ideally, all of the important testcases should already be documented in your test.txt, but you may also show other testcases during the demo.

16 Oct

Quorums: The grid quorums described in Example 4.7 on page 8 of Dahlia Malkhi and Michael Reiter. Byzantine Quorum Systems. Distributed Computing, 11(4):203--213, 1998. can easily be adapted to the kind of quorums needed in the Backoff paper. However, for a given value of b, if we take the minimal allowed value of n, grid-based quorums are larger than threshold-size quorums (as described in the announcement of 15 Oct). Grid-based quorums are smaller than threshold-size quorums when n is larger (and b is unchanged).

15 Oct

Quorums: Quorum systems for proj1 can be constructed as follows. Given n and b with n>5b, the set of all subsets of U of size n-b is a quorum system. You should be able to verify this by a proof similar to the one we discussed in class on 2 Oct for n=6 and b=1. If generating these quorum systems by hand is tedious, you can write a program to do it. These symmetric quorums are acceptable for this project but might not always be optimal. As mentioned below (on 1 Oct), extra credit will be given for more interesting quorum constructions. Quorum systems for proj2 are different: they must satisfy the additional condition in section 6.2.

6 Oct

JSSE: Another useful link is the JSSE API Documentation

5 Oct

JSSE: To use the certificates I provided, you might need to specify a trust store. See the documentation on TrustManagerFactory (you can set the property javax.net.ssl.trustStore) and KeyManager Factory in the JSSE API user's guide.

Authentication: It's clear that the client needs to authenticate the server, because a server may be Byzantine faulty and try to impersonate another server. Do servers need to authenticate clients? The answer depends on whether you assume the network is secure. With JSSE, authentication on both sides requires little extra work (compared to authentication on one side), so you should do authentication on both sides.

2 Oct

Quorum File Format: To facilitate grading, everyone should use the same file format for quorum systems. Here is the proposed format; if you think another format would be better, let me know. The first line contains n, b, and the number of quorums in the file; the numbers are separated by whitespace. The remaining lines each contain one quorum. A quorum is described by a sequence of numbers in the range 0 to n-1, separated by whitespace. Here is a sample quorum file.

1 Oct

Quorum Generation: It's your choice whether to write a separate little program to automatically generate files containing quorum systems, or to generate those files manually. No extra credit will be given for implementing simple quorum system constructions (e.g., all sets of a certain size); extra credit may be given for programs that construct more interesting quorum systems (e.g., based on grids) for arbitrary b and sufficiently large n.

Advice: To help separate concerns, I suggest that you get the mutex protocol working using ordinary sockets and then introduce JSSE for security. Some team members might want to experiment with JSSE and certificates in some simple programs while the mutex protocol is being implemented and tested.

21 Sep

Project1: For the first part of the project, you should use SSL for secure communication in your implementation of the mutex protocol.

Certificates: I added a zip file above containing keystores with certificates that you can use with SSL. "533ca" is the certification authority for all of these certificates. 533ca's public key is in keystore "cacerts". 533ca issued certificates for all of the clients and servers. Each client and server has its certificate in a separate keystore. Use keytool to view the contents of the keystores. For example (note the keystore passwords):

The other client and server stores have analogous keystore passwords. The passwords associated with individual aliases (clients or servers) are as follows; you need these passwords to access the private keys to generate signatures. The password associated with alias client0 is client0pwd; for server0, it's server0pwd; and so on. (You don't need the password for 533ca.) I am providing the certificates, because keytool can only generate self-signed certificates. To manipulate keystores and keys in your program, see the documentation for java.security, especially java.security.KeyStore.

20 Sep and Earlier

Testcases: Your test.txt should describe testcases with zero, one, and two faulty servers.

Quorums: For flexibility, your program should read the quorum system from a file with a human-editable format. Your instructions.txt should describe the file format, so a user can easily change the quorum system.

Quorums: [CMR01] claims that quorum systems with the required properties exist for n > 6b. This is incorrect. It is not difficult to show that no such quorum system exists for b=1 and n=7. For b=1 and n=8, the set of all subsets of U of size 6 is a quorum system. One might conjecture that the condition should be n > 7b. I have not attempted to prove this. A proof of this would earn extra credit! (Submit the proof whenever it is ready; don't wait for the project submission.)