Managing Update Conflicts in Bayou, a Weakly Connected Replicated Storage System

Weekly Paper Notes — the Seminal Paper of the Week. Area: Distributed Computing.

Authors: Douglas B. Terry, Marvin M. Theimer, Karin Petersen, Alan J. Demers, Mike J. Spreitzer, Carl H. Hauser — Xerox Palo Alto Research Center Published: SOSP ‘95 — Proceedings of the 15th ACM Symposium on Operating Systems Principles, pp. 172–182 DOI: 10.1145/224056.224070

Why the paper still matters

There is a version of distributed systems history in which “eventual consistency” arrives with Dynamo in 2007, gets popularised by the NoSQL wave, and is eventually formalised by CRDTs. That history is missing its first act. In 1995 — twelve years before Dynamo, when “weakly connected” meant a laptop with a dial-up modem and a PDA that synced in a docking cradle — a team at Xerox PARC built a replicated storage system that took the hardest question in eventual consistency seriously and gave a usable engineering answer to it.

The hard question is not “how do replicas converge?” Convergence is comparatively easy: pick a total order on updates, make every replica apply the same updates in that order, and they will agree. The hard question is what should the system do when two updates conflict? — and the honest answer is that the storage system cannot possibly know. Two people booking the same conference room is a conflict. Two people appending to the same log is not. Two people editing different fields of the same record might be either. Last-writer-wins silently destroys data. Manual resolution shoves the problem onto a human who has no context. Locking defeats the entire point of allowing disconnected operation.

Bayou’s answer was to stop trying to solve conflict resolution in the storage layer and instead build a mechanism through which the application supplies the policy — while preserving the property that any replica, in isolation, can resolve any conflict without consulting anyone. That is the contribution, and it is why the paper reads as startlingly modern thirty years on. Every offline-first application you have used — Git, CouchDB, Notion, Linear, Figma’s multiplayer layer, the sync engine in your notes app — is working within a design space that Bayou mapped.

The setup

Bayou targets what the authors call weakly connected environments: mobile devices, laptops, and machines behind unreliable or intermittent links. The design commitments follow directly and are more radical than they sound:

• Any replica accepts any write, at any time, without coordination. There is no quorum, no lock acquisition, no contacting a primary. A disconnected laptop is fully writable.
• Replicas exchange updates pairwise via anti-entropy. Any two servers that can talk will exchange writes and converge with each other. There is no requirement for global connectivity, or for any particular pair of servers to ever meet directly.
• Reads are served locally from whatever the replica currently knows. No blocking on remote state.
• Eventual consistency is guaranteed: if updates stop, all replicas eventually hold identical databases.

Those commitments make conflicts not an edge case but a routine operating condition. The system’s quality is therefore determined almost entirely by how well it handles them. Bayou’s target application — a shared calendar and meeting-room booking system, plus a bibliographic database — was chosen precisely because it has semantically rich conflicts that no generic rule handles well.

The three invariants that make it work

1. Every write carries its own conflict detection and resolution

This is the central idea. A Bayou write is not a mutation. It is a triple:

1. A dependency check — a query plus its expected result.
2. A merge procedure — arbitrary application code, run only if the dependency check fails.
3. The update itself — applied when the check passes.

The dependency check is the piece that makes this more than a version-vector scheme. It runs against the current database state at the replica, every time the write is applied or re-applied. That means it can express arbitrary application-level preconditions — “is room 401 free from 2pm to 3pm?” — rather than merely “has this record changed since I read it?” Optimistic concurrency control based on version numbers detects writes, which is a crude proxy; Bayou detects semantic conflicts, which is what the application actually cares about. Two writes that both touch the calendar record but book non-overlapping slots produce no conflict at all, and Bayou knows that because the application told it how to ask.

The merge procedure is where the policy lives. It is application-supplied code that runs inside the storage system with access to the database, and it must produce some update — it is not allowed to simply fail. In the calendar application, a merge procedure whose room booking has been beaten to the slot will look for another free slot satisfying the requester’s constraints and book that instead, recording the substitution. If it can find nothing acceptable, it writes an entry into an error log that the user will see. The user’s intent — “book me a room, roughly then” — survives, even though the literal update did not.

The requirement that makes this coherent: merge procedures must be deterministic, and they must depend only on the database state and the write’s own contents. Given the same log in the same order, every replica computes the same result. This is what buys convergence without coordination. The paper is candid that this places a real burden on the application programmer — writing a correct merge procedure is harder than writing an update — and discusses the sandboxing needed to keep a runaway merge procedure from wedging the server.

2. Writes are ordered, and the order is stable once committed

Every write receives an accept-stamp — a logical timestamp from the server that first accepted it — paired with that server’s ID for tie-breaking. Writes are ordered by <accept-stamp, server-id>, giving a total order that every replica can compute independently.

But logical timestamps alone are not enough for a usable system, because a write’s position in the order can always be disturbed by the later arrival of an older write from a long-disconnected replica. A user who saw a booking confirmed would have to accept that it might silently un-confirm forever. Bayou’s fix is the tentative/committed distinction, and it is the design’s second stroke of good judgement.

One replica is designated the primary. Its role is deliberately minimal: it assigns monotonically increasing Commit Sequence Numbers (CSNs) to writes as it learns of them, in the order it learns of them. A write with a CSN is committed; a write without one is tentative. Committed writes sort before all tentative writes and are ordered among themselves by CSN. Tentative writes sort by <accept-stamp, server-id>.

The consequence is that the log at every replica has a stable committed prefix and an unstable tentative suffix. Once a write is committed and a replica has learned of it, its position and effects will never change again. The tentative region may be reordered arbitrarily as new writes arrive.

Note what the primary is not. It is not on the write path — writes are accepted by any replica while the primary is unreachable. It is not a consistency authority — it does not validate writes or resolve conflicts. It does not need to be available for the system to make progress. It is purely a serialisation oracle that draws a moving watermark through an order that already exists. This is a much weaker requirement than a primary in primary-copy replication, and it is why Bayou tolerates the primary being partitioned away for extended periods: the system keeps working, it simply stops committing.

3. Rollback and replay is the execution model

Because a newly arrived write may sort before writes already applied, a replica cannot simply apply updates as they arrive. Bayou’s mechanism is honest and direct: undo back to the insertion point, then redo the log forward.

Each server maintains an undo log alongside the write log. When anti-entropy delivers a write that belongs at position $i$ in the tentative region, the server rolls the database back to the state before position $i$, inserts the write, and re-executes every subsequent write in order — re-running each dependency check and, where it now fails, re-running the merge procedure against the new state.

This is the step that makes merge-procedure determinism load-bearing rather than merely tidy. A merge procedure may resolve a conflict one way on first execution and a different way after replay, and that is correct — the resolution is a pure function of the log prefix, so every replica that eventually sees that prefix computes the same thing. What must never happen is two replicas computing differently from identical input.

The obvious cost is that replay is expensive and the log grows without bound. Bayou controls this using exactly the committed prefix from invariant 2: once writes are committed and every replica is known to have them, the log can be truncated and the undo information discarded, since that prefix will never be re-executed. The CSN watermark is simultaneously the user-facing stability guarantee and the garbage-collection frontier — one mechanism doing two jobs, which is usually the sign of a good design.

The algorithm walk-through

Put together, the life of a Bayou write on a disconnected laptop:

1. Acceptance. The user books room 401 for 2pm. The local server accepts the write immediately, stamps it, and appends it to the tentative region. It runs the dependency check against the local database: room 401 appears free, so the update applies. The UI shows the booking as tentative — Bayou surfaces this distinction to users rather than hiding it, so the calendar renders tentative bookings differently from confirmed ones.

2. Anti-entropy. Hours later the laptop reconnects and pairs with another server. They exchange writes. The peer has a write from a colleague, accepted earlier by wall-clock but with a lower accept-stamp, booking room 401 at 2pm.

3. Rollback. The colleague’s write sorts before the user’s. The laptop rolls its database back past the user’s booking, inserts the colleague’s write, and replays.

4. Re-resolution. On replay, the user’s dependency check now fails — room 401 is occupied. Its merge procedure runs, finds room 403 free at 2pm, and books that instead. The user’s calendar entry updates itself. No data was lost; no human was asked to adjudicate; no lock was ever held.

5. Commitment. Eventually anti-entropy propagates both writes to the primary, which assigns CSNs. The next time the laptop syncs, it learns the commit order, the writes move into the stable prefix, and the UI promotes them from tentative to confirmed. From this point the booking of room 403 is permanent.

The property worth pausing on: at no point did any replica need to contact any other replica at the moment of decision. Every choice was made locally, from local state, using logic that travelled with the data.

Why this design has outlasted everything around it

Bayou itself was a research system. It shipped no product, and PARC’s calendar application was never a commercial concern. Yet almost every element of it is now standard equipment somewhere in the industry, usually without attribution.

The tentative/committed distinction is now table stakes for user-facing sync. Every collaborative editor that renders your own edits immediately and reconciles them a moment later is running Bayou’s model. The insight that a replicated system should expose provisionality to the user rather than pretend to certainty it doesn’t have was, in 1995, contrarian; today it’s just good UX, and the systems that ignore it produce the phantom-edit bugs users find so maddening.

Application-specific conflict resolution won the argument. Dynamo’s shopping cart merge — the canonical example of application-level reconciliation, where the union of cart contents is taken because losing an item is worse than resurrecting a deleted one — is a Bayou merge procedure with a different name. CouchDB, Riak, Git’s merge drivers, and the whole _conflicts surface of offline-first databases are working in Bayou’s frame: the store detects, the application decides.

CRDTs are the natural refinement, not the replacement. Where Bayou lets you write arbitrary deterministic merge logic, CRDTs constrain you to operations that are commutative, associative, and idempotent — buying away the need for rollback-and-replay entirely, since order stops mattering. That’s a genuine advance in elegance and efficiency. But it’s also a genuine restriction: you must express your problem in the algebra. Bayou’s more permissive model still covers cases CRDTs handle awkwardly, which is why “run the application’s resolution function on replay” remains a live design in production sync engines. Reading Bayou first makes it much clearer what CRDTs are actually buying.

The minimal-primary pattern recurs constantly. A designated node whose only job is to assign a total order, which is off the critical path and whose unavailability degrades stability guarantees rather than availability, describes Bayou’s primary — and also describes Kafka’s partition leader for ordering purposes, the sequencer in Calvin and in a dozen deterministic-database designs, and the commit-timestamp assignment in various log-structured replication schemes. Separating ordering authority from write availability is one of the most reusable moves in the field, and Bayou stated it cleanly.

Session guarantees came from the same group and the same system. The companion work on read-your-writes, monotonic reads, writes-follow-reads, and monotonic writes — the vocabulary in which we still discuss consistency for replicated stores — was developed for Bayou. That taxonomy alone has outlived most of the systems built on it.

There is also a lesson in what Bayou got wrong, or at least what limited it. Requiring application programmers to write correct, deterministic, side-effect-free merge procedures — and to reason about them being re-executed unpredictably many times against states they never anticipated — is a heavy cognitive load. This is precisely the burden CRDTs remove, and it is a substantial part of why the CRDT formulation eventually got more industrial traction than the general merge-procedure formulation. Bayou identified the right problem and gave a fully general answer; the field then spent twenty-five years finding the special cases where the answer could be made automatic.

That trajectory — general mechanism first, then the constrained-but-automatic version — is a familiar shape. It is worth reading the paper that started it.

Read alongside

• “Session Guarantees for Weakly Consistent Replicated Data” (Terry, Demers, Petersen, Spreitzer, Theimer, Welch, PDIS 1994) — the companion Bayou paper that defined read-your-writes and friends.
• “Flexible Update Propagation for Weakly Consistent Replication” (Petersen, Spreitzer, Terry, Theimer, Demers, SOSP 1997) — the anti-entropy protocol underlying Bayou, treated in full detail.
• “Dynamo: Amazon’s Highly Available Key-value Store” (DeCandia et al., SOSP 2007) — covered in our 6 June digest; Bayou’s ideas at production scale, with vector clocks and syntactic reconciliation.
• “A Comprehensive Study of Convergent and Commutative Replicated Data Types” (Shapiro, Preguiça, Baquero, Zawirski, 2011) — the CRDT formalisation that constrains Bayou’s merge procedures into an algebra.
• “Epidemic Algorithms for Replicated Database Maintenance” (Demers et al., PODC 1987) — the earlier PARC work on anti-entropy and rumour-mongering that Bayou’s propagation layer builds on.
• “Time, Clocks, and the Ordering of Events in a Distributed System” (Lamport, 1978) — our 16 May seminal pick; the logical-clock machinery behind accept-stamps.

Links

📄 ACM Digital Library — DOI 10.1145/224056.224070

Part of the Weekly CS Paper Digest series. Diagram is original work. Written from a close read of the SOSP ‘95 paper.