Logical Time, Lamport Timestamps and Vector Clocks in distributed systems

Question

I am currently studying Distributed Systems for an exam. I think I have understood all the principles so far, but I go crazy when it comes to the topics of logical time, lamport timestamps and vector clocks. I just can't get an overview and connections to the topics. Here is my index card, which I would like to write...

Logical Time

• enables coordination of events without physical clock
• achieved by: ordering events into "happened before" relations
• each process knows order of local events, as timestamps are assigned to every event
• these timestamps can be lamport timestamps:
• or vector clocks:

I just don't know what to put behind lamport timestamps and vector clocks and generally what enables what, what implements what and why one can make competition visible and the other not. Can someone help me get an overview?

To look up definitions on wikipedia and reading scientific work has helped not that much...

Answer 1

In distributed systems it is very hard to keep wall clocks in sync. Different applications have different tolerance for clock drift. For example, some distributed systems use clock to resolve conflicts (last update wins) and they accept the risk that clocks might not be in sync. But in some cases there are no tolerance.

As you correctly said, logical clocks were invented to address timing in distributed systems. There are two main problems to resolve: a) events needs to be totally ordered and b) detect concurrent events. Lamport timestamp addresses the total order problem; and vector clock helps to detect concurrent events.

So if I would create an index card, I would actually create several of them:

Global/Wall clock

• allows events to be ordered globally, but the risk is that clocks will get out of sync
• worth exploring how Cassandra deals with Last Updates Win strategy

Lamport timestamp

• this is a logical clock
• it allows total order of events
• (all other info on lamport timestamp)

Version clock

• this is a logical clock
• it allows detecting concurrent events
• (...note what "concurrent" means)
• all other info on vector clock
• not to be confused with version vector

Version vector

• ...