Instructors : Dr. Tong Lai Yu

Homework 3
Due June 3, 2008 ( Tue )

1. What effect does a communication failure have on a system using the algorithm for the causual ordering of messages that we discussed in class?

2. In Lamport's algorithm for mutual exclusion, Process P_i enters CS when the following 2 conditions are satisfied:
   • P_i's request is at the head of request-queue_i
   • P_i has received a ( REPLY ) message from every other process time-stamped later than t_si
   Condition 1) can hold concurrently at several sites. Why then is 1) needed to guarantee mutual exclusion?

   Does the algorithm work if condition 2) is removed? Why? Give an example with illustrations ( drawings ) to support your argument.

3. In Lamport's algorithm of mutual exclusion, if a site S_i is executing the critical section, is it necessary that S_i's request need to be always at the top of the request-queue at another site S_j? Explain and give an example ( with diagrams ) to support your argument.

4. With the help of diagrams, show that Byzantine agreement cannot always be reached among four processors if two processors are faulty.

5. Are the servers of the following file systems stateless? a) NFS
   b)SFS
   c) Lustre What is special about the file system Lustre? How is it different from NFS and SFS?

6. Maekawa's Algorithm is used to achieve mutual exclusion for 13 sites. Suppose the sites are labeled 1, 2, ..., 13. Find the request sets R₁, R₂, ... , R₁₃.

   Suppose sites 1, 6, 12 want to enter a critical section ( CS ) and they have sent requests in the order 1, 6, 12. The following sequence of events have occurred in the order listed:

   1. The requests of site 1 have arrived at site 2, and site 3. Its request to site 4 is on the way.
   2. The requests of site 6 have arrived at site 9, and site 12. Its request to site 2 is on the way.
   3. The requests of site 12 have arrived at site 4, and site 7 and 8.
   Draw a diagram to show which sites have been locked and locked by whom.

   Suppose the transit requests have arrived at their destinations. At this point can any site enter the CS? Why? If not, how do the sites resolve the problem?