Distributed Systems — Episode 5

Physical clocks drift, while networks add variable and often asymmetric delay. Synchronization may be internal, keeping nodes close together, or external, relating them to reference time. NTP estimates offset and transmission delay and arranges sources into accuracy strata. The episode also covers Reference Broadcast Synchronization for wireless networks and Google's TrueTime in Spanner. A protocol exploits its environment and represents uncertainty; it cannot create a perfectly shared instant by abstraction alone.

Many algorithms need an agreed order rather than a calendar timestamp. Leslie Lamport's happens-before relation captures causally observable sequencing, and logical clocks can impose an order on messages. Totally ordered multicast uses that property for state machine replication, where replicas execute the same commands in the same sequence. Yet comparing two Lamport clock values does not by itself prove causality. Vector clocks retain enough information to distinguish dependent events from concurrent ones. Message-ordering rules also cannot always be hidden in middleware, because only the application knows which delivery semantics preserve its business invariants.

Mutual exclusion is needed when concurrent processes could corrupt a shared resource. The chapter compares several algorithm families and then connects the abstraction to coordination services. A ZooKeeper lock can be represented by creating a node in its hierarchical namespace: one contender acquires ownership while others coordinate through service state. Google's Chubby provides a related production example. The design question is broader than throughput. Engineers must know where coordination authority lives, what evidence grants ownership, and how participants determine that a previous owner can no longer perform the role safely.

Leader election solves a wider problem: some algorithms require a coordinator but not a particular process. The episode compares the bully algorithm, a ring algorithm, ZooKeeper's election, and Raft. Each assumes specific membership, identifiers, delivery, and failure detection. Wireless networks expose those assumptions because delivery and topology are unstable. Permissionless blockchains add another setting: proof of work and proof of stake coordinate participants without fixed, trusted membership.

Gossip-based coordination spreads locally known changes through repeated exchanges among neighbours. It fits problems that value scale and eventual shared knowledge more than an immediate global order. The guarantee changes accordingly: instead of one arbiter, nodes temporarily hold different views while information propagates. Gossip should not be selected merely because its interface looks simple. A design must state how much divergence is acceptable, how convergence is recognized, and what happens when an operation actually requires strict sequencing or a unique owner.

Distributed event matching makes the same choices visible in publish-subscribe systems. Matching events to subscriptions may use a scaled central service, selective routing, or gossip; privacy introduces searchable-encryption techniques such as PEKS. The final topic is locality. GPS coordinates, Wi‑Fi positioning, and logical coordinates in an overlay network help nearby processes communicate with preferable peers. The episode's practical conclusion is to name the relation first—clock accuracy, causality, exclusivity, convergence, or proximity—and choose a coordination mechanism only after that requirement and its failure assumptions are explicit.