Distributed Systems as a Local-to-Global Problem

A course built on one analogy, carried the whole way: a distributed system is data defined locally on overlapping regions, and consistency is the question of whether that local data glues into a global whole. That is the sheaf condition, and when it fails the obstruction is a cohomology class — the same class that obstructs a hidden-variable account of quantum correlations, and the same class that makes a database schedule non-serialisable.

The analogy is not decorative. It predicts which impossibility results are of which kind, says in advance why CRDTs work, and explains why two famous theorems that sound similar (FLP and CAP) are not the same statement at all.

Prerequisites: comfort with partial orders and basic linear algebra over 𝔽₂. No topology assumed; the cohomology is built from scratch and stays finite-dimensional.

Part I — The presenting problem

1.1 Local agreement does not imply global agreement

Three nodes, each holding one bit. Each pair of nodes has agreed a constraint, and every pair is individually satisfiable:

Every pair agrees. No global assignment exists. Verified by exhaustion: zero of the eight global assignments satisfy all three.

Now flip the last constraint to 0 and you get two global solutions, (0,0,0) and (1,1,1). The local data is structurally identical in both cases — three pairwise constraints, two solutions each. The difference is one bit: the sum of the parities around the cycle.

That bit is the whole course.

Exercise 1.1. Generalise to n nodes in a ring with parities p₁…pₙ. Show a global assignment exists iff Σpᵢ = 0 mod 2, and that when it exists there are exactly two.

Exercise 1.2. Now let the nodes form a tree rather than a ring. Show a global assignment always exists, for any parities. What changed?

1.2 What the second exercise is telling you

The tree has no cycles, and with no cycles there is no sum-around-a-loop to obstruct anything. The obstruction lives on cycles, and only on cycles.

This is the shape of the whole subject. Keep it in view: whenever a distributed system cannot reach global consistency despite every local view being fine, look for the loop.

Part II — The formal picture

2.1 Happens-before is a partial order, and that is a causal structure

Lamport’s 1978 relation: event a happens-before b if they are on the same node and a precedes it, or a is a send and b the matching receive, plus transitivity. Events not related either way are concurrent.

This is a partial order, not a total one, and that is not a limitation to be engineered away — it is what the system is. Lamport drew the analogy to special relativity explicitly: concurrent events are spacelike separated, and asking which happened first is asking a question with no observer-independent answer.

Consequence you can use. A logical clock is a map from events to a totally ordered set that respects happens-before. A vector clock is the finer object that reconstructs the partial order exactly: VC(a) ≤ VC(b) iff a → b. The partial order is the invariant; a scalar timestamp is a lossy projection of it.

Exercise 2.1. Show that a scalar Lamport clock can order two concurrent events either way depending on implementation, and that no scalar clock can detect concurrency. Then show a vector clock of length n does, and that n is optimal.

2.2 The cover, the sections, the restriction maps

Set up the sheaf properly, because everything later is a specialisation of it.

• The space is the set of variables (keys, registers, objects) the system holds.
• A cover is a collection of subsets U₁…Uₘ, one per node or per transaction — what that participant can see.
• A local section over Uᵢ is an assignment of values to the variables in Uᵢ that is consistent by that participant’s lights.
• Restriction takes a section over U and forgets everything outside U ∩ V.

The sheaf condition: local sections that agree on every overlap glue to a unique global section.

Distributed consistency is exactly the claim that the sheaf condition holds. §1.1 is a cover of three variables by three pairs, with local sections that agree on overlaps, and no gluing.

Exercise 2.2. Write §1.1 in this language explicitly: name the cover, the sections over each Uᵢ, and the restriction maps. Confirm that agreement-on-overlaps holds and that gluing fails.

2.3 The obstruction is a cocycle

Given local sections sᵢ that agree pairwise, try to build a global one. Walk a loop U₁ → U₂ → U₃ → U₁, carrying the value along. If you return with what you started, the loop is fine. If not, the discrepancy is a 1-cocycle on the nerve of the cover, and gluing is obstructed exactly when its class in H¹ is nonzero.

In §1.1 the group is ℤ/2, the cocycle is the parity, and its class is Σpᵢ mod 2:

• Σpᵢ = 0 → class is zero → glues, two global sections.
• Σpᵢ = 1 → class is nonzero → no global section.

Exercise 2.3. Compute H¹ of the nerve for (a) three sets pairwise overlapping in a ring, (b) three sets all sharing one common overlap. Predict which cover can host an obstruction before doing any constraint-solving.

2.4 Three obstructions that are one obstruction

This is the payoff of the formalism, and it is worth sitting with.

All three are nonvanishing H¹ on the nerve of a cover. Abramsky and Brandenburger’s sheaf-theoretic treatment of contextuality and the relational database theory of non-serialisable schedules are the same mathematics, and that is a theorem rather than a resemblance.

What this buys you: an intuition transfer that is licensed. When you learn that a non-serialisable schedule shows up as a cycle in the precedence graph, you already know why, and you already know the fix — break the cycle or enlarge the cover.

Exercise 2.4. The precedence graph for transaction scheduling has an edge T→T′ when T must precede T′. Show that acyclicity is equivalent to the existence of a serial order, and identify which cohomological statement that is.

Part III — Impossibility results, sorted by kind

The analogy earns its keep here, because it says the two most-cited impossibility theorems are not the same kind of statement, which the usual pairing of them obscures.

3.1 FLP is not a cohomological obstruction

Fischer, Lynch and Paterson (1985): in an asynchronous system, no deterministic protocol solves consensus if even one process may crash.

The obstruction is not a cycle. The proof is a connectivity argument on the space of system configurations: there is always a bivalent configuration (one from which both decisions are still reachable), and the adversary can keep the system in bivalent configurations forever by delaying one message. Nothing is being glued and nothing goes around a loop. It is closer to a fixed-point statement — the adversary maintains an invariant set — than to a cocycle.

Practical reading: FLP is defeated by changing the model, not the topology. Randomisation (Ben-Or), partial synchrony (Dwork–Lynch–Stockmeyer), or failure detectors all break it, because each removes the adversary’s ability to stall indefinitely. Paxos and Raft live here: they are safe always and live only under synchrony assumptions.

3.2 CAP is a cohomological obstruction

Brewer’s conjecture, Gilbert–Lynch’s theorem: under a network partition you may have consistency or availability, not both.

This one is the sheaf condition failing. A partition literally splits the cover into components with no overlap. Each side can serve reads and writes — local sections exist and are fine. There is no gluing, because there is no overlap on which to check agreement. Choosing C means refusing to produce a local section unless it is known to glue; choosing A means producing local sections you know may not.

Exercise 3.1. State precisely what the cover looks like during a partition, and why “agree on overlaps” is vacuously true. Why does vacuous agreement not imply gluing?

3.3 So the two theorems answer different questions

They are routinely taught together and they are different. FLP says you cannot always finish; CAP says you cannot always be consistent and answer. Conflating them is the single most common confusion in this subject, and the analogy separates them cleanly.

Part IV — Making the obstruction vanish

Three strategies, and each is a recognisable move on the sheaf.

4.1 Enlarge the cover: quorums

A quorum system is a family of subsets any two of which intersect. That intersection is exactly forcing an overlap to exist, so that agreement can be checked.

Majority quorums in a system of n nodes need ⌊n/2⌋+1, and the intersection property is why. Read and write quorums need only satisfy R + W > n, which is a weaker and more useful condition.

Exercise 4.1. Show R + W > n guarantees every read quorum meets every write quorum. Then find a non-majority quorum system (a grid quorum on a √n × √n layout) and compute its quorum size. Why might you prefer it?

4.2 Make every cocycle trivial: CRDTs

A conflict-free replicated data type converges without coordination, and the reason is structural: the state space is a join-semilattice and the merge is its join.

Join is associative, commutative and idempotent. Those three properties are exactly what make the order of merging irrelevant — so carrying a value around a loop returns it unchanged, and every cocycle is trivial by construction.

In sheaf language a CRDT is a presheaf where gluing never fails, because the gluing map cannot depend on the path. That is why CRDTs need no consensus: there is no obstruction to resolve.

The price is expressiveness. Anything requiring a global invariant that is not a semilattice property — “this counter never goes negative”, “this seat is sold once” — cannot be a CRDT, because the invariant is precisely a global section the local data does not determine.

Exercise 4.2. Build a grow-only counter (G-Counter) and prove convergence from the semilattice laws alone. Then show why a general counter supporting decrement needs two G-Counters (PN-Counter), and why that still cannot enforce non-negativity.

Exercise 4.3. Explain, in the vocabulary of this course, why “sell each seat once” is not expressible as a CRDT. What kind of object is the invariant?

4.3 Force a global section: consensus

Paxos, Raft and their relatives do the expensive thing — they manufacture a total order where the system only gave you a partial one.

The structure of Paxos in this language: a proposer tries to establish a global section by getting a quorum to commit to it; the quorum intersection property means any two successful proposals overlap, so the later one can see the earlier and adopt its value. The intersection is doing the gluing.

Exercise 4.4. In Paxos, why must a proposer adopt the highest-numbered value it sees in prepare responses rather than its own? State the answer as a gluing condition.

Exercise 4.5. Raft strengthens Paxos’s leader election so that only a node with an up-to-date log may win. Which part of the sheaf picture does that enforce, and what does it buy in exchange for less flexibility?

Part V — When the restriction maps lie

5.1 Byzantine faults break the sheaf’s assumptions

Everything so far assumes participants report their local sections honestly. A Byzantine node may report different sections to different peers — which means the restriction maps are no longer well defined.

This is a strictly worse problem and the bounds show it. Byzantine agreement needs n ≥ 3f + 1 for f faulty nodes, against n ≥ 2f + 1 for crash faults. The extra factor is the cost of not being able to trust a restriction.

Exercise 5.1. Give the classic three-generals argument for why n = 3, f = 1 is impossible, and identify precisely which sheaf axiom the traitor violates.

5.2 What a blockchain is, structurally

Under this lens: a mechanism for making one global section expensive to produce and cheap to verify, so that competing sections can be ranked rather than reconciled. Proof-of-work prices section-production; the longest-chain rule is a selection procedure among candidate global sections.

Exercise 5.2. Why does this not violate FLP? Identify the model assumption that has been changed.

Part VI — What the analogy does not cover

Stated explicitly, because an analogy that explains everything explains nothing. Test of a good analogy: it should say where it stops.

• Performance. Latency, throughput and tail behaviour are invisible here. The sheaf says whether a global section exists, never how long it takes to find one. Most engineering effort in real systems goes into a question this analogy cannot see.
• Failure detection. Deciding whether a node is dead or slow is an epistemic problem about an asynchronous network, not a gluing problem.
• FLP, as established. Not cohomological; a different kind of obstruction entirely.
• Economic and incentive structure. Byzantine fault tolerance is in scope; Byzantine motivation is not.

Exercise 6.1. For each item above, state what extra structure would have to be added to the formalism to bring it in scope — or argue that it cannot be.

Part VII — Where to go next

Read in this order.

1. Lamport, Time, Clocks, and the Ordering of Events in a Distributed System (1978). The partial order, stated by the person who noticed it. Short.
2. Fischer, Lynch, Paterson (1985). The bivalence argument is worth following line by line; it is the clearest impossibility proof in the subject.
3. Gilbert & Lynch, Brewer’s Conjecture (2002). Short, and notice how much of the confusion around CAP comes from the informal statement rather than this one.
4. Shapiro et al., Conflict-free Replicated Data Types (2011). The semilattice condition is the whole paper.
5. Abramsky & Brandenburger, The Sheaf-Theoretic Structure of Non-Locality and Contextuality (2011). This is where the analogy stops being an analogy. §2.4’s claim is theirs.
6. Abramsky, Barbosa, Kishida, Lal, Mansfield, Contextuality, Cohomology and Paradox (2015). The cohomological obstruction made precise, with database examples alongside the quantum ones.

A project worth doing. Implement §1.1 as a small simulator: n nodes, a ring of parity constraints, each node gossiping with neighbours. Watch it converge when Σpᵢ = 0 and oscillate forever when Σpᵢ = 1 — the cohomology class is visible in the runtime behaviour. Then add a quorum overlay and watch the obstruction resolve.