Lamport & Vector Clocks | miafish

Lamport & Vector Clocks | miafish

They are two algorithms used to determine the order of events in a distributed computer system.

Why do we need it?

Now, imagine process 1 sends a message to the disk asking for access to write, and then sends a message to process 2 asking it to read. Process 2 receives the message, and as a result sends its own message to the disk. Now, due to some timing delay, the disk receives both messages at the same time: how does it determine which message happened-before the other?

two synchronized servers that write timestamps to the same system. If one server falls behind by even a few milliseconds, it would quickly be impossible to know the actual order of events.

Lamport Timestamps

It follows some simple rules:

• A process increments its counter before each event in that process;
• When a process sends a message, it includes its counter value with the message;
• On receiving a message, the receiver process sets its counter to be greater than the maximum of its own value and the received value before it considers the message received.

if  A -> B, then L(A) < L(B). so we know who happened first.

Vector clock

It follows rules:

• Initially all clocks are zero.
• Each time a process experiences an internal event, it increments its own logical clock in the vector by one.
• Each time a process prepares to send a message, it sends its entire vector along with the message being sent.
• Each time a process receives a message, it increments its own logical clock in the vector by one and updates each element in its vector by taking the maximum of the value in its own vector clock and the value in the vector in the received message (for every element).

Read full article from Lamport & Vector Clocks | miafish