CODEWITHSUNDEEP
messagingdistributed-computingstate-machine
mname
mname

Reputation: 53

Lamport Clock and state machine

I am reading the Lamport's paper on Clock and State machine and there is a little point that I don't understand. Lamport state that: "A process can execute a command timestamped T when it has learned of all commands issued by all other processes with timestamps less than or equal to T. The precise algorithm is straight- forward, and we will not bother to describe it."

The algorithm is straightforward, but I actually don't have it... How do a process knows that there are no more incoming message with a timestamp less than or equal to the timestamp of the message to be processed?

It might be solved by all processes broadcasting an ACK when they receives a message... So since the message are ordered, upon receiving the ACK a process knows that there are no incoming message with a lower timestamp... But this does not look like "a straightforward algorithm".

Hope I'm clear enough.

Upvotes: 3

Views: 388

Answers (1)

Forketyfork
Forketyfork

Reputation: 7810

The process knows there are no more commands, because/when it received a command with a timestamp >=T from every other process.

Say we have a process P1 that received from process P2 a command with timestamp T2 >= T. Upon receiving this command, process P1 immediately learns of all the commands by P2 that were issued before or concurrently with its command timestamped with T.

Actually P1 can learn of all the intermediate commands even if they were not received yet (for example, P2 could assign an ordinal number to each command sent, so P1 would notice the gap in numbers). Then P1 can choose either to wait for the missing commands, or re-request them if they were lost during transmission.

So to execute the command timestamped with T, process P1 must wait until it receives a single command with timestamp >=T from every other process — then it can wait for (or re-request) all the missing intermediate commands and execute the command T.

Upvotes: 2

Related Questions