1. Ricart-Agrawala mutual exclusion

Background reading

• Section 5.5 Mutual Exclusion T&vS 1st Ed.
• Section 6.3.4 A Distributed Algorithm T&vS 2nd Ed.

Look at the slide 58 of Chapter 3. Assume that while P2 is using the resource the process P3 (with the timestamp 35) makes a request for the resource. Does the algorithm really work correctly? In all cases?

2. Bully algorithm

Reading material

• Section 5.5 ''Mutual Exclusion'', T&vS 1st Ed.
• Section 6.3.5 ''A Token Ring Algorithm'', T&vS 2nd Ed.
• Section 6.5.1 ''The Bully Algorithm'', T&vS 2nd Ed.

a) Suppose that two members of a group detect the demise of the coordinator simultaneuously and both decide to hold an election using the bully algorithm. What happens?

b) Does the bully algorithm work properly even if during the election the state of some member changes (present => absent) ?

c) If the ring algorithm would be used in a) then we would have two ELECTION messages circulating simultaneously. Devise an improved algorithm which kills off superfluous messages.

3. Consistency models in the field

Reading material

• Ch. 6 Consistency and Replication, T&vS 1st Ed.
• Ch. 7 Consistency and Replication, T&vS 2nd Ed.

a) Which consistency models have been used (or could be used) in the following cases:

1. DNS
2. Web cache
3. Facebook user's Wall
4. Collaborative writing (e.g., Wikipedia)
5. Store inventory system

Justify your answers.