I would like you to do a class project. I expect them to be done individually, but if you would like to do a larger project that requires more than one person, I'm happy to discuss the idea with you.

• One thing you could do is write a survey paper on a topic that is related to this class, but that we have not covered. Some possible topics are:

  • Self-stabilization.
    
    
  • Probabilistic quorum systems.
    
    
  • Dependent failure models.
    
    
  • Game theory application to distributed algorithms.
    
    
  • Gossip protocols.

  If you intend to do a survey, then please collect a set of papers and come see me. We will work out an appropriate depth for your survey.

• You can instead try to answer some question. Here are some big fuzzy questions that might suggest to you a more narrow and doable question. Again, once you have some ideas, let's talk.

  • Asynchronous protocols were developed as a response to the prevailing network behaviors. But, one could argue that, now, synchronous protocols may be feasible. For example, SOC are timely, and at the level of routers, the Internet behaves synchronously. Identify such a domain (it need not be either of these) and determine whether the benefits of a synchronous system - eg, reliable failure detection, skew-sensitive protocols, etc, are truly feasible and useful.
    
    
  • Consider some distributed coordination problem - for example, distributed hash tables, or distributed sensor networks. Such protocols coordinate by exchanging messages using a well-known protocol. Can the fact that the protocol is well-known be used to build a detector that determines whether a participant is behaving in a malicious manner? A survey of protocols that use this approach applied to routers is here.
    
    
  • Byzantine tolerant consensus protocols typically have a "view change" problem embedded with them. Extract this as a separable problem and give a precise specification for it.
    
    
  • Group based programming is built around an abstraction of group membership. This was it's great strength (a powerful abstraction) and weakness (hard to pin down exactly, great complexity, some specifications were nonsense, many intelligent researchers claiming abstraction was at the wrong level).

    Paxos has steered clear of group membership as an abstraction. Is there some kind of small step one can take to bring some of the power of the group membership abstraction without reinventing group based programming?
    
    

  • Some researchers have argued that we can implement distributed systems that provide the abstraction of asynchronous communication and perfect failure detectors. What do you think? What kind of failure detector would you provide?
    
    
• Finally, you could do an implementation project. Here's some possibilities, but you can easily generate more like this: both explore some part of the course through implementation and execution in a realistic environment. Again, please talk with me once you have some ideas of what you might like to do:
  
  
  • Implement a quorum update protocol for a large number of nodes on PlanetLab. Choose some coterie constructions that you think is reasonable (B-Grid? Junqueira's model? Majority?) and measure the performance differences.
    
    
  • Compare the the Gray-Lamport nonblocking atomic commit protocol with classic three-phase commit. (Note that we won't cover G-L until near the end of the quarter; this would be of interest if you already have some knowledge of Paxos).