Synchronization and Coordination
Open in the Padhaiko app3.1 Need for Synchronization and Physical Clock Synchronization
In a distributed system, there is no shared global clock or shared memory. Each machine uses a quartz crystal oscillator that experiences slight frequency variations (clock drift), causing clocks on different nodes to diverge (clock skew).
Why Synchronization Is Essential
- Consistent Ordering & Causality: Distributed databases, logs, and transaction managers must determine which event occurred first.
- Mutual Exclusion & Resource Allocation: Multiple processes sharing files, locks, or critical sections must avoid race conditions and deadlocks.
- Data Freshness & Security: Cache leases (Kerberos tickets, TLS certificates,
makebuild timestamps) depend on bounded clock agreement.
3.1.1 Cristian's Algorithm (External Synchronization)
A client requests the current time from a UTC-synchronized time server (). Let:
- = client timestamp when request is sent,
- = client timestamp when reply is received,
- = UTC time returned by the server,
- = server interrupt/processing time (if known; otherwise ).
Assuming symmetric network propagation delays, the one-way delay is , so the client sets its clock to:
- Accuracy Bound: If the minimum one-way transmission time is , the error is at most .
- Monotonicity Rule: Never set a local clock backward abruptly; instead, slew (slow down) the clock rate gradually until it matches .
3.1.2 Berkeley Algorithm (Internal Synchronization)
Used when no external UTC source is available and all nodes only need to agree with one another:
- A designated time daemon (coordinator) polls every node for its current clock value (measuring round-trip time to compensate).
- Each node replies with its clock offset relative to the daemon.
- The daemon computes a fault-tolerant average (discarding outlier/faulty clocks that differ beyond a threshold).
- Instead of broadcasting the absolute time (which would introduce delay error), the daemon sends each node its signed adjustment ( forward or slow-down).
3.1.3 Network Time Protocol (NTP)
NTP scales external synchronization across the Internet using a hierarchical stratum tree:
- Stratum 0: Atomic clocks / GPS receivers (reference hardware).
- Stratum 1: Primary servers directly attached to Stratum 0 sources.
- Stratum 2+: Secondary servers synchronizing from Stratum 1/2 over the network.
Let client send a packet at , server receive it at , reply at , and client receive the reply at :
Client adjusts its clock by to align with server (accuracy over WAN, on LAN).
| Algorithm | Sync Type | Master / Hierarchy | Fault Tolerance | Typical Accuracy |
|---|---|---|---|---|
| Cristian's | External (UTC) | Single time server | Single point of failure (needs backup) | |
| Berkeley | Internal | Elected coordinator daemon | Discards outlier clocks; re-elects daemon | Few ms on LAN |
| NTP | External (UTC) | Hierarchical Strata () | Multiple redundant peers + filtering | WAN; LAN |
3.2 Logical Clocks: Lamport Clocks, Vector Clocks, Event Ordering, and Causality
When exact wall-clock time is unnecessary, logical clocks capture the causal order of events without physical clock synchronization.
3.2.1 Lamport's Happened-Before Relation and Logical Clocks
Happened-Before Relation and Lamport Timestamps
Leslie Lamport (1978) defined the happened-before relation (, read " causally precedes ") as the smallest strict partial order satisfying:
- Same Process: If and are events in the same process and occurs before , then .
- Message Passing: If is the sending of a message and is the receipt of that same message, then .
- Transitivity: If and , then .
If neither nor , the events are concurrent ().
Lamport Clock Update Rules
Each process maintains a scalar integer counter (initially ):
- Local / Send Event: Before executing a local event or sending a message , increments and attaches timestamp to .
- Receive Event: Upon receiving , updates:
- Key Property (One-Way Implication): .
- Limitation: The converse is false! does not prove (concurrent events may still have ). Total ordering can be obtained by breaking ties with process IDs: .
3.2.2 Vector Clocks (Capturing Exact Causality)
To detect concurrency accurately (), each process in an -process system maintains an -element vector (initially all ):
- Local / Send Event at : Increment own entry ; attach to every outgoing message.
- Receive Event at (receiving ): Update component-wise maximum, then increment own entry:
Comparing Two Vector Timestamps and
- iff for all .
- (): and (strictly smaller in at least one index).
- Concurrent (): Neither nor (some index is larger in and another is larger in ).
| Aspect | Lamport Clocks | Vector Clocks |
|---|---|---|
| State per Process | Single integer | Vector of integers |
| Message Overhead | integer per message | integers per message |
| Causality Equivalence | (converse FALSE) | (exact!) |
| Concurrency Detection | Cannot distinguish concurrent from causal | Detects immediately |
3.3 Global State and Distributed Snapshots: Chandy-Lamport Algorithm
A consistent global state consists of local states of all processes plus the in-flight messages on every communication channel, without violating causality (i.e., if receipt of is recorded, sending of must also be recorded).
Chandy-Lamport Distributed Snapshot Algorithm
Assumes FIFO, reliable, unidirectional channels between processes:
- Initiation: An initiator process records its local state, then immediately sends a special Marker message along all its outgoing channels before sending any further application messages.
- Receiving a Marker for the First Time ( on channel ):
- records its own local state.
- Marks channel as empty (since no in-flight messages preceded the marker on after 's snapshot).
- Starts recording incoming messages on all other incoming channels ().
- Sends a Marker out on all its outgoing channels.
- Receiving a Subsequent Marker ( on channel , already recorded):
- Stops recording on channel ; the messages captured since took its snapshot form the in-flight state of channel .
- Termination: Once every process has recorded its local state and received a marker on all incoming channels, the collected local states and channel states form a consistent global cut (used for deadlock detection, checkpointing, and garbage collection).
3.4 Distributed Mutual Exclusion: Centralized, Ricart-Agrawala, Token Ring, and Maekawa
To guarantee safety (at most one process in the Critical Section, CS), liveness (no deadlock/starvation), and fairness (FIFO/ordered entry) across processes:
- Centralized Algorithm:
- A single coordinator grants
OKto one requester at a time and queues others. - Cost: messages per CS entry (
REQUEST,GRANT,RELEASE). - Weakness: Single point of failure and coordinator bottleneck.
- A single coordinator grants
- Ricart-Agrawala Algorithm (Permission-Based, Distributed):
- Process wanting CS broadcasts
REQUEST(T_i, i)to all other processes. - Receiver replies
OKimmediately unless is in CS, or also wants CS with a lower timestamp (in which case defers itsOKuntil leaving CS). - Cost: messages per CS entry (
REQUESTs +OKs). - Weakness: Every single node is a point of failure (if one node crashes without replying, everyone stalls).
- Process wanting CS broadcasts
- Token Ring Algorithm:
- Processes are arranged in a logical ring; a single token circulates continuously around the ring.
- A process may enter CS only while holding the token, then passes it to its ring neighbor.
- Cost: to messages per CS entry (or idle passes), zero starvation, but must detect and regenerate lost tokens.
- Maekawa's Algorithm (Quorum-Based):
- Instead of asking all nodes, each process requests permission only from a voting set (quorum) of size , where every pair of voting sets overlaps ().
- Since each voter grants permission to at most one requester at a time, overlapping quorums guarantee mutual exclusion.
- Cost: messages (
REQUEST,GRANT,RELEASE), or up to with deadlock avoidance (INQUIRE,RELINQUISH,FAILED).
| Algorithm | Messages per Entry/Exit | Synchronization Delay | Failure Vulnerability |
|---|---|---|---|
| Centralized | message times | Coordinator crash | |
| Ricart-Agrawala | message times | Any single process crash blocks entry | |
| Token Ring | to (idle circulation) | to hops | Lost token or broken ring link |
| Maekawa's Quorum | (to w/ deadlock handling) | message times | Quorum member crash (requires alive) |
3.5 Election Algorithms: Bully and Ring
Election algorithms dynamically select a single living process with the highest unique ID as the new coordinator after a coordinator failure.
3.5.1 Bully Algorithm
When process notices the coordinator is unresponsive:
- sends an
ELECTIONmessage to all processes with higher IDs (). - If no higher process responds within timeout , wins and broadcasts
COORDINATORto all lower processes. - If a higher process responds with
OK("alive"), steps back and starts its own election among processes .
- Message Complexity: Best case (when the highest surviving node starts); worst case (when the lowest-ID node initiates and triggers cascading elections).
3.5.2 Ring Algorithm
Processes are arranged in a logical unidirectional ring (each knows its successor list):
- Initiator creates an
ELECTION([k])message containing its own ID and sends it to its next living clockwise neighbor. - Each receiving process appends its own ID to the list and forwards it around the ring.
- When the message returns to , picks the maximum ID in the list as the winner and circulates a
COORDINATOR(winner)message around the ring once more.
- Message Complexity: Always messages ( for
ELECTION+ forCOORDINATOR), even if two elections run concurrently.
3.6 Coordination Services: ZooKeeper and etcd
Modern distributed clusters offload leader election, distributed locks, service discovery, and configuration management to dedicated consensus-backed coordination services rather than re-implementing them inside every application.
| Aspect | Apache ZooKeeper | etcd |
|---|---|---|
| Consensus Protocol | ZAB (ZooKeeper Atomic Broadcast) | Raft |
| Data Model | Hierarchical tree of znodes (like filesystem paths) | Flat key-value store with hierarchical prefix keys & revisions |
| Node / Key Types | Persistent, Ephemeral (auto-deleted on session timeout), Sequential | Keys attached to Leases (auto-deleted on TTL expiry) |
| Change Notification | One-time Watches (must re-register) | Persistent streaming Watches over gRPC |
| Primary Ecosystem | Hadoop, HBase, legacy Apache Kafka | Kubernetes control plane store, CoreOS, service discovery |
How Coordination Primitives Work
- Leader Election: Every candidate creates an ephemeral sequential znode (in ZooKeeper) or competes to attach a lease key via compare-and-swap (in
etcd). The lowest sequence number (or lease winner) becomes leader; followers watch the preceding node so they react instantly on crash. - Distributed Locks & Service Registration: Services register ephemeral/leased entries on startup; if a node crashes, its session/lease expires and the registry removes it automatically.
Worked Out Examples
3.1
- NTP Calculation: Client sends an NTP request at . Server receives it at and sends the reply at . Client receives the reply at . Compute the round-trip delay and clock offset , and state how should adjust its clock.
- Berkeley Algorithm: A time daemon's clock reads
03:00:00. Three cluster nodes report clocks of02:59:45(),03:00:25(), and03:00:10(). Calculate the average offset and the adjustment sent to each node (including the daemon).
Part 1 — NTP Delay and Offset:
Since , client should advance its clock by (to ).
Part 2 — Berkeley Algorithm Adjustments: Relative offsets from the daemon (03:00:00): seconds across nodes:
Target synchronized clock time .
- Daemon (
03:00:00): - Node 1 (
02:59:45): - Node 2 (
03:00:25): (slow clock gradually) - Node 3 (
03:00:10): (slow clock gradually)
- NTP delay , offset (advance client clock by ).
- Berkeley target is
03:00:05; adjustments are (daemon), (Node 1), (Node 2), (Node 3).
3.2
Three processes start with vector clocks . The following events occur:
- : local event , then sends to (event ).
- : receives (event ), then sends to (event ).
- : local event , then receives (event ).
- : local event .
Compute the Vector Clocks for all events and determine the relationship between and .
Tracing Vector Clock Updates:
- :
- (local):
- (send ): , sends
- (local):
- :
- (recv with ):
- (send ): , sends
- :
- (local):
- (recv with ):
Checking Causality and Concurrency:
- Comparing and : Since (index 1) while (index 2), neither vector dominates the other (concurrent).
- Comparing and : Every entry of is with strict inequality ( causally precedes ).
Vector timestamps: , , , , , , . Thus (concurrent) and (causal).
3.3
A cluster has nodes with IDs . Node (the coordinator) crashes, and Node detects the failure first.
- Trace the Bully Algorithm messages and count the total messages sent (assuming no other node starts concurrently).
- Compare with the Ring Algorithm message count for the same surviving nodes (say Node initiates), and compute the messages per CS entry in Ricart-Agrawala if all nodes were active.
1. Bully Algorithm Trace (Node crashed; Node initiates):
- Node sends
ELECTIONto higher nodes ( messages). Nodes and replyOK( messages; is dead). - Node sends
ELECTIONto ( messages); Node repliesOK( message). - Node sends
ELECTIONto ( message); gets no reply after timeout, so Node wins! - Node broadcasts
COORDINATORto all surviving lower nodes ( messages). - Total Bully messages messages.
2. Ring Algorithm and Ricart-Agrawala Counts:
- Ring Algorithm ( surviving nodes):
ELECTIONhops around the surviving ring +COORDINATORhops messages. (With all nodes alive: messages.) - Ricart-Agrawala (): messages per CS entry.
- Bully elects Node using messages ( election/OK + coordinator broadcasts).
- Ring uses messages among the survivors ( for nodes); Ricart-Agrawala uses messages per CS entry.
Exercises
Practice Exercises — Synchronization and Coordination
In an NTP exchange, client sends a request at , server receives it at and replies at , and client receives the reply at . Calculate the round-trip delay and clock offset . Also state how Cristian's algorithm differs from the Berkeley algorithm.
Calculating NTP Delay and Offset:
Client 's clock is ahead of server , so slews its clock back by .
Cristian's vs. Berkeley Algorithm:
- Cristian's: External synchronization against a single UTC server; each client polls the server independently.
- Berkeley: Internal synchronization without UTC; a coordinator daemon polls all nodes, averages their clocks (filtering outliers), and distributes relative adjustments.
, (client slows clock by ). Cristian's synchronizes externally to UTC, whereas Berkeley synchronizes nodes internally around a fault-tolerant average.
Explain why Lamport timestamps cannot detect concurrent events, and prove with a small two-event example how Vector Clocks resolve this ambiguity.
Limitation of Lamport Clocks: Lamport clocks map causal order to a single scalar (), compressing an -dimensional partial order into dimension. Therefore holds for both causally ordered events and many concurrent events.
Vector Clock Example: Suppose executes local event () and executes two local events ().
- Scalar Lamport clocks give , falsely suggesting might precede .
- Vector clocks satisfy and , proving immediately that (concurrent).
Lamport clocks satisfy only in one direction; concurrent events like and have , whereas vector clocks detect concurrency cleanly because neither vector is component-wise the other.
Describe the Chandy-Lamport distributed snapshot algorithm step by step, stating its channel assumptions and explaining how in-flight messages are captured.
Assumptions: Communication channels are reliable, unidirectional, and FIFO (messages arrive in the exact order sent).
Algorithm Mechanism:
- Initiator records its local state and immediately sends a Marker on all outgoing channels.
- When any process receives its first Marker on incoming channel , it records its local state, marks as empty, starts logging messages arriving on all other incoming channels, and forwards Markers on all its outgoing channels.
- When receives a Marker on another incoming channel , it stops logging on —the logged messages represent the in-flight channel state of .
Assuming reliable FIFO channels, Chandy-Lamport uses Marker messages to separate pre-snapshot and post-snapshot traffic: each process records its state upon receiving its first Marker, sends Markers outward, and logs messages arriving on every other incoming channel until that channel's Marker arrives.
For a system of processes, compare the message complexity per critical section entry of Centralized, Ricart-Agrawala, Token Ring, and Maekawa's algorithm (with quorum size , minimal 3-phase REQUEST/GRANT/RELEASE). Also state the main failure weakness of each.
Message Counts for :
- Centralized: messages (
REQUEST,GRANT,RELEASE). Weakness: Coordinator crash stalls everyone. - Ricart-Agrawala: messages. Weakness: Any single crashed node fails to reply
OK, stalling entry. - Token Ring: to hops when active (plus idle ring traffic). Weakness: Lost token or broken link needs recovery.
- Maekawa's (): messages (
REQUEST,GRANT,RELEASEto quorum members; up to if deadlock resolution is triggered). Weakness: Susceptible to deadlocks withoutINQUIRE/RELINQUISH, and quorum node failure blocks that quorum.
Messages per CS entry (): Centralized = , Ricart-Agrawala = , Token Ring = , Maekawa () = (basic). Centralized fails on coordinator crash; Ricart-Agrawala blocks on any node crash; Token Ring fails on lost token; Maekawa risks deadlock without extra probes.
Compare Bully and Ring leader election algorithms in terms of message complexity and failure handling. Explain how ZooKeeper and etcd implement leader election and service discovery in modern cloud clusters.
Bully vs. Ring Election:
- Bully: Higher-ID processes pre-empt lower ones. Best case messages; worst case when the lowest-ID node initiates.
- Ring: Appends live IDs around a logical ring and announces the maximum ID; always takes messages regardless of who initiates.
ZooKeeper and etcd Coordination:
- ZooKeeper (ZAB consensus): Uses ephemeral sequential znodes; the lowest-sequence node is leader, and followers place watches on their immediate predecessor to detect crashes automatically.
- etcd (Raft consensus): Uses TTL leases and atomic compare-and-swap transactions with gRPC streaming watches (e.g., powering Kubernetes control plane leader election and state storage).
Bully takes messages by contacting higher IDs, whereas Ring always uses messages around a ring. ZooKeeper (ZAB + ephemeral sequential znodes + watches) and etcd (Raft + leases + gRPC watches) provide consensus-backed leader election and automatic liveness tracking.