CS262 Exam 1 Spring, 2006

Stretching section (5 pts. each)

Answer any 5 of 1-7

1. What is safety? Liveness? Which is easier to prove, and why?

2. Define synchronous and asynchronous systems. Why is most formal work done on asynchronous systems?

3. What is a stable predicate? What is the relationship between a possible state and a definite state?

4. List the six types of benign failure, starting with the weakest and ending with the strongest (where x is weaker than y if x is contained in y).

5. According to Waldo, et. al., what are the four characteristics of a distributed system that make it impossible to write distributed systems in the same way that local systems are written?

6. What three properties define reliable broadcast?

7. Why is atomic broadcast impossible in a deterministic asynchronous system?

Aerobics Section (25 points each)

Answer one of 8 or 9, and two of 10-12

8. Discuss the type truncation problem in RPC based systems. Describe how this problem is solved in CORBA, Modula-3 Network Objects, and Java RMI, and point out some of the consequences of these solutions.

9. Explain the Jini notion of a lease. How are leases used in the Jini system? How do leases interact with the transaction system in Jini?

10. Describe the relationship between a vector clock and a distributed system history. Explain how the requirements for consistency based on vector clocks can be re-stated in terms of a consistent cut on a history.

11. What is the gap detection problem in logical clocks? Explain why logical clocks have this problem, and then show that vector clocks do not in a particular special case. Why is this special case important?

12. Given a proof that the algorithm given in Fig. 5 of Hadzilacos and Toueg transforms a reliable broadcast algorithm into a FIFO reliable broadcast.