Ordering Events Without Trusting Any Clock

Subtitle: Throw away the clock. Keep a counter. Left column - Wall clock timestamps: - Two machines never agree exactly - Clocks drift apart every hour - A sync can jump time backwards - So a smaller time proves nothing - Ordering by timestamp is a guess Right column - Lamport clock: - No time at all, just a counter - One counter per process - Merge counters when you receive - Break ties with the process id - Gives a usable total order Three rules - the whole algorithm: 1. Bump your counter before each event 2. Send the counter with every message 3. On receive: max of both, then bump Simple difference: A before B -> ts(A) < ts(B) ts(A) < ts(B) -> proves nothing The trap - smaller is not earlier: - The converse does not hold - Concurrent events still compare - So it cannot detect concurrency - It respects order, never finds it - Vector clocks can, at a size cost Sticky note - Honest test: Fire two truly independent events and compare their counters. It answers, so the answer is meaningless.