Module logged_epoch_change 

Epoch-change that survives a restart.

Status: implementation. Space: bounded by membership, plus what the stubborn children hold outstanding — which nothing here retires, so see the departure on Stop below.

Cachin, Guerraoui & Rodrigues, Module 5.6 (LoggedEpochChange) and Algorithm 5.8 (“Logged Leader-Based Epoch-Change”), quoted from the book:

Algorithm 5.8: Logged Leader-Based Epoch-Change
Implements: LoggedEpochChange, instance lec.
Uses:
    StubbornPointToPointLinks, instance sl;
    StubbornBestEffortBroadcast, instance sbeb;
    EventualLeaderDetector, instance Ω.

upon event ⟨ lec, Init ⟩ do
    trusted := ℓ0;
    (startts, start) := (0, ℓ0);
    ts := rank(self) − N;

upon event ⟨ lec, Recovery ⟩ do
    retrieve(startts, start);

upon event ⟨ Ω, Trust | p ⟩ do
    trusted := p;
    if p = self then
        ts := ts + N;
        trigger ⟨ sbeb, Broadcast | [NEWEPOCH, ts] ⟩;

upon event ⟨ sbeb, Deliver | ℓ, [NEWEPOCH, newts] ⟩ do
    if ℓ = trusted ∧ newts > startts then
        (startts, start) := (newts, ℓ);
        store(startts, start);
        trigger ⟨ lec, StartEpoch | startts, start ⟩;
    else
        trigger ⟨ sl, Send | ℓ, [NACK, newts] ⟩;

upon event ⟨ sl, Deliver | p, [NACK, nts] ⟩ such that nts = ts do
    if trusted = self then
        ts := ts + N;
        trigger ⟨ sbeb, Broadcast | [NEWEPOCH, ts] ⟩;

What is durable, and what is not

(startts, start) — the epoch this process has actually entered, and who leads it. Written before StartEpoch is raised, in the handler’s own text, because that indication is what the consensus above acts on: a process that told its consensus to enter epoch 20 and then came back believing it had entered nothing would read an empty state where an accepted value should be.

ts — this process’s own next candidate — is not durable, and the book does not store it. A recovered leader therefore starts climbing again from rank(self), and has to walk back up in steps of N before it can announce a timestamp anybody will accept. That is slow but it is not wrong, and the reason it is not wrong is that startts is durable: every process refuses a timestamp no greater than the epoch it has already entered, so a reused candidate is refused rather than confused with the epoch that first used it. The NACK carries the timestamp it refuses, so each refusal moves the leader up exactly once.

Reusing a candidate is safe for a second reason too: ts ≡ rank(self) (mod N) holds across incarnations, because rank is a function of the membership rather than of anything this process remembers. Two processes still cannot mint the same timestamp, so EC2 — one timestamp names one leader — survives a restart even though ts does not.

Identity, and how durable it has to be

CLAUDE.md: an identifier that crosses the wire or lands in storage outlives the handler that minted it. The sl::SendId and sbeb::BroadcastId counters here mint identifiers that do neither — they name entries in the stubborn children’s own volatile tables, which a crash empties. A restarted process therefore restarts its counters at zero and names nothing that is still live, because nothing is. Their scope is the incarnation, and that is the whole of it.

The timestamp is the identifier that does cross the wire, and it is the one that is durable in the sense that matters: not stored, but re-derived from rank, which does not change.

Departure: a repeat of the epoch already entered is not refused

Algorithm 5.8 answers every NEWEPOCH it does not act on with a NACK. Over the stubborn broadcast the same algorithm’s Uses: line names, that does not terminate, and the loop is tighter than the one crate::epoch_change describes: the leader announces t, every process enters it and writes it down, and then the broadcast — which retransmits until retired, and nothing here retires it — delivers t again. The second delivery fails newts > startts, because startts is now t. So every process refuses the announcement it has just accepted, the leader climbs to t + N, and the cycle restarts one retransmission interval later, for ever. Measured: epoch 380 and still climbing after eight timeouts, with leadership settled and nothing faulty.

crate::epoch_change does not have this, and the reason is the child rather than the algorithm: a best-effort broadcast over perfect links delivers each announcement exactly once, so the repeat never reaches the handler. Moving to a stubborn broadcast — which must not deduplicate, because repeating for ever is what reaches a recovered process — brings it back.

The guard is that a repeat is not a refusal. newts = startts from the leader of the epoch already entered is silence: there is nothing for the leader to climb past, because its announcement was accepted. A NACK is still sent when the sender is not trusted, and when the timestamp is genuinely stale — those are the two cases the book’s else is for.

Departure: each distinct announcement is refused once per peer

The same shape one step earlier, for the announcements that are stale. A NEWEPOCH below startts from a process that is not the leader of the epoch entered is refused; the stubborn broadcast delivers it again next interval; Algorithm 5.8 refuses it again, on a fresh stubborn transmission, and so on for ever. nacked remembers the highest timestamp refused per peer and refuses nothing at or below it. Bounded by membership. The one NACK sent is itself stubborn, so it reaches the leader; a second carries no information the first did not.

Departure: nothing calls Stop

crate::stubborn_broadcast and crate::stubborn_link retransmit until retired, and this module retires nothing, so its space grows with the number of distinct announcements and refusals rather than with the membership — though not, after the two guards above, with time. That is the same unbounded transcription crate::logged_uniform_reliable_broadcast has and for the same reason: retransmitting for ever is what reaches a process that was down when the message was sent, and a recovered process has no way to ask for what it missed.

It is bounded in practice by the thing that bounds the announcements themselves — leadership settling — and the NACK’s timestamp guard is what makes that a finite number rather than a feedback loop. See crate::epoch_change, whose module documentation records what the unguarded form cost.

EC1 [always]     Monotonicity — the timestamps a process starts strictly increase, across
                 restarts as well as within one incarnation, and one timestamp names one leader
EC2 [conditional] Consistency — every correct process eventually starts the same last epoch,
                 provided the leader detector settles

Structs

LoggedEpochChange

A sequence of epochs whose current position survives a restart.

Nack

[NACK, nts] — “I will not start that one”, naming the timestamp refused.

NewEpoch

[NEWEPOCH, ts] — the trusted leader announcing the epoch it wants to start.

Started

(startts, start) — the one metadata value this layer rewrites.

Enums

Ind

Indications to the layer above.

Wire

The wire, multiplexing the three children the book names.

Type Aliases

Cmd

Requests from the layer above.