Class meets in University Center 413-2 on Tuesday and Thursday 2:20 - 3:40.

Your grades will be based on three homework assignments and a class project.

Assignment 1, due 30 January 2001.

Assignment 2, due 26 February 2001.

Assignment 3, due 16 March 2001.

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. Over twelve years ago Robert Morris Jr. unleased the "Internet Worm". It was brought under control by the coordinated effort of many system administrator (some of this coordiantion was provided by Morris). Such a coordinated effort would most likely be impossible today. The internet has grown massively in the last 12 years, and the average experience of the (vastly more) systems administrators has dropped significantly. What can be practically done to contain or to destroy a newly unleased internet worm?
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. 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 of them, informally define it, give a careful specification, and find its complexity (using an appropriate metric of your choosing).
4. Research and developent of the computational grid has led to a resurgence in interest in large distributed applications.Indeed, some systems are being designed to scale to millions of distributed objects and tens of thousands or more of processors. So far, though, the computational grid community have not yet built large enough appliations to make fault-tolerance a concern. Will it ever become a concern? How large does a scientific application need to get for fault-tolerance to become a concern?
5. Suppose one wanted to checkpoint the state of a huge multiprocessor such as the SDSC Blue Horizon (which has thousands 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 because time is ignored. 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, DCOM and 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. We'll cover several protocols in class. For each protocol that I cover there are dozens of related protocols. Some try to minimize metrics, others try to give good average performance, still others examine the problem in a different way. Choose one of the protocols that we cover and do an in-depth study of the problem it addresses and the solutions that have been developed. You might also develop a new solution (or form of the problem) in doing so.
10. 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?
11. There are several reliable broadcast protocols, including those based on agreement, SRM, and epidemiological-based protocols. Consider the UCSD stub doman: that is, the internet of all of the computers that have names that end in ucsd.edu. Suppose you wished to deliver a message stream to all of the computers in this stub domain, with an average intermessage arrival time of T. For a given value of T and given the performance and failure properties of the stub domain, which approach works best, for some suitable definition of "works"?
12. 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.