Distributed computing

USING THE RESOURCE

• Process Pi starts using the resource when:
• its own request on its local request queue has the earliest Lamport timestamp T (consistent with );
• it has received a message (either an acknowledgement or some other message) from every other process with a timestamp larger than T.
• iii. (Always) On receiving a release from pj, remove the request from pj.

CORRECTNESS

• Theorem: Mutual exclusion and first-requested, first-served are achieved.
• Proof
• Suppose Pi and Pj are both using the resource at the same time and have timestamps Ti and Tj.
• Suppose Ti < Tj. Then Pj must have received i’s request, since it has received at least one message with a timestamp greater than Tj from Pi and since messages arrive in the order they are sent. But then Pj would not execute its request. Contradiction.
• First-requested, first-served. If Pi requests the resource before Pj (in the  sense), then Ti < Tj, so Pi will win.

CRITICISMS

• Many messages. If only one process is using the resource, it still must send messages to many other processes.
• If one process stops, then all processes hang (no wait freedom; could we achieve?)

Is there a Wait-Free Variant?

• Modify resource locally and then send to everyone. If everyone accepts the new value, then new resource value is good.
• Difficulty: what do you do if you don’t hear from someone? Could there be a partition of processes?
• Is this even possible?

NEED FOR PHYSICAL CLOCKS

• Time as a partial order is the most frequent assumption in distributed systems, however it is sometimes important to have a physical notion of time.
• Example: Going outside the system. Person X starts a program A, then calls Y on the telephone, who then starts program B. We would like A  B.
• But that may not be true for Lamport clocks, because they are sensitive only to inter computer messages. Physical clocks try to account for event ordering that are external to the system.

• X

• Y

• starts A

• Would like starts A  starts B
• But this may not be true with
•  as so far defined.

• calls y

• receives call
• from x

• starts B