Geo replication: route by availability, reason about fixed membership

A nearby replica can answer quickly. That does not establish that the answer participates in a safe replication protocol. This module separates three questions: which replicas belong to the key's configuration, which can respond now, and what response sets the protocol requires.

You should already understand the set-intersection argument in replication and quorums. The geo planner adds regional latency and health observations. Its output is a plan, not the execution of a consensus protocol.

Keep two counts with different meanings

A region supplies a name, latency, replica count, and health flag. The input contains the complete configured replica group for one key range. A health failure makes those replicas unavailable; it does not remove them from that configuration.

Count	Includes unhealthy replicas?	Purpose
Configured N	Yes	Prove properties of permitted response sets
Available capacity	No	Decide whether this caller can collect enough responses

All callers must reason about the same configuration. Their current health observations can differ. A legitimate membership change requires a separate protocol; filtering a local health list is not such a protocol.

Derive the intersection conditions

Suppose a completed write obtains W responses and a read obtains R responses from a fixed universe of N replicas. If those sets were disjoint, their union would contain R+W distinct members. Therefore R+W>N guarantees an overlap.

Similarly, two write-response sets must overlap when 2W>N, equivalently W>N/2. The planner requires both properties. Equality is insufficient: with N=6 and R=W=3, sets {a,b,c} and {d,e,f} can be disjoint.

These are cardinality guarantees over any qualifying sets in the configuration. The particular routes selected for one caller may overlap even when the inequalities fail. That accidental overlap does not establish the general guarantee reported by IntersectionSafe.

Intersection alone also does not choose which value a reader returns, order concurrent writes, or establish linearizability. Those need version/ordering rules and a complete protocol. The planner has no state with which to prove them.

Expose the healthy-count mistake with a partition

Configure five replicas: three in west and two in east. A network partition prevents the regions from communicating.

Caller	West healthy?	East healthy?	Available	Configured N
West	yes	no	3	5
East	no	yes	2	5

Choose R=W=2. Each side can collect two local responses. If west replaces N with 3, it finds 2+2>3 and 2*2>3. If east replaces N with 2, it finds both conditions true too. They can then acknowledge conflicting writes using entirely disjoint replicas.

The correct calculation keeps N=5 at both callers. 4>5 is false, so both plans are feasible but return unsafe-quorum. With R=W=3, west can satisfy an intersecting configuration and east lacks read capacity. Losing a member can reduce availability; it must not manufacture a quorum.

For a concrete system's treatment of this distinction, etcd's failure-mode documentation describes how a partition affects progress relative to cluster membership. Our R/W planner is a simpler set calculation, not an implementation of etcd or Raft.

Derive a latency-aware route

Assume requests can go to selected regions in parallel, each region has one fixed response latency, and any requested subset of its replicas can respond at that latency. The route's modeled latency is the slowest selected region. Region names have no performance meaning; they break equal-latency ties deterministically.

Example configuration:

Region	Latency	Replicas	Healthy
north	12	2	yes
south	35	2	yes
west	70	1	no

For R=W=3, configured N=5 and available capacity=4. Sorting responders gives north then south. North contributes two responses, so each route still needs one from south. The selected region list is [north,south], modeled latency 35. Both inequalities hold, so status is ok.

Now let south fail. N remains 5, but only two responses are available. Both routes become infeasible. The contract reports insufficient-read first, with a nil read list and latency -1; the write list is independently infeasible too. A positive-capacity failure must not cause thresholds to be silently lowered.

Why is sorting appropriate? At any latency threshold L, all regions faster than or equal to L are the only possible contributors. If their cumulative capacity is too small, no route finishing by L can work. The first sorted prefix reaching the required count therefore attains the minimum possible maximum latency in this model. It does not minimize region count, price, or correlated failure risk. Those are different optimization objectives.

Map the reasoning onto the API

Keep the steps separate:

1. Sum positive replica counts across the complete configuration.
2. Copy healthy, positive-capacity regions into a separate slice; leave the input unchanged.
3. Sort the copied slice by latency, then name.
4. Build read and write routes independently. Accumulate replica counts, not region counts.
5. Report insufficient-read before insufficient-write when both fail.
6. For two feasible routes, apply the fixed-N inequalities and select ok or unsafe-quorum.

A nonpositive requested count is considered satisfied with an empty route and latency 0 by this exercise's existing convention. This is a route-construction edge case, not a recommendation for zero-response replication. Zero-capacity regions never contribute and should not appear in selected routes.

For feasible positive W, you can compare W > N/2 and R > N-W without forming 2*W or R+W, avoiding unnecessary integer overflow. Building/sorting the region list takes O(n log n) time; the two prefix scans take O(n), with O(n) auxiliary space.

Reconstruction lab

1. Same membership, different health. N=7, R=W=4. One caller can reach four replicas and another only three. Which can get an ok plan?

Model answer

Only the four-replica caller. Both use N=7, so their threshold configuration intersects (8>7). The three-replica caller cannot obtain the required responses and returns insufficient-read. Safety arithmetic does not create capacity.

2. An equal boundary. N=5, R=2, W=3. Both routes are feasible. Does a majority write quorum make the whole plan safe?

Model answer

No. Writes overlap because 2*3>5, but 2+3=5 permits a read set disjoint from a completed write set. Both conditions are required by this planner.

3. A routing objective. Two fast regions have one replica each at latencies 5 and 6. A slower region has two at latency 20. Which route does a two-response request choose, and what tradeoff remains?

Model answer

It chooses the two fast regions and finishes at modeled latency 6. Choosing only the slower region uses fewer regions but finishes at 20. Minimum maximum latency and minimum number of regions are different goals.

4. A correct-looking sample. Why is an all-healthy example unable to expose a healthy-N implementation?

Model answer

Available and configured counts are identical when every replica is healthy. Use the same complete membership with different health flags, including disjoint partitions, to distinguish the two interpretations.

Implement Geo Quorum Route Planner. Before coding, reproduce the partition table and the route's latency lower-bound argument; they justify the two calculations that are easiest to conflate.

Geo replication checkpoint