CAP Theorem and Consistency Models

package main

import (
	"fmt"
	"sort"
)

// Three replicas of one key, x = 1. A client writes x = 2 and reads it straight back.
// rtt is the round trip to each replica in ms; lag is how far behind its replication queue
// runs. C sits in another region and is behind.
type replica struct {
	name     string
	rtt, lag int
}

var replicas = []replica{{"A", 4, 0}, {"B", 20, 0}, {"C", 80, 400}}

// has: the moment replica r holds x = 2 (the write reaches it after half a round trip, then waits
// in its queue). ack: when the client hears back from it.
func has(r replica) int { return r.rtt/2 + r.lag }
func ack(r replica) int { return r.rtt + r.lag }

// subsets returns every way to pick k of the n replicas.
func subsets(k int) [][]replica {
	var out [][]replica
	n := len(replicas)
	for mask := 0; mask < 1<<n; mask++ {
		var s []replica
		for i := 0; i < n; i++ {
			if mask&(1<<i) != 0 {
				s = append(s, replicas[i])
			}
		}
		if len(s) == k {
			out = append(out, s)
		}
	}
	return out
}

// quorum: the write waits for w acks; the read then asks r replicas and keeps the newest value.
func quorum(w, r int) {
	acks := []int{}
	for _, rep := range replicas {
		acks = append(acks, ack(rep))
	}
	sort.Ints(acks)
	wrote := acks[w-1] // the w-th fastest ack

	stale, worst, total := 0, 0, 0
	for _, s := range subsets(r) {
		total++
		fresh, slowest := false, 0
		for _, rep := range s {
			if wrote+rep.rtt/2 >= has(rep) { // the read reaches it after it got the write
				fresh = true
			}
			slowest = max(slowest, rep.rtt)
		}
		if !fresh {
			stale++
		}
		worst = max(worst, slowest)
	}
	fmt.Printf("  W=%d R=%d (W+R=%d): write %3d ms, read up to %2d ms, stale reads: %d of %d\n", w, r, w+r, wrote, worst, stale, total)
}

func main() {
	fmt.Println("3 replicas: A 4 ms away, B 20 ms, C 80 ms and 400 ms behind; write x=2, read it back")
	for _, wr := range [][2]int{{1, 1}, {2, 1}, {2, 2}, {1, 3}, {3, 1}} {
		quorum(wr[0], wr[1])
	}

	// A network partition cuts C off from A and B.
	fmt.Println("partition: C can't reach A or B")
	reachable := 2
	for _, w := range []int{3, 2} {
		if w > reachable {
			fmt.Printf("  W=%d: write refused (needs %d acks, %d reachable): consistent, not available\n", w, w, reachable)
		} else {
			fmt.Printf("  W=%d: write accepted by A and B; R=2 reads still see it\n", w)
		}
	}
	// If both sides keep taking writes (W=1), they drift apart.
	sideAB, sideC := 2, 3 // a client near A writes x=2, a client near C writes x=3
	fmt.Printf("  W=1 on both sides: A,B say x=%d, C says x=%d: available, but they disagree until the partition heals\n", sideAB, sideC)
}

# Three replicas of one key, x = 1. A client writes x = 2 and reads it straight back.
# rtt is the round trip to each replica in ms; lag is how far behind its replication queue
# runs. C sits in another region and is behind.
from typing import NamedTuple


class Replica(NamedTuple):
    name: str
    rtt: int
    lag: int


REPLICAS = [Replica("A", 4, 0), Replica("B", 20, 0), Replica("C", 80, 400)]


def has(r: Replica) -> int:
    """The moment r holds x = 2 (half a round trip, then its queue)."""
    return r.rtt // 2 + r.lag


def ack(r: Replica) -> int:
    """When the client hears back from r."""
    return r.rtt + r.lag


def subsets(k: int) -> list[list[Replica]]:
    """Every way to pick k of the n replicas."""
    n = len(REPLICAS)
    out = []
    for mask in range(1 << n):
        s = [REPLICAS[i] for i in range(n) if mask & (1 << i)]
        if len(s) == k:
            out.append(s)
    return out


def quorum(w: int, r: int) -> None:
    """The write waits for w acks; the read then asks r replicas and keeps the newest value."""
    wrote = sorted(ack(rep) for rep in REPLICAS)[w - 1]  # the w-th fastest ack
    stale = worst = total = 0
    for s in subsets(r):
        total += 1
        fresh = any(wrote + rep.rtt // 2 >= has(rep) for rep in s)  # the read reaches it after it got the write
        if not fresh:
            stale += 1
        worst = max(worst, max(rep.rtt for rep in s))
    print(f"  W={w} R={r} (W+R={w + r}): write {wrote:3} ms, read up to {worst:2} ms, stale reads: {stale} of {total}")


print("3 replicas: A 4 ms away, B 20 ms, C 80 ms and 400 ms behind; write x=2, read it back")
for w, r in [(1, 1), (2, 1), (2, 2), (1, 3), (3, 1)]:
    quorum(w, r)

# A network partition cuts C off from A and B.
print("partition: C can't reach A or B")
reachable = 2
for w in (3, 2):
    if w > reachable:
        print(f"  W={w}: write refused (needs {w} acks, {reachable} reachable): consistent, not available")
    else:
        print(f"  W={w}: write accepted by A and B; R=2 reads still see it")
# If both sides keep taking writes (W=1), they drift apart.
side_ab, side_c = 2, 3  # a client near A writes x=2, a client near C writes x=3
print(f"  W=1 on both sides: A,B say x={side_ab}, C says x={side_c}: available, but they disagree until the partition heals")

// Three replicas of one key, x = 1. A client writes x = 2 and reads it straight back.
// rtt is the round trip to each replica in ms; lag is how far behind its replication queue
// runs. C sits in another region and is behind.
type Replica = { name: string; rtt: number; lag: number };

const REPLICAS: Replica[] = [
  { name: "A", rtt: 4, lag: 0 },
  { name: "B", rtt: 20, lag: 0 },
  { name: "C", rtt: 80, lag: 400 },
];

/** The moment r holds x = 2 (half a round trip, then its queue). */
const has = (r: Replica) => Math.floor(r.rtt / 2) + r.lag;
/** When the client hears back from r. */
const ack = (r: Replica) => r.rtt + r.lag;

/** Every way to pick k of the n replicas. */
function subsets(k: number): Replica[][] {
  const out: Replica[][] = [];
  const n = REPLICAS.length;
  for (let mask = 0; mask < 1 << n; mask++) {
    const s = REPLICAS.filter((_, i) => mask & (1 << i));
    if (s.length === k) out.push(s);
  }
  return out;
}

/** The write waits for w acks; the read then asks r replicas and keeps the newest value. */
function quorum(w: number, r: number) {
  const wrote = REPLICAS.map(ack).sort((a, b) => a - b)[w - 1]!; // the w-th fastest ack
  let stale = 0;
  let worst = 0;
  let total = 0;
  for (const s of subsets(r)) {
    total++;
    const fresh = s.some((rep) => wrote + Math.floor(rep.rtt / 2) >= has(rep)); // the read reaches it after it got the write
    if (!fresh) stale++;
    worst = Math.max(worst, ...s.map((rep) => rep.rtt));
  }
  console.log(`  W=${w} R=${r} (W+R=${w + r}): write ${String(wrote).padStart(3)} ms, read up to ${String(worst).padStart(2)} ms, stale reads: ${stale} of ${total}`);
}

console.log("3 replicas: A 4 ms away, B 20 ms, C 80 ms and 400 ms behind; write x=2, read it back");
for (const [w, r] of [[1, 1], [2, 1], [2, 2], [1, 3], [3, 1]] as const) quorum(w, r);

// A network partition cuts C off from A and B.
console.log("partition: C can't reach A or B");
const reachable = 2;
for (const w of [3, 2]) {
  if (w > reachable) console.log(`  W=${w}: write refused (needs ${w} acks, ${reachable} reachable): consistent, not available`);
  else console.log(`  W=${w}: write accepted by A and B; R=2 reads still see it`);
}
// If both sides keep taking writes (W=1), they drift apart.
const [sideAB, sideC] = [2, 3]; // a client near A writes x=2, a client near C writes x=3
console.log(`  W=1 on both sides: A,B say x=${sideAB}, C says x=${sideC}: available, but they disagree until the partition heals`);

// Three replicas of one key, x = 1. A client writes x = 2 and reads it straight back.
// rtt is the round trip to each replica in ms; lag is how far behind its replication queue
// runs. C sits in another region and is behind.
#[derive(Clone, Copy)]
struct Replica {
    rtt: i32,
    lag: i32,
}

const REPLICAS: [Replica; 3] = [Replica { rtt: 4, lag: 0 }, Replica { rtt: 20, lag: 0 }, Replica { rtt: 80, lag: 400 }];

/// The moment r holds x = 2 (half a round trip, then its queue).
fn has(r: Replica) -> i32 {
    r.rtt / 2 + r.lag
}

/// When the client hears back from r.
fn ack(r: Replica) -> i32 {
    r.rtt + r.lag
}

/// Every way to pick k of the n replicas.
fn subsets(k: usize) -> Vec<Vec<Replica>> {
    let n = REPLICAS.len();
    (0..1 << n)
        .map(|mask: usize| (0..n).filter(|i| mask & (1 << i) != 0).map(|i| REPLICAS[i]).collect::<Vec<_>>())
        .filter(|s| s.len() == k)
        .collect()
}

/// The write waits for w acks; the read then asks r replicas and keeps the newest value.
fn quorum(w: usize, r: usize) {
    let mut acks: Vec<i32> = REPLICAS.iter().map(|&rep| ack(rep)).collect();
    acks.sort();
    let wrote = acks[w - 1]; // the w-th fastest ack
    let (mut stale, mut worst, mut total) = (0, 0, 0);
    for s in subsets(r) {
        total += 1;
        let fresh = s.iter().any(|&rep| wrote + rep.rtt / 2 >= has(rep)); // the read reaches it after it got the write
        if !fresh {
            stale += 1;
        }
        worst = worst.max(s.iter().map(|rep| rep.rtt).max().unwrap());
    }
    println!("  W={w} R={r} (W+R={}): write {wrote:3} ms, read up to {worst:2} ms, stale reads: {stale} of {total}", w + r);
}

fn main() {
    println!("3 replicas: A 4 ms away, B 20 ms, C 80 ms and 400 ms behind; write x=2, read it back");
    for (w, r) in [(1, 1), (2, 1), (2, 2), (1, 3), (3, 1)] {
        quorum(w, r);
    }

    // A network partition cuts C off from A and B.
    println!("partition: C can't reach A or B");
    let reachable = 2;
    for w in [3, 2] {
        if w > reachable {
            println!("  W={w}: write refused (needs {w} acks, {reachable} reachable): consistent, not available");
        } else {
            println!("  W={w}: write accepted by A and B; R=2 reads still see it");
        }
    }
    // If both sides keep taking writes (W=1), they drift apart.
    let (side_ab, side_c) = (2, 3); // a client near A writes x=2, a client near C writes x=3
    println!("  W=1 on both sides: A,B say x={side_ab}, C says x={side_c}: available, but they disagree until the partition heals");
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

// Three replicas of one key, x = 1. A client writes x = 2 and reads it straight back.
// rtt is the round trip to each replica in ms; lag is how far behind its replication queue
// runs. C sits in another region and is behind.
public class Main {
    record Replica(String name, int rtt, int lag) {
        /** The moment this replica holds x = 2 (half a round trip, then its queue). */
        int has() { return rtt / 2 + lag; }
        /** When the client hears back from it. */
        int ack() { return rtt + lag; }
    }

    static final List<Replica> REPLICAS = List.of(new Replica("A", 4, 0), new Replica("B", 20, 0), new Replica("C", 80, 400));

    /** Every way to pick k of the n replicas. */
    static List<List<Replica>> subsets(int k) {
        List<List<Replica>> out = new ArrayList<>();
        int n = REPLICAS.size();
        for (int mask = 0; mask < 1 << n; mask++) {
            List<Replica> s = new ArrayList<>();
            for (int i = 0; i < n; i++) if ((mask & (1 << i)) != 0) s.add(REPLICAS.get(i));
            if (s.size() == k) out.add(s);
        }
        return out;
    }

    /** The write waits for w acks; the read then asks r replicas and keeps the newest value. */
    static void quorum(int w, int r) {
        int[] acks = REPLICAS.stream().mapToInt(Replica::ack).toArray();
        Arrays.sort(acks);
        int wrote = acks[w - 1]; // the w-th fastest ack
        int stale = 0, worst = 0, total = 0;
        for (List<Replica> s : subsets(r)) {
            total++;
            boolean fresh = false;
            for (Replica rep : s) {
                if (wrote + rep.rtt() / 2 >= rep.has()) fresh = true; // the read reaches it after it got the write
                worst = Math.max(worst, rep.rtt());
            }
            if (!fresh) stale++;
        }
        System.out.printf("  W=%d R=%d (W+R=%d): write %3d ms, read up to %2d ms, stale reads: %d of %d%n", w, r, w + r, wrote, worst, stale, total);
    }

    public static void main(String[] args) {
        System.out.println("3 replicas: A 4 ms away, B 20 ms, C 80 ms and 400 ms behind; write x=2, read it back");
        int[][] combos = {{1, 1}, {2, 1}, {2, 2}, {1, 3}, {3, 1}};
        for (int[] wr : combos) quorum(wr[0], wr[1]);

        // A network partition cuts C off from A and B.
        System.out.println("partition: C can't reach A or B");
        int reachable = 2;
        for (int w : new int[] {3, 2}) {
            if (w > reachable) System.out.printf("  W=%d: write refused (needs %d acks, %d reachable): consistent, not available%n", w, w, reachable);
            else System.out.printf("  W=%d: write accepted by A and B; R=2 reads still see it%n", w);
        }
        // If both sides keep taking writes (W=1), they drift apart.
        int sideAB = 2, sideC = 3; // a client near A writes x=2, a client near C writes x=3
        System.out.printf("  W=1 on both sides: A,B say x=%d, C says x=%d: available, but they disagree until the partition heals%n", sideAB, sideC);
    }
}

// Three replicas of one key, x = 1. A client writes x = 2 and reads it straight back.
// rtt is the round trip to each replica in ms; lag is how far behind its replication queue
// runs. C sits in another region and is behind.
#include <algorithm>
#include <cstdio>
#include <utility>
#include <vector>

struct Replica {
    const char* name;
    int rtt, lag;
    int has() const { return rtt / 2 + lag; }  // the moment it holds x = 2 (half a round trip, then its queue)
    int ack() const { return rtt + lag; }      // when the client hears back from it
};

const std::vector<Replica> kReplicas = {{"A", 4, 0}, {"B", 20, 0}, {"C", 80, 400}};

// Every way to pick k of the n replicas.
std::vector<std::vector<Replica>> subsets(size_t k) {
    std::vector<std::vector<Replica>> out;
    size_t n = kReplicas.size();
    for (size_t mask = 0; mask < (1u << n); mask++) {
        std::vector<Replica> s;
        for (size_t i = 0; i < n; i++)
            if (mask & (1u << i)) s.push_back(kReplicas[i]);
        if (s.size() == k) out.push_back(s);
    }
    return out;
}

// The write waits for w acks; the read then asks r replicas and keeps the newest value.
void quorum(int w, int r) {
    std::vector<int> acks;
    for (const auto& rep : kReplicas) acks.push_back(rep.ack());
    std::sort(acks.begin(), acks.end());
    int wrote = acks[w - 1];  // the w-th fastest ack
    int stale = 0, worst = 0, total = 0;
    for (const auto& s : subsets(r)) {
        total++;
        bool fresh = false;
        for (const auto& rep : s) {
            if (wrote + rep.rtt / 2 >= rep.has()) fresh = true;  // the read reaches it after it got the write
            worst = std::max(worst, rep.rtt);
        }
        if (!fresh) stale++;
    }
    std::printf("  W=%d R=%d (W+R=%d): write %3d ms, read up to %2d ms, stale reads: %d of %d\n", w, r, w + r, wrote, worst, stale, total);
}

int main() {
    std::printf("3 replicas: A 4 ms away, B 20 ms, C 80 ms and 400 ms behind; write x=2, read it back\n");
    for (auto [w, r] : std::vector<std::pair<int, int>>{{1, 1}, {2, 1}, {2, 2}, {1, 3}, {3, 1}}) quorum(w, r);

    // A network partition cuts C off from A and B.
    std::printf("partition: C can't reach A or B\n");
    int reachable = 2;
    for (int w : {3, 2}) {
        if (w > reachable)
            std::printf("  W=%d: write refused (needs %d acks, %d reachable): consistent, not available\n", w, w, reachable);
        else
            std::printf("  W=%d: write accepted by A and B; R=2 reads still see it\n", w);
    }
    // If both sides keep taking writes (W=1), they drift apart.
    int sideAB = 2, sideC = 3;  // a client near A writes x=2, a client near C writes x=3
    std::printf("  W=1 on both sides: A,B say x=%d, C says x=%d: available, but they disagree until the partition heals\n", sideAB, sideC);
}