G08: Cloud systems, partial failure, and consistency

Prerequisites and observable goals#

The central question: what does each participant know?#

In one sequential process, a function either returns or raises. Across a network, a sender may not know whether the receiver ran, committed, crashed, or replied into a broken connection. A distributed design must specify both system state and each participant’s knowledge. Treat timeouts as missing knowledge, not proof of nonexecution.

Cloud infrastructure adds mechanisms for provisioning and isolation, but it does not repeal these facts. A virtual machine virtualizes a hardware environment; containers ordinarily isolate processes while sharing a host kernel. Replicas on one host can share its power, storage, kernel, and networking failure. Zones or regions may change the failure correlation but do not imply absolute independence. Define a failure domain operationally: which components can disappear together under a stated event?

Safety, liveness, and user-visible contracts#

A safety property says something bad never happens: a job is never charged twice under one accepted request ID, or a committed register read does not move backward under a linearizable history. A liveness property says something good eventually happens under stated assumptions: an accepted job eventually completes when a worker and storage remain available and retries continue fairly. Permanent outages make unconditional eventual-completion claims untenable.

Linearizability asks whether each completed operation can be placed at one point between its invocation and response, respecting real-time order of nonoverlapping operations, so that the resulting sequential history satisfies the object’s specification. Eventual convergence, by contrast, does not itself promise a fresh value for each read. “Strong consistency” is too vague until a particular contract is named.

The CAP result concerns the inability to guarantee both its specified consistency and availability properties when partitions are possible in the relevant model. It is not a menu where every practical database permanently selects exactly two of three independent features. During a partition, an operation may wait or fail to preserve a consistency guarantee; a different operation may safely return stale or local data under another contract. State the operation, fault, and guarantee rather than repeating a slogan.

Quorum intersection is a combinatorial fact#

For $N$ replicas, every read set of size $R$ intersects every write set of size $W$ exactly when $R+W>N$. If they were disjoint, their union would have $R+W$ distinct members, impossible when this exceeds $N$. Conversely, when $R+W\le N$, choose disjoint subsets of those sizes. Similarly, two write quorums intersect when $2W>N$.

These facts say sets overlap. They do not specify timestamp generation, failure recovery, conflicting writes, read repair, or which incomplete operations may be visible. Therefore they are ingredients of a protocol proof, not a proof of a complete register implementation.

Worked counterexample: the read that goes backward#

Take three replicas initially holding version 0, value old. A writer sends version 1, value new, but only replica A stores it before the writer stalls. Use read/write quorum sizes two. A first read queries A and B and returns the maximum version, new. After that read completes, a second read queries B and C and returns old.

Every completed read contacted two replicas; $R+W=4>3$ still holds as a set-size statement. The new write never completed a write quorum. If the first read exposes it, a linearization would need to account for the observed new value; a later nonoverlapping read cannot then revert to old in the absence of another write. A proper register protocol needs additional machinery, such as an appropriate write-back phase and versioning rules. This trace is deliberately unsafe; the lab is a counterexample generator, not a recommended quorum storage implementation.

Time moves downward. The drawing shows chosen query sets and observations, not a implemented transport. The ordering of the two reads is essential to the counterexample.

Logical clocks do not create real-time knowledge#

The happened-before relation includes program order within a process, message send before its receive, and transitive closure. Lamport clocks increment at local events and set the receiver to $\max(\text{local},\text{message})+1$. Then $a\to b$ implies $L(a)<L(b)$. The converse is false: two unrelated events may have ordered clock numbers. Adding a process-ID tie-break makes a total order of timestamps but does not prove causality or elapsed time. [G-LAMPORT]

For process P starting at zero, a send gets timestamp 1. Process Q at 4 receives it and moves to 5. Q’s receive is later causally than that send even though its larger value partly reflects unrelated local events. A five-unit logical-clock difference is not five milliseconds. Physical clock synchronization has different assumptions and uncertainties.

Consensus requires a complete protocol#

A replicated log needs agreement about entries and ordering despite failures, not merely a leader-shaped box. Raft separates leader election, log replication, and safety rules, using terms, quorum decisions, and log restrictions. Majority intersection helps, but leadership terms and the rules governing which entries may commit are essential. This chapter does not implement Raft, and its two-quorum enumeration is not evidence that a consensus implementation is correct. [G-RAFT]

Choose an existing, well-understood system when a real service needs consensus. For study, start by stating the assumptions (crash versus Byzantine behavior, storage persistence, message loss/delay, membership changes), tracing an election or failover from an actual protocol, and testing safety in a bounded model. Do not combine convenient fragments from different protocols and assume their proofs compose.

Retries, idempotent effects, and transactional boundaries#

An idempotent mathematical operation satisfies $f(f(x))=f(x)$, but request deduplication is a protocol-level contract. A request ID must bind to a payload; storing only the ID can let a changed request silently inherit an unrelated old answer. The deduplication record and effect must be atomic relative to failures. “Check ID, change state, later save ID” has a crash window that allows repetition.

GP2 uses an outbox row committed with the producer’s job, a consumer receipt committed with the score, and a producer acknowledgement after consumer success. A crash after consumer commit but before acknowledgement causes redelivery, which the consumer detects. This gives at-most-one recorded effect per valid ID/payload under its transaction assumptions and eventual attempts when recovery proceeds. It is not exactly-once network delivery, and it does not survive arbitrary corrupt storage or guarantee that an unrelated external side effect was atomic.

Reliability targets and overload#

Define a service-level indicator from user-visible events, then a target and window. If an availability objective is 99.9% over a 30-day window measured by elapsed time, its error budget is $.001(30)(24)(60)=43.2$ minutes. A request-based indicator has a request-count denominator instead. Percentile latency must state success filtering and workload; excluding failures can make a broken service appear fast. An SLO is an engineering target, not a warranty. [G-SLO]

Under overload, bound queues and retry work. Use backoff with randomness and attempt/deadline limits; otherwise clients can synchronize and amplify failure. Separate transient failures from permanent bad requests. Preserve enough logs, metrics, and trace identifiers to explain which boundary failed, while keeping secrets and personal data out of logs. [G-OVERLOAD]

Independent practice#

F foundation C standard course work T transfer S optional stretch L runnable lab or project. Attempt the complete set before opening its solutions.

Smallest useful hints#

For .01, compare the union size with $N$. For .04, place a crash between the two commits. For .06, an expected counterexample is a successful test of a bad idea, not a failed implementation of a good one.

Complete solutions: G08#

Compare the first step where your work differs. A corrected answer is not yet an independent success.

Open every solution

"""G08: bounded combinatorial checks, not a production storage protocol."""
from dataclasses import dataclass
from itertools import combinations


def disjoint_quorums(n, read_size, write_size):
    if any(type(x) is not int for x in (n,read_size,write_size)):
        raise ValueError("strict integer sizes required")
    if not 1 <= n <= 12 or not 1 <= read_size <= n or not 1 <= write_size <= n:
        raise ValueError("bounded valid quorum sizes required")
    for readers in combinations(range(n),read_size):
        complement = [i for i in range(n) if i not in readers]
        # Enumerate write quorums disjoint from this read set only.
        for writers in combinations(complement,write_size):
            return set(readers),set(writers)
    return None


@dataclass
class LogicalClock:
    value: int = 0

    def __post_init__(self):
        if type(self.value) is not int or self.value < 0:
            raise ValueError("nonnegative integer clock required")

    def tick(self):
        self.value += 1
        return self.value

    def receive(self, timestamp):
        if type(timestamp) is not int or timestamp < 0:
            raise ValueError("nonnegative integer message timestamp required")
        self.value = max(self.value,timestamp)+1
        return self.value


def unsafe_register_trace():
    """Deliberately violates linearizable read behavior; never use as storage."""
    replicas = {name:(0,"old") for name in "ABC"}
    replicas["A"] = (1,"new")  # incomplete write, no write quorum
    first = max(replicas[name] for name in "AB")
    second = max(replicas[name] for name in "BC")
    return first,second


if __name__ == "__main__":
    print(disjoint_quorums(5,2,3))
    print(unsafe_register_trace())

Readiness and continuation#

Advance when you can distinguish a timeout from rollback, quorum overlap from a register protocol, and causal order from a timestamp comparison. Continue with a single complete consensus protocol and its model before attempting an implementation. GP2 applies a smaller transaction/retry argument you can test locally without claiming real distributed deployment.