Assignment 1, due 27 April 2000.

Assignment 2, due 18 May 2000.

Fault-Tolerant Broadcasts by Fred B. Schneider, David Gries and Rick Schlichting. postscript

Impossibility of Distributed Consensus with One Faulty Process by M. Fischer, N. Lynch and M. Paterson. pdf

Unreliable Failure Detectors for Reliable Distributed Systems by T. Chandra and S. Toueg. postscript

Report projects can be studies, survey papers, or research papers. Below is a short list of some possible topics. You’re free (indeed, encouraged) to modify, restrict, or expand on one of these topics or to choose a completely different topic, but please clear with me before proceeding with your work.

1. The precision to which we can synchronize clocks in distributed systems has improved by a factor of 10⁶ over the last ten years or so. Why is this so? How much of this is attributable to software improvements and how much of it is attributable to hardware improvements?
2. Epidemic protocols are protocols that multicast data similar to the way a disease spreads. Epidemic protocols are very robust; it’s hard to stop an epidemic. But, they are very message intensive. Can one design epidemic protocols that maintain their robustness without sending as many messages?
3. Ten years ago, the research field was filled with different projects producing distributed operating systems: V, Locus, Eden, Amoeba, Sprite, Andrew, Camelot, RIG, and so on. What happened? Did these systems have an impact on the products being sold today, or were they largely irrelevant? Is there any research going on today in distributed operating systems (or topics that cover some of the issues, at least)?
4. One issue in fault-tolerant distributed systems is the ability to record the state of a process (commonly called a checkpoint) and transferring it to another process (commonly called state transfer). What is the state-of-the-art in protocols that solve these two problems? Have these problems been specified? Is there anything known about the complexity of these problems? If not, can you say anything about their complexity?
5. Suppose one wanted to checkpoint the state of a huge multiprocessor such as a Los Alamos Blue Mountain (which has several thousand processors). How would it be done? What kind of performance penalty would be imposed? What would the performance bottleneck be?
6. There has been a considerable amount of research done in detecting properties that are not stable. We will briefly touch on this topic in class. The work that has been done so far, however, has been confined to the asynchronous system model, which can lead to silly notifications. Can the current state-of-the-art detection protocols be improved by introducing some weak notion of synchronous execution?
7. A different approach to fault-tolerance than the one that will be covered in class is self-stabilization. In self-stabilizing systems, a safe state will always lead to another safe state, but an error may force the system to enter an unsafe state. Yet, all executions starting in unsafe states will eventually lead to a safe state. For example, in a self-stabilizing token passing protocol, the token is safely passed from processor to processor. A failure may cause the token to be lost (or several tokens to be spontaneously generated), but if this occurs the system will eventually return to a state in which there is a single token. What is the state-of-the-art in self-stabilization? Are the protocols practical? Can one design a self-stabilizing system that has a hierarchy of safety; for example, a token-passing system that ensures that, while proceeding from a state in which there are k tokens to a safe state in which there is only one token, the system will never enter a state that has more than k tokens?
8. Distributed object oriented systems (such as CORBA or Legion) support object location transparency, and, by doing so, should provide some measure of fault-tolerance. What are researchers doing to address fault-tolerance in such systems? What should they be doing? Are the protocols that are used for process oriented systems (such as primary-backup, state machines, message logging) applicable to object oriented systems? What is a reasonable failure model for such systems? Is independence of failure a good assumption? If not, then how can dependent failures be accommodated? Can information obtained at compile-time or link-time be used to aid in providing fault-tolerance?
9. The timed asynchronous model is a set of system assumptions that, like the asynchronous system model, constrain what one can and can’t do in a distributed system. The timed asynchronous model is more practical than the standard asynchronous system, in that one assumes that there are clocks that run at standard rates and that the system’s performance is reasonable frequently enough for one to make progress. What does this last phrase really mean? Are there minimal conditions required for various problems to be solvable? Are there conditions that are mathematically reasonable to establish, in that one could actually prove in some manner that they hold with a given probability?
10. Agent-based computing is yet another form of distributed computing that some are advocating as being useful for internet-based applications. Hence, the basic building blocks of distributed computing used in process oriented systems (such as atomic broadcast, agreement, group membership) may not be appropriate for agent-based systems. What are some appropriate building blocks? Choose one or two of them, informally define them, give a careful specification, and find their complexity (using an appropriate metric).
11. Agent-based computing has a very different model of communication than process oriented systems. Much of the work in process oriented systems assume a piecewise deterministic model in which the only class of nondeterministic actions that a process can execute is  selecting of which of a set of ready-to-deliver messages should be delivered. How does this change with agent-based computing? With your observations, modify an existing fault-tolerance protocol (such as message logging or primary-backup) to be useful in an agent-based system.