Consider the mutex algorithm of Ricart and Agrawala. Recall the assumptions: 1.
ID: 3813288 • Letter: C
Question
Consider the mutex algorithm of Ricart and Agrawala. Recall the assumptions:
1. Each thread executes at non-zero speed.
2. Communication lines and input ports are non-FIFO (“non” here means “not necessarily”).
3. Each thread can receive its input messages independently, without synchronization issues with other threads’ inputs.
In each question, a modification to the code is suggested.
Will the new code work? (YES or No).
If Yes, give an explanation, in less than 50 words.
If No, give a counter example. In this example, assume we have EXACTLY TWO processes P0 and P1 in the system.
Q2.
Make the following change: A reply message in a communication line may get duplicated so that two identical copies of the sent reply message arrive at the input port, instead of just one copy.
Explanation / Answer
Show that in the Ricart-Agrawala algorithm, the critical section is accessed according to the increasing order of timestamps.
Answer: Proof by contradiction. Suppose process p1 issues a request to enter the critical section at time t1t1, p2 issues
a similar request at time t2 with t1 < t2, and p2 enters first. This means that p2 has received reply messages from all
other processes including p1. But p1 will send such a message only if it is neither requesting nor executing the critical
section (which is false) or if p2's request's timestamp is smaller than that of p1's request (which is also false).
Hence p1 will not send a reply to p2's request, and so p2 cannot enter the critical section first. This contradicts
hypothesis, proving the claim.