Lamport Clocks

Question 1

What is the purpose of the Lamport logical clock?

Answer 1

Simple mechanism to capture the happened-before ordering numerically

Question 2

What is a process pi logical clock, Li used for?

Answer 2

Li used to apply Lamport timestamps to events

Question 3

How are Lamport timestamps denoted?

Answer 3

The timestamp of event e at pi is denoted by Li(e)

Question 4

How is the happened-before relation captured?

Answer 4

processes update their logical clocks and transmit the values of their logical clocks in messages

Question 5

State LC1

Answer 5

LC1: Li is incremented before each event is issued at process pi (Li = Li + 1)

Question 6

State LC2 sends

Answer 6

LC2: When process pi sends message m, it piggybacks on m the value t = Li

Question 7

State LC2 recieves

Answer 7

LC2: On receiving (m, t), a process pj computes

Lj = max(Lj, t) and then applies LC1 before timestamping the event receive(m)

Question 8

State the limitation of Lamport clocks

Answer 8

from L(e) < L(e’) we cannot conclude that e → e’