Module logged_uniform_total_order_broadcast 

Logged uniform total-order broadcast.

Status: transcription. Space: unbounded — unordered, delivered and the family of consensus instances all grow with the number of entries handled, and delivered and proposals grow in stable storage as well. That is the page. See docs/bounded-space.md.

Cachin, Guerraoui & Rodrigues, Module LoggedUniformTotalOrderBroadcast and Algorithm 6.12, p. 327, quoted from the book:

Algorithm 6.12: Logged Uniform Total-Order Broadcast
Implements: LoggedUniformTotalOrderBroadcast, instance lutob.
Uses:
    LoggedUniformReliableBroadcast, instance lurb;
    LoggedUniformConsensus (multiple instances).

upon event ⟨ lutob, Init ⟩ do
    unordered := ∅;
    delivered := [];
    round := 1;
    recovering := FALSE;
    wait := FALSE;
    forall r > 0 do proposals[r] := ⊥;

upon event ⟨ Recovery ⟩ do
    unordered := ∅;
    delivered := [];
    round := 1;
    recovering := TRUE;
    wait := FALSE;
    retrieve(proposals);
    if proposals[1] ≠ ⊥ then
        trigger ⟨ luc.1, Propose | proposals[1] ⟩;

upon event ⟨ lutob, Broadcast | m ⟩ do
    trigger ⟨ lurb, Broadcast | m ⟩;

upon event ⟨ lurb, Deliver | lurbdelivered ⟩ do
    unordered := unordered ∪ lurbdelivered;

upon unordered \ delivered ≠ ∅ ∧ wait = FALSE ∧ recovering = FALSE do
    wait := TRUE;
    Initialize a new instance luc.round of logged uniform consensus;
    proposals[round] := unordered \ delivered;
    store(proposals);
    trigger ⟨ luc.round, Propose | proposals[round] ⟩;

upon event ⟨ luc.r, Decide | decided ⟩ such that r = round do
    forall (s, m) ∈ sort(decided) do     // by the order in the resulting sorted list
        append(delivered, (s, m));
    store(delivered);
    round := round + 1;
    if recovering = TRUE then
        if proposals[round] ≠ ⊥ then
            trigger ⟨ luc.round, Propose | proposals[round] ⟩;
        else
            recovering := FALSE;
    else
        wait := FALSE;
    trigger ⟨ lutob, Deliver | delivered ⟩;

The pair to crate::consensus_based_total_order_broadcast, and held to the same suite. What differs is exactly one thing: the ordered sequence survives a restart. Everything else — one consensus instance per round, propose the unordered set, sort what is decided — is the same shape, which is what makes the comparison worth having.

Why the recovery is not simply “read it back”. A process that proposed for a round and then forgot would, on recovering, propose something different for the same round — and a uniform consensus that has already decided cannot accommodate it. So proposals[r] is durable before the proposal is visible to anyone, and recovery re-proposes what was recorded, round by round, until it reaches one it never proposed for. That is what recovering is counting through.

Departures from the page

• A read, as the port requires. See crate::total_order_log.

• Consensus instances are a family, and the conditional event handler is discharged here. Both as in the crash-stop member, and for the same reasons; that module’s header states them. Unlike that member, this one runs over a consensus assuming no synchrony, so processes can genuinely drift and the family is doing work rather than standing on faithfulness alone.

• delivered and proposals are appended, not rewritten. The page writes append(delivered, (s, m)); store(delivered) and store(proposals) — rewriting a whole growing structure on every change, which costs O(n²) bytes over a run. This repository’s storage interface splits the two cases so the choice is visible in the types, and docs/bounded-space.md records both logged modules having had exactly this defect and losing it. So both go into the appended sequence, one entry each, and recovery replays them.

• Consensus instances are re-created here, not by a runtime. The page says so outright: “During the recovery operation after a crash, the total-order algorithm runs again through all rounds executed before the crash and executes the same consensus instances once more. (We assume that the runtime environment re-instantiates all instances of consensus that had been dynamically initialized before the crash.)” There is no such runtime here — a crash rebuilds a process from its constructor and nothing else survives but storage — so on_recovery re-creates every instance the durable record names and runs each one’s own recovery, all of them before any decision is acted on: a decided instance announces its decision again from its record, and an undecided one must have read its state back before recovery re-proposes into it. The same shape of departure as the conditional event handler: a facility the book assumes, discharged in the module.

• The decided prefix is replayed from the record, not re-decided. The page rebuilds delivered by running every round again, which is what its runtime’s re-instantiated instances are for. The appended Record::Ordered entries already hold the sequence in order, so recovery replays them directly and the walk over re-announced decisions advances round without appending or announcing anything twice — the same guard that makes duplicate decisions harmless in a live run makes the replay idempotent. Each replayed entry is announced again, once, for the reason crate::logged_leader_driven_consensus gives for re-announcing a decision: the layer above may have crashed with this process and never seen the first indication. Positions make the re-announcement idempotent for a client.

• The child that appends is composed through a sequence slot. logged_uniform_reliable_ broadcast keeps an appended record of its own, and until this module nothing composed over a child that appends — store.rs said so, and said what the missing half would be. This is its second consumer, and [recon_core::SeqSlot] is what that paragraph described. Parent and child append into one sequence, so the order between their entries is real rather than invented at recovery.

Structs

Durable

This protocol’s rewritten metadata, and its children’s inside it.

LoggedUniformTotalOrderBroadcast

A totally ordered log whose sequence survives a restart.

Enums

Cmd

Requests from the layer above.

Ind

Indications to the layer above.

Record

What this protocol appends. One sequence, carrying its own entries and its child’s.

Wire

This layer’s messages: the broadcast’s, and a consensus instance’s stamped with its round.

Type Aliases

Consensus

The consensus one round runs. Not a type parameter, for the reason the crash-stop member gives.