Barriers and distributed snapshots: group state without simultaneity
Why does a barrier cost the slowest member, and how does a snapshot get global state without simultaneity?
Barriers
A barrier makes all N participants wait for the last one. So the group time per round is E[max of N] (the expected maximum) and not E[mean]. The barrier converts a mean into a tail quantile, every round, forever. This is the tail-at-scale arithmetic turned into a synchronization primitive, and it is why a single straggler prices the whole group. Implementation costs O(N) messages to a coordinator, or O(log N) latency through a tree, but the message cost is never the problem. The order statistic is.
Snapshots
A snapshot wants something stronger and cannot have it: a global state at an instant. That requires simultaneity, which does not exist. The substitute is a consistent cut: a set of local states plus in-flight messages, such that no recorded receive lacks a recorded send.
Chandy-Lamport achieves it with marker messages on FIFO (first-in-first-out) channels:
- A node that starts the snapshot records its own state and sends a marker on all its outgoing channels.
- A node that receives its first marker records its local state, and sends markers on all outgoing channels.
- After that, it records every message that arrives on each other channel until the marker arrives on that channel.
The resulting snapshot may describe a global state that the system was never actually in. It is still usable, because no participant could have distinguished it from a real one. That is the purest case of this article's governing move: simultaneity is unobservable, so it is replaced by indistinguishability from simultaneous, and the replacement is legislated to be good enough.
The aligned/unaligned distinction (used in stream processors) is the barrier trade applied to snapshots. Aligned snapshots hold back fast inputs until the slowest marker arrives (paying the max, as above). Unaligned snapshots record in-flight data into the snapshot instead (paying in snapshot bytes and recovery time). It is buffering time versus snapshot size, and which one you want depends on whether your skew or your state is larger. The streaming use is a stream-processing topic; the primitive and its cost belong here.
Compression: a barrier prices the group at its slowest member every round, and a snapshot buys global state by settling for a cut nobody inside can tell from simultaneous.