Semi-Linearizability: Cut Coordination, Keep Invariants

Introduction

Geo-distributed systems often treat every operation as if it needed the same level of coordination. The result is a blunt trade-off: either pay global tail latency and bandwidth for linearizability, or accept broad inconsistency. Semi-linearizability offers a third path — exploit asymmetric (directional) dependencies between operations so that only the few ops that truly need global ordering use consensus, while the common-case ops proceed locally and fast.

In this article I'll explain the core idea behind semi-linearizability, show how the DeMon prototype implements it, walk through a concrete auction example, and give a practical migration checklist you can use to start removing coordination from 50–70% of your writes.

What is semi-linearizability?

Semi-linearizability is a consistency model that distinguishes operations by the ordering relationships they require relative to other operations. Instead of forcing the entire system to provide a single uniform guarantee (e.g., linearizability), semi-linearizability defines three classes of relationships:

• Strong (linearizable) operations: require a global, strongly-ordered execution.
• Weak operations: may execute locally and be asynchronously propagated, provided their causal relationships to strong operations are preserved.
• Semi (or intermediate) operations: a hybrid that may require additional ordering constraints in one direction.

The key observation: many applications have asymmetric dependencies. For example, in auctions a CloseAuction must observe all prior Bids that are relevant, but individual Bid operations don't need to be globally serialized against every other Bid. Semi-linearizability expresses those asymmetries and maps them to different coordination primitives.

How DeMon realizes the model (high level)

DeMon is a prototype that implements semi-linearizability with three primitives:

• Causal broadcast for weak operations (fast, local execution and asynchronous dissemination).
• Targeted consensus (e.g., OmniPaxos) for strong operations to establish a small, totally-ordered log.
• Watermarks (vector-clock style summaries) to bridge weak and strong paths: when a strong op is proposed it attaches a watermark that tells consensus which weak ops must be considered ordered before the strong op.

Flow summary:

1. A replica accepts a weak op, applies it locally, and returns to the client immediately. The op is then causal-broadcast.
2. A strong op is proposed through consensus and carries a watermark summarizing the set of weak ops that must be ordered before it.
3. When a consensus entry is applied, replicas use the watermark to ensure any previously-applied weak ops are reconciled (possibly rolled back and replayed) so the strong ordering is respected.

This lets frequent weak ops be sub-millisecond (DeMon reports up to four orders of magnitude improvement for the common operation in RUBiS), while keeping the strong ops correct and linearizable.

Auctions: a concrete example

Auctions are a simple, practical example that exposes asymmetric dependencies.

• Bid: high-frequency, local update. Bids may be applied locally, then disseminated with causal broadcast. They only need eventual agreement and causal order relative to other ops.
• CloseAuction: rare, decisive operation. CloseAuction must observe and order relevant Bids to decide a winner — it needs strong, consensus-based ordering.

Behavior with semi-linearizability:

• Mark Bid as weak: replicas accept and apply locally, broadcast the operation causally, and return immediately.
• Mark CloseAuction as strong: proposer attaches a watermark (vector clock of known weak-op counts) and proposes CloseAuction in consensus.
• The chosen CloseAuction entry finalizes the auction using the watermark to exclude unknown bids.

Example (pseudo-API annotation):

// annotate intent: weak vs strong
op Bid(user, amount)  -> consistency: weak
op CloseAuction(id)   -> consistency: strong

Example sequence (simplified):
1) Replica A accepts Bid(100) locally and broadcasts it. Replica B accepts Bid(200) locally.
2) Replica C decides CloseAuction and attaches a watermark that does not include A’s recent Bid(300) (because it hasn't seen it).
3) Consensus finalizes CloseAuction with the watermark and the system determines the winner (Bid(200)). If later Bid(300) arrives at a replica that had finalized the close, that bid is ignored or applied after the closed state based on your fail-open/closed policy.

This approach reduces the latency paid by the frequent Bid path while preserving correctness for the rare CloseAuction.

Primitives you need in practice

• Causal broadcast: to deliver weak operations in causal order so replicas converge consistently without synchronous global coordination.
• Watermarks (vector clocks): per-replica counters or vector clocks summarize which weak ops have been observed by a quorum — used by strong ops to anchor ordering.
• Targeted consensus: run consensus only for the strong operations. You don't need to serialize every write into a global log — only those entries that require it.
• Fail-open vs fail-closed policy: decide whether weak ops are allowed in partitioned/isolated conditions (fail-open) or need to be blocked until safety can be guaranteed (fail-closed). Strong ops must be fail-closed to guarantee correctness.

Migration checklist (practical)

1) Audit APIs: list each operation and the invariants it must preserve.
2) Draw dependency edges: which ops must observe which others? Identify asymmetric (directional) dependencies.
3) Annotate ops: mark each op weak / semi / strong. Aim to mark only the minority of ops as strong.
4) Implement local fast-paths: weak ops should be applied locally and asynchronously causal-broadcast.
5) Add targeted consensus: implement consensus for strong ops; attach watermarks summarizing weak-op state when proposing.
6) Reconcile replay/rollback: design how replicas reorder or roll back locally-applied weak ops when a strong op finalizes state.
7) Choose partition policy: decide fail-open vs fail-closed for weak ops; strong ops must remain fail-closed.
8) Test with benchmarks: run realistic workloads (e.g., RUBiS-style mixes) and measure latency and correctness.

Trade-offs and gotchas

• You trade immediate global visibility for lower latency on the weak path. That means some clients may see different intermediate states until weak ops converge.
• Rollback and reorder complexity: when a strong op finalizes with a watermark that excludes some weak ops a replica already applied, you must either rollback and replay or apply compensating logic.
• Correct annotation is critical: mistakenly marking an operation weak when it must be strong can break invariants.

When to use semi-linearizability

• Geo-distributed apps where the common-case operations are simple updates and a few operations need global coordination (auctions, leader elections, platform payments with settle steps).
• Systems where tail latency for frequent operations is a bottleneck and you can accept eventual convergence for those ops.

Closing thoughts

Semi-linearizability reframes consistency from a binary choice into a per-operation design decision. With causal broadcast, watermarks, and targeted consensus you can keep the hot path local and fast while reserving heavy coordination for the rare, critical operations. DeMon’s experiments (RUBiS) show that marking the frequent Bid operation weak reduced latency dramatically, while CloseAuction preserved correctness via consensus. If you're building geo-distributed services, consider annotating operations and exploiting asymmetric dependencies — you may be coordinating much more than you need to.

If you want, I can help you audit a small API and propose a weak/strong annotation map and a minimal implementation sketch for causal broadcast + watermarks.