Tutorial 4: COORDINATION & AGREEMENT

Question 1

Does the following algorithm solve the mutual exclusion problem? Discuss your answer based on the requirements for

the solutions of the mutual exclusion problem, as discussed in the lecture.

Answer 1

Requirements for Mutual Exclusion:

• Safety
  
  • At most one process accesses the CS at a time
• Liveness
  
  • Requests to enter & exit the CS eventually succeed (no deadlocks)
• Fairness
  
  • If one request to enter the CS happened-before another one, then access is granted in that order
  • Requests are ordered such that no process enters the CS twice while another process waits to enter (no star- vation)
• This algorithm satisfies none of the requirements of the mutual exclusion problem.
  Safety is not guaranteed. For instance, suppose there are only two processes P1 and P2 in the system:
  1. P1 is in the CS and P2 is waiting for receiving a reply message from P1 to access the CS
  2. P1 leaves the CS and sends a reply message to P2
  3. Directly after sending the reply message, P1 again sends a new request message
  4. P1 gets the reply from P2 (because P1’s new request has overtaken P1’s reply. This was not detected by P2 due to the lack of a notion of time)
  5. Now P2 receives the reply message from P1
  6. P1 changes its state to HELD and goes into the CS
  7. P2 changes its state to HELD and goes into the CS
• → There are now two processes in the CS; therefore, safety is violated.
• Liveness is violated because for every two processes Pj and Pi with j < i, if process Pj is in state WANTED or HELD, it will never allow process Pi to get in the CS. This is the case when Pj continuously requests access.
• Fairness fails because if Pi requests to enter the CS before Pj but j < i, then Pj will enter the CS first.
• Finally, the Ordering property is not guaranteed, since the algorithm is based only on process ids, and a notion of time is ignored. Consequently, the happened-before relation cannot be obtained.

Question 2

Give an example execution for the ring-based algorithm to the mutual exclusion problem showing that processes are not necessarily granted entry to the critical section in the happened-before order.

Answer 2

The processes in the ring-based algorithm are granted entry to the critical section in the order they are arranged on the ring. For example if the process situated counter-clockwise right next to the process holding the token is requesting access to the critical section and while the token is being passed, another process is also requesting access, by the time the token gets to the second requesting process, this one will get access although it requested it later (cf. Figure 2.1).

Question 3

A distributed system may have multiple, independent critical sections. Suppose that Process Pi wants to enter critical section A and Process Pj wants to enter critical section B. Can Ricart and Agrawala’s algorithm lead to deadlock? Explain your answer.

Answer 3

It depends on the ground rules. If processes access resources strictly sequentially, that is, a process holding a resource may not attempt to access another one, then there is no way that it can block while holding a resource that some other process wants. The system is then deadlock free. On the other hand, if process Pi is allowed to access resource A and then try to access resource B, a deadlock can occur if some other process tries to acquire them in the reverse order. The Ricart and Agrawala algorithm is only designed for accessing a single resource.

Question 4

(a) For leader election, assume that two processes detect the demise of the coordinator simultaneously and both decide to hold an election using the Bully algorithm. What happens?

Answer 4

Solution: Bully algorithm at a glance:

• Assumption: Synchronous system with timeouts.
• Processes know each other and have ids (higher ids are prioritized).
• Algorithm is initiated once a process suspects a failure.
• There are three types of messages: Elect, Answer, and Victory (or Coordinator in the lecture slides).
• Example: j < i < k (cf. above)
• @Pi : Broadcast election
• Pk sends answer (higher id) and broadcasts new election, Pj doesn’t answer (lower id)
• if Pi receives no answer it broadcasts victory else Pi waits for victory.
• → Each of the higher-numbered processes will get two election messages, but will ignore the second one. The election will proceed as usual.

Question 5

(b) Adapt the Bully algorithm to deal with temporary network partitions and slow processes.

Answer 5

• (i) In order to deal with temporary network partitions, in each partition, bully algorithm is run locally and each partition chooses its own leader. However, each process keeps running the bully algorithm (continuous heart- beating) and as soon as two partitions merge, the stronger leader (higher process id) bullies the leader of the other partition. This continues until we have only one partition. So, nothing bad happens.
• (ii) In order to deal with slow processes, the participants run the bully algorithm, and lower-id-holder processes might, for a while, think that there are no higher-id-holder processes than themselves and declare themselves leaders. However, sooner or later the stronger process’s messages will arrive and it will bully the temporary weaker leaders.