Expand description
Logged uniform reliable broadcast.
Cachin, Guerraoui & Rodrigues, Module 3.6 and Algorithm 3.8 (“Logged Majority-Ack Uniform Reliable Broadcast”).
Status: transcription. Space: unbounded — and on disk. Write cost: a fixed number of appends
per message. pending and delivered grow with every message handled, as in
crate::majority_ack_uniform_reliable_broadcast, except that here they are written down.
Each is recorded by appending one entry, so the cost of recording a message does not depend on
how many preceded it; the record itself is still unbounded. See docs/bounded-space.md.
Assumption: a correct majority, N > 2f — where in this model a correct process is one
that always recovers from its crashes, and what it knows after recovering is what it wrote.
upon event ⟨ lurb, Init ⟩ do
delivered := ∅; pending := ∅;
forall m do ack[m] := ∅;
store(pending, delivered);
upon event ⟨ lurb, Recovery ⟩ do
retrieve(pending, delivered);
trigger ⟨ lurb, Deliver | delivered ⟩;
forall (s, m) ∈ pending do
trigger ⟨ sbeb, Broadcast | [DATA, s, m] ⟩;
upon event ⟨ lurb, Broadcast | m ⟩ do
pending := pending ∪ {(self, m)};
store(pending);
trigger ⟨ sbeb, Broadcast | [DATA, self, m] ⟩;
upon event ⟨ sbeb, Deliver | p, [DATA, s, m] ⟩ do
if (s, m) ∉ pending then
pending := pending ∪ {(s, m)};
store(pending);
trigger ⟨ sbeb, Broadcast | [DATA, s, m] ⟩;
if p ∉ ack[m] then
ack[m] := ack[m] ∪ {p};
if #(ack[m]) > N/2 ∧ (s, m) ∉ delivered then
delivered := delivered ∪ {(s, m)};
store(delivered);
trigger ⟨ lurb, Deliver | delivered ⟩;§ack is deliberately not durable
The book: “Variable ack is not logged because it will be reconstructed upon recovery.”
Getting this wrong in the direction of storing more looks safer and is worse — it would cost a
write per acknowledgement to save work that retransmission does anyway, and would make the
durable state grow with traffic rather than with messages.
What rebuilds it is the recovery clause: a recovered process re-broadcasts everything still pending, and acknowledgements accumulate as the answers arrive. The stubborn broadcast beneath never stops retransmitting, so a process that was down when something was sent gets it anyway.
§Why the child is stubborn broadcast and not the logged link
The book’s logged abstractions do not stack: Algorithm 2.3 is over stubborn links, and this one is over stubborn broadcast. Each keeps its own log. A perfect link’s deduplication is volatile, so after a restart it would re-deliver anyway — the deduplication buys nothing a logged layer above does not already do for itself, and it is the retransmission a recovered process needs. Deduplicating beneath would suppress exactly that.
§Departures from the page
⟨ Init ⟩is here and performs the book’s initial store, ascrate::logged_linkdoes.pendinganddeliveredshare one appended sequence, distinguished by a tag on each entry, rather than the book’s two stores. Recovery replays the sequence and rebuilds both.- Messages are keyed by an identifier carrying the originator and a sequence number rather than by content, so identical content broadcast twice is delivered twice.
- The sequence number is therefore as durable as the log it keys, and recovery recomputes it rather than resuming from zero. See the note below; the obligation is part of the departure.
- No
Stop: retransmission for ever is what reaches a recovered process.
§The sequence number survives a crash, without being written
Content-keyed identity, as the book has it, needs nothing restored: a payload names itself. An
id-keyed departure owes the counter the same durability as the set it keys, or a recovered
process re-mints (me, 1) for something new and two distinct payloads collide under one
identifier — last-write-wins in pending, acks for the old counting toward the new, at most
one of the two ever delivered locally, and different processes log-delivering different
payloads under the same id. No-creation, validity and uniform agreement all fail, in the one
module whose model expects a recovered process to keep working.
Recovery recomputes it as the greatest seq over replayed records originating here, which is
sound because every own broadcast appends its Pending record in the handler that emits it:
a torn write discards that handler’s sends, so no broadcast escapes without a record. The
alternative — the counter in Meta — is also correct and costs a metadata write per
broadcast, which is what buys nothing here.
Structs§
- Logged
- What survives a crash: what has been seen, and what has been log-delivered.
- Logged
Uniform Reliable Broadcast - Uniform agreement over log-delivery, in the fail-recovery model.