Distributed System Notes - goofycoder/knowdb GitHub Wiki

Lamport timestamps

Why we need Lamport timestamps?

• Distributed algorithms depend on some method of ordering events to function.
• Example: a system with two processes and a disk.
  • The processes send messages to each other, and also send messages to the disk requesting access.
  • The disk grants access in the order the messages were sent.
    1. process 1: sends a message to the disk asking for access to write
    2. process 1: sends a message to process 2 asking it to read.
    3. Process 2: receives the message from Process 1
    4. Process 2: 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?
  • (A happens-before B if one can get from A to B by a sequence of moves of two types: moving forward while remaining in the same process, and following a message from its sending to its reception.)
  • A logical clock algorithm provides a mechanism to determine facts about the order of such events.

The algorithm of Lamport timestamps

• a simple algorithm used to determine the order of events in a distributed computer system.
  • the happened-before ordering can be captured numerically.
• this algorithm is used to provide a partial ordering of events with minimal overhead - different nodes or processes are typically not be perfectly synchronized
• Conceptually provide a starting point for the more advanced vector clock method.
• A Lamport logical clock is an incrementing software counter maintained in each process.

Details about Lamport timestamps:

Lamport timestamps 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.
• Conceptually, this logical clock can be thought of as a clock that only has meaning in relation to messages moving between processes. When a process receives a message, it resynchronizes its logical clock with that sender.