Hybrid Logical Clocks

Remco Bloemen

Definition: happened-before is a scrict partial order

  1. If two events ee and ff are on the same site and ee occurred before ff, then ee happened-before ff.
  2. If ee is sending a message and ff is receipt of the message, then ee happened-before ff.
  3. If ee happened-before ff and ff happened-before gg, then ee happened-before gg.

Definition: concurrent. Two events ee and ff are concurrent iff neither ee happened-before ff nor ff happened-before ee.

Lamport timestamps

Vector clocks

Hybrid logical clocks

Source:

http://muratbuffalo.blogspot.nl/2013/08/beyond-truetime-using-augmentedtime-for.html

http://muratbuffalo.blogspot.nl/2013/07/spanner-googles-globally-distributed_4.html

http://muratbuffalo.blogspot.nl/2014/07/hybrid-logical-clocks.html