Time and Ordering in Distributed Systems
Stub. Physical time and the sequential-vs-concurrent event distinction; logical (Lamport) clocks and vector clocks for capturing causality without a shared clock; and physical clock synchronization, internal and external.
Without a shared clock, “before” and “after” have to be defined causally rather than temporally: Lamport’s happened-before relation and the logical clocks that respect it, and vector clocks, which additionally let two events be recognized as concurrent rather than falsely ordered. Also covers the complementary problem of keeping real (physical) clocks approximately in sync, both among peers (internal synchronization) and against an external reference (external synchronization) — foundational for the snapshot algorithms and consistency models that follow.
Outline (TODO — flesh out each)
- Physical time; sequential and concurrent events
- Logical (Lamport) clocks
- Vector clocks
- Physical clock synchronization — clock reading error
- Algorithms for internal synchronization
- Algorithms for external synchronization