Description
1. Mutual Exclusion – Ricart Agrawala Algorithm
Figure 1 shows three process P1, P2, and P3 (with ids 1, 2, and 3 respectively) implementing the RicartAgrawala (RA) algorithm for mutual exclusion. The lines indicate requests for accessing the critical
section (CS) made by each process – blue, green, and red requests are from P1, P2, and P3 respectively.
Other than the replies to CS requests (not shown in the figure), no other messages are exchanged between
the processes. The timeline indicates real time. Assume that any reply sent for a CS request reaches the
requesting process after exactly one (real) time unit. Further assume that any process that enters the
CS, spends 3 (real) time units in it.
(a) (2 points) What is P1’s state as per the RA algorithm when it receives CS request from P2 – Held,
Wanted, or neither (Free)? How will P1 handle P2’s request upon receiving it – will it immediately
send back a reply or will it queue the request? Why?
(b) (2 points) What is P3’s state as per the RA algorithm when it receives CS request from P2 – Held,
Wanted, or neither (Free)? How will P3 handle P2’s request upon receiving it – will it immediately
send back a reply or will it queue the request? Why?
(c) (2 points) What is P2’s state as per the RA algorithm when it receives CS request from P1 – Held,
Wanted, or neither (Free)? How will P2 handle P1’s request upon receiving it – will it immediately
send back a reply or will it queue the request? Why?
(d) (2 points) What is P3’s state as per the RA algorithm when it receives CS request from P1 – Held,
Wanted, or neither (Free)? How will P3 handle P1’s request upon receiving it – will it immediately
send back a reply or will it queue the request? Why?
(e) (2 points) What is P2’s state as per the RA algorithm when it receives CS request from P3 – Held,
Wanted, or neither (Free)? How will P2 handle P3’s request upon receiving it – will it immediately
send back a reply or will it queue the request? Why?
2. Leader Election – Bully Algorithm
Consider the following modification of the Bully algorithm: The initiating node (which we assume does
not fail) sends an Election message only to the process with the highest id. If it does not get a response
after a timeout, it then sends an Election message to the process with the second highest id. If after
another timeout it gets no response, it tries the third highest id, and so on. If no higher numbered
processes respond, it sends a Coordinator message to all lower-numbered processes.
(a) (1 point) What should a process do when it receives an Election message in order to minimize
turnaround time?
For the following parts, consider a distributed system of 8 processes {P1, P2, . . . P8}. P8 has the
highest id, followed by P7, then P6, and so on. The system uses the modified Bully algorithm for
leader election (including the solution for 2a). Initially, all 8 processes are alive and P8 is the leader.
Then P8 fails, P3 detects this, and initiates the election. P3 knows that P8 has failed and P7 has
the highest id among the remaining processes. Assume one-way message transmission time is T,
and timeout is set using the knowledge of T.
(b) (1 point) If no other node fails during the election run, how many total messages will be sent by
all processes in this election run?
(c) (1 point) If no other node fails during the election run, how long will it take for the election to
finish?
(d) (1 point) Now assume that right after P3 detects P8’s failure and initiates the election, P7 fails.
How many total messages will be sent by all processes in this election run?
(e) (1 point) For the above scenario (where P7 fails right after P3 initiates election upon detecting P8’s
failure), how long will it take for the election to finish?
3. Ring-based leader election + consensus
(5 points) Consider a system of N process that are arranged in a ring, with each process having a ring
successor and a predecessor, and a communication channel only to its ring successor. Each process Pi has
a unique id i. Further, each process Pi maintains a value xi (which may not be unique across processes).
A process may not know the total number of other processes in the ring.
Each process Pi
is required to set the value of an output variable yi (initialized to undecided) to
minN
j=1(xj ). The safety condition for the problem requires that, at any point in time, the variable
yi at process Pi ∀i ∈ [1, N] is either undecided or minN
j=1(xj ).
A distributed algorithm designed for the above problem works as follows:
• A process Pi
initiates the algorithm by sending (propose, xi) to its ring successor.
• When a process Pj receives (propose, x) from its ring predecessor:
– if x < xj , it forwards (propose, x) to its successor.
– if x > xj , it sends (propose, xj ) to its successor.
– if x = xj , it concludes that x = xj is the minimum value, and sends (decided, x) to its successor.
• When a process Pj receives (decided, x), it sets yj = x and forwards (decided, x) to its successor
(if it had not already done so in the past). Once Pj sets yj , it ignores any subsequently received
decided messages.
Multiple processes may initiate the above algorithm simultaneously. Assume no process fails and the
communication channel delivers all messages correctly and exactly once.
Does the algorithm described above guarantee safety condition for the problem? If yes, prove how. If
not, (i) describe a scenario where safety is violated, and (ii) suggest modifications to the algorithm that
would guarantee the safety condition.
4. Synchronous Consensus
Consider a system of five processes [P1, P2, P3, P4, P5]. Each process Pi proposes a value xi
. Let x1 = 6,
x2 = 5, x3 = 8, x4 = 2, and x5 = 10.
Each process Pk must decide on an output variable yk (initialized to undecided), setting it to one of the
proposed values xi for i ∈ [1, 5]. The safety condition requires that at any point in time, for any two
processes Pj and Pk, either yj or yk is undecided, or yj = yk (in other words, the decided value must be
same across all processes that have decided).
A consensus algorithm is designed for the above problem that works as follows:
• Each process R-multicasts its proposed value at the same time t = 0ms since start of the system
(as per their local clocks).
• As soon as proposed values from all 5 processes are delivered at a process Pj , Pj sets yj to the
minimum of the proposed values it received from the five processes.
• If yj is still undecided at time (t + timeout), Pj computes the minimum of the proposed values it
has received so far and sets yj to that value.
• Once a process Pj decides on yj , it does not update yj ’s value, and ignores future proposals (if any
are received).
Assume that all clocks are perfectly synchronized with zero skew with respect to one-another. The
proposed value xi of a process Pi gets self-delivered immediately at time t = 0ms when Pi begins the
multicast of xi
. A message sent from a process to any other process takes exactly T = 10ms (and this
value is known to all processes). All communication channels are reliable. Processes may fail, but a
failed process never restarts.
Suppose the timeout value for the above algorithm is set to 25ms. Answer the following questions with
respect to local time at the processes’ clock since the start of the system.
(a) (2 points) Assume no process fails in the system. When will each process decide on a value and
what will each of their decided values be?
(b) (2 points) Assume P4 fails right after unicasting x4 to P3 and P5 but just before it could initiate
the unicast of x4 to any of the other processes. When will each of the alive processes decide on a
value and what will each of their decided values be?
(c) (2 points) Assume P4 fails at right after unicasting x4 to P3 but just before it could initiate the
unicast of x4 to any of the other processes. P3 fails right after it has relayed x4 to P5 but just
before it unicasts it to any other process. When will each of the alive processes decide on a value
and what will each of their decided values be?
(d) (2 points) Assume P4 fails right after unicasting x4 to P3 but just before it could initiate the unicast
of x4 to any of the other processes. P3 fails right after it has relayed x4 to P5 but just before it
unicasts it to any other process. P2 fails right before it could unicast x2 to any process. When will
each of the remaining alive processes decide on a value and what will each of their decided values
be?
(e) (2 points) What is the smallest value that the timeout should be set to for ensuring safety in this
system?
(f) (1 point) Answer Q4c assuming that the timeout is updated to the value in Q4e.
(g) (1 point) Answer Q4d assuming that the timeout is updated to the value in Q4e.
5. Paxos
Consider a system of five processes that implement the Paxos algorithm for consensus. As shown in
Figure 2, P1 and P2 are proposers. P3, P4, P5 are acceptors. P1 sends a prepare message with proposal
number 2 to processes P4 and P5, receives their replies, and sends an accept message with proposed
value of 10 for proposal #2. P2 concurrently sends a prepare message with proposal #5, with an
initial intention to propose a value of 15 if it receives sufficient replies. Only a subset of responses from
processes P4, and P5 are shown in the figure. Assume no other proposals are initiated.
Answer the
following sub-questions.
0 1 2 3 4 5 6 7 8 9 10 11 12
P1
P2
P3
P4
P5
Prepare #2
13 14 15 16 17 18
Accept #2
Proposed value = 10
Prepare #5
Acceptors Proposers
Figure 2: Figure for question 5(f)
(a) (1 point) Which processes will accept P1’s proposal?
(b) (1 point) Which processes will reply back to P2’s prepare message?
(c) (2 points) Will P2 send out an accept message for its proposal #5? If yes, what will be the
corresponding proposed value?
(d) (2 points) Consider the state of the system at time 10 units. Has the proposed value 10 been
implicitly decided upon at this point? If yes, explain why? If not, construct a possible scenario that
may occur after time 10 units where the system ends up deciding on a different proposed value.
The scenario would involve a temporal sequence of events that may differ from the one shown in the
figure beyond time t=10units but must comply with what is shown until t=10units. An event in
such a sequence may include a prepare/accept request sent by a proposer or received by an acceptor,
or a prepare reply received by the proposer at some time unit.
(e) (1 point) Suppose that P1’s accept request reaches P5 at time 8 units (instead of 14 units). If we
now consider the state of the system at time 10 units, has the proposed value 10 been implicitly
decided upon?
(f) (1 point) Suppose that P1’s accept request reaches P4 at time 15 units (instead of 9 unit) and
reaches P5 at the original time 14 units. Will P2 send out an accept message for its proposal #5?
If yes, what will be the corresponding proposed value?