CODEWITHSUNDEEP
distributed-system
Shawn Armstrong
Shawn Armstrong

Reputation: 165

Can a distributed system designed with logical clocks truly derive a total ordering of events?

I’m reading Leslie Lamport’s white paper, “Time, clocks, and the ordering of events in a distributed system”. His explanation for total ordering has me a bit confused in the following excerpt.

enter image description here

  1. I've interpreted this as if event x's timestamp is less than event y then x happened before y.
  2. If x's timestamp is the same as y's timestamp then use the process name to determine who comes first.

I'm confused because if x is less than y then there are two possibilities to my understanding; either x happened first or x and y are concurrent. It seems like he's always assuming the former and never the latter.

Upvotes: 0

Views: 592

Answers (1)

AndrewR
AndrewR

Reputation: 1740

As a clarification: "A happened before B" means that result of A influenced B in some way. If A did not happen before B, then two events are concurrent - B is not influenced by A in any way - (not as wall time concurrent, but from causality point of view).

Two notes:

I've interpreted this as if event x's timestamp is less than event y then x happened before y.

Lamport timestamp does not capture causality. When X < Y, the only thing we can be sure about is that Y did no happened before X. We can't conclude if X happened before Y or they are concurrent. This is by definition of Total Order. To detect concurrent events, you would need to use Vector clock.

I'm confused because if x is less than y then there are two possibilities to my understanding; either x happened first or x and y are concurrent. It seems like he's always assuming the former and never the latter.

Technically you are right - for any two events they are either concurrent or one happened before the other. But we don't assume anything - we know that we won't be able to decide on this by using Total Order.

Edit: from your comment - " If they're concurrent then their timestamps do no provide any insight in their ordering so it seems impossible to create a total ordering."

I am not sure how you arrived to this statement. You actually create total order by throwing away the information about concurrency, that's the spirit of Lamport timestamp algorithm.

If we have:

  • event A happened before B
  • A happened before C
  • B happened before D
  • C happened before D

then we know that A happened before D. Applying Lamport timestamp algorithm will give us total order: ABCD or ACBD. While B and C are truly concurrent (neither happened before the other), they still will have different position in total order - even if we don't know which one will come first.

From another point of view - let's say we have a distributed system producing events. Using Lamport timestamp we will be able to get some total order. If we will send this total order to another distributed system for a replay of all events - the new system won't be able to decide on concurrency and will have to execute events one by one according to the total order.

Upvotes: 2

Related Questions