CampusLearn
← CSC 413 Distributed Systems

Clock Synchronization and Logical Time

Notes

Clock Synchronization and Ordering In centralized systems, event ordering is governed by a shared hardware clock and operating system timer. In distributed systems, each independent node relies on an internal quartz oscillator that experiences physical clock drift caused by temperature variations and hardware aging. Because absolute synchronization across independent nodes is physically impossible without minor discrepancies, distributed algorithms must implement logical clocks or specialized physical clock synchronization protocols. Physical and Logical Clocks Physical clock synchronization algorithms include Christian algorithm for external synchronization via a centralized time server and the Berkeley algorithm for internal synchronization where a coordinator polls worker nodes, averages the observed drift while discarding outliers, and sends clock adjustments back to the nodes. When physical precision cannot be guaranteed, Lamport timestamps provide a causal ordering of events based on the happened-before relation. If event A causes event B, the timestamp of A must be strictly lower than B. Vector clocks extend Lamport timestamps by maintaining an array of logical counters, allowing nodes to determine whether two events are causally related or concurrent. Practical example The Nairobi Securities Exchange (NSE) operates an automated trading system that ingests limit orders from multiple independent stockbroker nodes located in Upper Hill, Westlands, and international institutional conduits. If two brokers submit buy orders for Safaricom shares at the exact market opening, relying on uncoordinated local server timestamps could cause conflicting execution orders or unfair trade precedence. The NSE distributed matching engine implements Lamport logical timestamps alongside Network Time Protocol (NTP). Each broker application increments its local counter before broadcasting an order. When the matching engine receives an incoming order message, it updates its own logical clock to exceed the message timestamp before assigning the execution sequence. If network jitter delays an order originating from a Mombasa branch compared to a Westlands branch, the causal ordering guarantees that dependent transactions are queued fairly, preventing arbitrage exploits and preserving market integrity across Kenya.

Quiz

1. In Lamport logical clocks, what rule is applied when a node receives a message with timestamp Tm?

2. Which timing construct enables distributed systems to detect whether two events are causally related or concurrent?

3. How does the Berkeley algorithm achieve internal physical clock synchronization?

Sign in to submit and securely grade your quiz.