Sample Code for interface between replication protocol and service
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.
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.)
Demo Deadline: Proj1 demos must be done on or before Thursday, Oct 25.
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.
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).
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.
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.
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):
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.)