University of Freiburg | Faculty of Applied Sciences | Institute for Computer Science | Computer Networks and Telematics
The tele Research Group
Home         Teaching         Research        Tools         Openings        Publications





Distributed Systems - Assignment 6

Question 1

  • Two processes P and Q are connected in a ring using two channels, and they constantly rotate a message m. At one time, there is only one copy of m in the system. Each process's state consists of the number of times it has received m, and P sends m first. At a certain point, P has the message and its state is 101. Immediately after sending m, P initiates the snapshot algorithm.
  • Explain the operation of the algorithm in this case, giving the possible global state(s) reported by it.
Question 2
  • The following figure shows events occuring for each of two processes, p1 and p2. Arrows between processes denote message transmission.
  • Draw and label the lattice of consistent states (p1 state, p2 state), beginning with the initial state (0,0).
Question 3
  • Jones is running a collection of processes p1, p2, ...,pN. Each process pi contains variable vi. She wishes to determine whether all the variables v1, v2, ...,vN were ever equal in the course of the execution.



    (i) Jones' processes run in a synchronous system. She uses a monitor process to determine whether the variables were ever equal. When should the application processes communicate with the monitor process, and what should their messages contain?

    (ii) Explain the statement possibly(v1=v2=...=vN). How can Jones determine whether this statement is true of her execution?

Question 4
  • Is it possible to implement either a reliable or an unreliable (process) failure detector using an unreliable communication channel?
Question 5
  • In a certain system, each process typically uses a critical section many times before another process requires it. Explain why Ricart and Agrawala's multicast-based mutual exclusion algorithm is inefficient for this case, and describe how to improve its performance.
  • Does your adaptation satisfy liveness condition ME2?
Question 6
  • In the Bully algorithm, a recovering process starts an election and will become the new coordinator if it has a higher identifier than the current incumbent. Is this a necessary feature of the algorithm?
Question 7
  • Suggest how to adapt the Bully algorithm to deal with temporary network partition (slow communication) and slow processes.