arXiv CSopen access

Consensus as Collapse Policy: Communication Evidence, Horizons, and Prefix Decisions

Consensus as Collapse Policy: Communication Evidence, Horizons, and Prefix Decisions Tomislav Grospić [email protected]

July 2026

arXiv:2607.10152v1 [cs.DC] 11 Jul 2026

Abstract Consensus protocols are usually specified by their terminal artifact: a decided value, replicated log, or finalized prefix. This output-first view hides the communication-derived evidence that makes such artifacts safe: messages, votes, certificates, causal dependencies, equivocation evidence, timeouts, and local views. This paper makes that carrier explicit. We model distributed execution as an order-2 evidence state induced by communication and read classical consensus outputs as order-1 projections of that state. Under this view, consensus protocols can be compared as collapse policies. A protocol specifies which evidence is legitimate, which finite horizon it inspects, when it projects a communication-induced evidence state into a value or prefix, and how it repairs or defers collapse when the visible evidence is insufficient. This separates legitimacy from collapse: quorum intersection, committee eligibility, checkpoint votes, sampling confidence, estimator safety, or DAG support can make evidence decision-grade, while the collapse policy determines when preserved distinctions are allowed to stop mattering. The impossibility lineage supports the same distinction. FLP constrains deterministic guaranteed collapse to a terminal decision under full asynchrony with one crash failure; set agreement exposes the width of the output carrier; topological distributed computing characterizes when a history/view carrier admits a structure-preserving map to an output carrier. The contribution is therefore not a new impossibility theorem or a replacement for protocol-specific proofs, but a denotational specification framework: consensus is collapse under evidence.

1

Introduction

Consensus is commonly presented as the problem of making distributed processes agree on a single value. That definition is correct for the classical task: agreement, validity, and termination are stated over a terminal decision [5]. But concrete protocols do not begin with a decided value. They begin with proposals embedded in communication. Processes exchange messages, form local views, collect votes, detect equivocation, wait for rounds or waves, build certificates, follow leaders, and sometimes defer decisions through fallback rules. This paper studies the structure that appears before the terminal decision. The central claim is simple: Nontrivial consensus is lawful projection from communication history: protocols differ less in their terminal artifact than in their policy for making accumulated communication evidence legitimate, visible, and stable enough to collapse into an order-1 output.

1

In many protocols, legitimacy is supplied by an intersection or threshold condition. In crashfault protocols such as Paxos and Raft, majority quorums intersect, so a later leader can recover the value or log prefix that may already have been made durable [2, 4]. In Byzantine quorum protocols, the boundary is stronger: with n = 3f + 1, any two quorums of size 2f + 1 intersect in at least f + 1 validators, hence in at least one correct validator. Weighted quorum systems, resource-weighted systems, and flexible quorum systems change the unit being counted or the pairs of quorums that must intersect. Federated quorum slices, private committee sortition, stable-prefix rules, finality gadgets, and repeated sampling change how decision-grade evidence is carried, but they still give the collapse rule a structured carrier to read. The real variation lies in the carrier and its closure policy. Protocols choose how much communicationinduced evidence to preserve before output, how they compress that evidence, when they stop waiting, and what they do when the visible evidence is insufficient. The same pattern is already visible in the original Byzantine Generals Problem: oral-message recursion and signed messages are two ways of preserving enough communication evidence before collapsing to a common order [10]. Leaders, rounds, waves, quorum-certificate chains, committee credentials, checkpoint links, sampling windows, direct and indirect rules, timeouts, anchors, and random leaders are later mechanisms for controlling this collapse boundary. Communication-history reading. In nontrivial distributed consensus, the primary carrier is not the terminal value. It is the communication-induced evidence state from which the value becomes justified. When the problem is framed output-first, the field studies increasingly elaborate ways to make the collapsed artifact safe. When framed communication-first, the same mechanisms become policies for preserving, compressing, delaying, or repairing the collapse from evidence state to prefix. In this sense, nontrivial distributed consensus is necessarily communication-mediated. If different components may begin with different information, then agreement satisfying a nontrivial validity condition must depend on some interaction structure by which information becomes shared, constrained, or made observable. The paper uses communication in this broad concurrency-theoretic sense, not merely as explicit network transmission. Lamport’s starting point. This communication-first view is already present in Lamport’s happened-before relation [1]. Lamport does not begin with a single global sequence. He begins with distributed events and the partial order induced by process-local order and message send/receive causality. Logical clocks then provide a way to extend that partial order into a total order when a system needs one. In the terminology used here, the causal communication history is the carrier; the total order is a projection. Consensus protocols repeat the same semantic move: they construct communication evidence and then project it to a value, log, block, or prefix. Protocol presentations often foreground the projected artifact, but the semantic work is carried by the communication evidence. Order terminology. We use “order-2” for the communication carrier: the evidence state induced by labelled events together with causal and evidential relations among them. We use “order-1” for the terminal artifact exposed by the usual consensus abstraction: a value, a linear log, or a finalized prefix. The terminology is semantic rather than hierarchical: order-2 objects remember relations between changes; order-1 objects expose the chosen state or prefix after those relations have been compressed.

2

Closure criterion. Meaning closes at a carrier when the correctness question can be answered from that carrier without consulting distinctions preserved only at a higher order. Thus collapse from order-2 history to an order-1 prefix is valid only when the evidence visible at the chosen horizon makes the discarded distinctions irrelevant. Thesis. Consensus protocols have accumulated many protocol-specific vocabularies. Lamport clocks speak in happened-before order and logical timestamps; Paxos in ballots, promises, and accepted values; Raft in terms, leaders, and log replication; PBFT in phases and views; Stellar in quorum slices and federated ballots; HotStuff in quorum-certificate chains; Tendermint and Streamlet in rounds, locks, notarizations, and finalized chains; Algorand in VRF sortition and committee certificates; Ouroboros in slots, stake, leader eligibility, and stable prefixes; GRANDPA and Casper FFG in finality votes and justified checkpoints; Avalanche/Snowman in repeated sampling and confidence thresholds; Jolteon and Ditto in fast paths and asynchronous fallback; CBC Casper in estimates, justifications, protocol states, and safety oracles; DAG-Rider in DAG waves and local interpretation; Hashgraph in gossip-about-gossip, witnesses, fame, and virtual voting; Aleph in units, posets, and common-coin ordering; Cordial Miners in blocklace, ratification, and final leaders; Mysticeti in direct and indirect slot rules. These names matter operationally, but semantically they often play the same role: they determine when a communication-induced evidence state is sufficiently legitimate, sufficiently visible, or sufficiently old to be collapsed into a prefix. Scope. This paper does not claim that FLP is false, incomplete, or merely an artifact of naive state abstraction. FLP remains the classical impossibility result for deterministic consensus in a fully asynchronous system with one crash failure [5]. The claim here is interpretive and structural: FLP constrains guaranteed terminal collapse under its model. It does not say that communication cannot accumulate causal structure, nor that all protocols should be understood only from the terminal value abstraction. The protocol comparison is limited to representative fault-tolerant consensus and atomic-broadcast protocols whose safety is organized around explicit evidence carriers: quorums, certificates, slices, committees, stake-weighted chain evidence, checkpoint votes, sampling histories, estimators, or DAG structure. Contributions.

The paper makes four contributions.

• It gives a self-contained vocabulary for reading consensus protocols as maps from communicationinduced evidence states to terminal outputs: evidence domain, communication carrier, legitimacy extraction, evidence horizon, collapse rule, and repair/deferral rule. • It separates legitimacy from collapse: quorum evidence, committee eligibility, checkpoint votes, sampling confidence, estimator safety, or DAG support says that evidence is decision-grade, while the collapse policy says when that evidence is sufficient to emit a value, log entry, block, or prefix. • It rereads the FLP–set agreement–topology lineage as a sequence of constraints on terminal decision carriers, without changing the underlying theorems. • It compares real consensus protocols in a shared normal form, with main case studies and appendix instantiations that name each carrier, operation, horizon, collapse rule, and protocol reading.

3

Non-contributions. The paper does not prove a new lower bound, derive the listed protocols from a single formal model, or claim that richer histories evade FLP. It also does not replace protocol-specific safety or liveness proofs, and it does not rank protocols by performance. Its contribution is a denotational specification framework for comparing consensus protocols by the communication evidence they retain, the legitimacy evidence they accept, the horizon they inspect, the projection they emit, and the repair or deferral rule they use when that horizon is insufficient.

2

Consensus as Communication

We separate two notions that are usually conflated. Semantic use of communication. The word “communication” is semantic here, in the concurrencytheoretic sense: execution is interaction among components. It does not mean only explicit network sends. It names the relational structure by which evidence becomes available and constraining: causality, dependency, certification, observation, inclusion, equivocation, and justification. Messages are one way to expose that structure; the carrier is the interaction structure recorded by the execution. The degenerate case in which all components already have the same fixed value, or in which validity does not depend on distributed information, is not the phenomenon studied here. The paper concerns consensus as a distributed computation: information is initially separated, and correctness depends on the interaction structure that makes some terminal observation safe. Definition 2.1 (Communication carrier) Given an evidence domain H, a communication carrier Ht ∈ H is the evidence state of the concurrent execution up to time or logical horizon t. Depending on the protocol instance, the observable distinctions may include labelled events, proposals, votes, messages, receives, timeout evidence, certificates, justified messages, local views, or DAG/blocklace structure. The relevant relations may include local order, message delivery, inclusion, certification, ratification, justification, equivocation, and anchor reachability. Definition 2.2 (Terminal consensus output) A terminal consensus output is an order-1 artifact such as a value, a log position, a block sequence, or a finalized prefix. It is obtained by applying a protocol-specific projection to a communication carrier. Standard consensus specifies properties of the terminal output. This paper asks how that output is produced from the communication carrier.

2.1

Collapse

Definition 2.3 (Collapse rule) A collapse rule is a partial map C : Ht ⇀ P from an evidence state to an order-1 prefix or value carrier. The map is partial because a protocol may refuse to decide when the visible evidence is insufficient. Collapse is not the same as legitimacy. A quorum certificate, commit certificate, or superratification witness says that some evidence is decision-grade. Collapse says which distinctions in the evidence state stop mattering once the protocol emits a value or prefix. 4

2.2

Evidence horizon

Every concrete decision is made from a finite visible cut of the evidence state, even if the protocol as a whole maintains an unbounded growing carrier. We call this cut the evidence horizon. Definition 2.4 (Evidence horizon) An evidence horizon is the portion of Ht that a protocol consults before attempting collapse. It may be a view, round, phase sequence, quorum-certificate chain, wave, anchor distance, slot frontier, or timeout window. If the horizon is too short or too compressed, progress may be blocked or unsafe. Protocols then need a repair, deferral, or fallback mechanism: view change, timeout certificates, randomized leaders, indirect rules, undecided slots, or later anchors.

2.3

Denotational reading of evidence

The evidence domain H is the space of possible order-2 carriers for a protocol. A particular Ht ∈ H is the communication carrier of an execution prefix: the evidence state produced by component interaction up to horizon t. The carrier may be described using protocol vocabulary– ballots, promises, certificates, DAG vertices, anchors, justified messages, or protocol states–but those names appear in the specification only for the distinctions they make meaningful. The generic collapse-policy form leaves H abstract. Each protocol instance chooses the evidence domain on which its legitimacy, horizon, and collapse maps are defined. Definition 2.5 (Evidence domain) An evidence domain for a protocol is a preordered set (H, ⊑ ). Its elements are evidence states. The relation h ⊑ h′ means that h′ preserves the evidence of h and may add further distinctions. The order is semantic: two descriptions may differ in irrelevant detail while determining the same evidence state. Definition 2.6 (Semantic collapse) Let Adm(h) be the admissibility predicate for evidence states and let obs : H ⇀ P be the terminal observation. For h ∈ H, write ↑Adm h = {h′ | h ⊑ h′ ∧ Adm(h′ )} for the admissible future cone of h. A prefix p is determined at h when some admissible refinement of h produces p, and all admissible refinements of h that can produce an observation produce that same observation: ∃h0 ∈↑Adm h. obs(h0 ) ↓ ∧obs(h0 ) = p and ∀h1 , h2 ∈↑Adm h. obs(h1 ) ↓ ∧obs(h2 ) ↓⇒ obs(h1 ) = obs(h2 ) = p. Collapse is valid when the emitted order-1 artifact is invariant under all admissible refinements of the current evidence. Meaning before mechanism. Under this reading, quorum certificates, locks, anchors, committee credentials, sampling thresholds, and safety oracles are not the meaning of consensus. They are protocol-specific witnesses that a terminal observation has become invariant over the relevant admissible future cone. A protocol may establish this invariant through messages, votes, DAG reachability, or estimator analysis, but the semantic question is the same: have all remaining admissible refinements lost the ability to change the exposed value or prefix? 5

Collapse debt. We call this situation collapse debt: the protocol tries to obtain an order-1 decision from an evidence horizon whose admissible refinements can still change the terminal observation. The debt is paid by waiting, carrying additional evidence, changing views, adding randomness, routing through fallback rules, or declaring a slot undecided. Collapse debt measures the semantic gap between the evidence a protocol has chosen to inspect and the evidence needed to make its terminal observation invariant. A repair rule is therefore not merely an operational fallback; it is a way of preserving or recovering the communication distinctions that the first horizon could not yet lawfully discard. For a concrete collapse attempt, debt is evaluated at the visible evidence v = R(L(Ht )), not necessarily at the full carrier Ht . A protocol may retain enough information in Ht to decide later while still refusing collapse from the current horizon. This is a recurring link across protocol families. Many mechanisms presented as distinct innovations can be read as ways of managing collapse debt.

3

Collapse-Policy Specification

We describe protocols using the following normal form: L

R

C

Ht −−→ Et −−→ Et |R −−→ P. • Ht ∈ H is the current communication carrier: the order-2 evidence state visible at the chosen time or horizon. • L is the legitimacy extraction that marks evidence as decision-grade. • Et is the admissible evidence extracted from the history. • R is the evidence horizon: the bounded region the protocol is willing to inspect before output. • Et |R is the visible admissible evidence inside the horizon. • C is the collapse rule that emits a prefix/value only when the visible evidence determines an observation, or refuses to decide. • P is the order-1 terminal artifact: value, log, block prefix, or ordered slot prefix. The legitimacy extraction belongs to L. For crash-fault protocols this is usually majority intersection; for Byzantine quorum protocols it is usually the 2f +1 supermajority rule; in weighted or flexible variants it is the required intersection relation among the relevant weighted or phasespecific quorums. In other families, legitimacy may come from quorum slices, VRF committee credentials, stable-prefix assumptions, checkpoint votes, sampling confidence, estimator safety, or DAG support. None of these is a collapse rule. Collapse belongs to R and C: how long the protocol waits, what evidence remains visible, and what is projected away when output is produced.

3.1

Protocol vocabulary dictionary

The normal form does not erase protocol terminology; it maps protocol terms to semantic roles. The table is a guide rather than a strict partition: blocks may be carrier events or output artifacts, and certificates, leaders, or anchors may also shape the horizon or collapse rule.

6

Semantic role evidence state (H) legitimacy extraction (L) admissible evidence (E) visibility horizon (R) collapse and repair (C) terminal output (P )

3.2

Protocol terms votes, accepts, proposals, blocks, ratifications quorum intersection, threshold checks, credentials, confidence, equivocation filters, safety predicates quorums, certificates, accepted values, ratifications, confidence counters, support/skip evidence leaders, proposers, primaries, anchors, relays, rounds, terms, views, waves, slots, QC chains timeouts, view changes, fallback rules, random leaders, indirect rules values, log entries, blocks, finalized prefixes

Specification form

The specification below makes the normal form explicit for the consensus protocols considered here, both in the main case studies and in the appendix catalog. It does not restate each protocol proof. It gives a small specification language in which each protocol becomes an instance: first the carriers and operations, then the mechanisms that realize them. The examples are representative published consensus or atomic-broadcast protocol families. The main text focuses on Lamport causal ordering, Byzantine Generals, Paxos, HotStuff, CBC Casper, Cordial Miners, and Mysticeti-C. The appendix gives additional instantiations for HoneyBadgerBFT and randomized asynchronous agreement, Raft, PBFT, Stellar, Tendermint, Streamlet, Algorand, Ouroboros, GRANDPA, Casper FFG, Snowman/Avalanche, Jolteon/Ditto, DAG-Rider, Hashgraph, Aleph, and Narwhal/Tusk/Bullshark. The method is spec-first. A protocol is introduced as a collapse-policy specification over named carriers: the carriers are named sorts, the operations are L, R, and C, and the laws say when the specified meaning is preserved. The protocol vocabulary names the protocol-specific evidence domain and the witnesses that satisfy those laws. Definition 3.1 (Collapse-policy specification) A collapse-policy specification for a protocol family Π consists of named carriers HΠ EΠ VΠ PΠ

: : : :

Type Type Type Type

and operations LΠ RΠ CΠ

: : :

HΠ → EΠ EΠ → VΠ VΠ ⇀ PΠ .

Here HΠ is the protocol-specific evidence domain, EΠ is decision-grade evidence, VΠ is the visible evidence inside the chosen horizon, and PΠ is the terminal output carrier. The induced decision map is DΠ := CΠ ◦ RΠ ◦ LΠ DΠ : HΠ ⇀ PΠ . When CΠ is undefined, the protocol does not have a valid collapse from the current horizon. It must either preserve the carrier for later evidence, repair the horizon, or defer output. Definition 3.2 (Realization law) A concrete realization I of a collapse-policy specification Π I , E I , V I , P I , concrete operations LI , RI , C I , and denotations supplies carriers HΠ Π Π Π Π Π Π I [[−]]H : HΠ → HΠ ,

[[−]]E : EΠI → EΠ ,

[[−]]V : VΠI → VΠ , 7

[[−]]P : PΠI → PΠ .

Correctness means that the realization preserves the specified meaning: hh

ii

hh

ii E

hh

ii V

LIΠ (h)

≡ LΠ ([[h]]H ),

I RΠ (e)

≡ RΠ ([[e]]E ),

I CΠ (v)

P

≡ CΠ ([[v]]V )

I when CΠ (v) is defined.

Consequently, hh

I DΠ (h)

ii P

≡ DΠ ([[h]]H )

whenever the realization emits an output. This is the denotational obligation: concrete structures may vary, but their observable collapse must preserve the specified meaning.

4

FLP as Order-Collapse Constraint

The FLP theorem states that deterministic consensus cannot guarantee termination in a fully asynchronous message-passing system with even one crash failure [5]. It is a theorem about the classical terminal task. The order vocabulary does not change the theorem. It makes explicit which semantic operation the theorem constrains. FLP is about the impossibility of guaranteeing an order-1 terminal decision from an asynchronous execution carrier under a particular adversary model: deterministic processes, reliable asynchronous message passing, and one possible crash failure. Classical structure. The FLP proof reasons over global configurations: process states, message buffers, and the deterministic protocol state induced by prior steps. A configuration is 0-valent if every admissible continuation decides 0, 1-valent if every admissible continuation decides 1, and bivalent if both decisions remain possible under different admissible continuations. The proof shows that there is an initial bivalent configuration and that, from a bivalent configuration, the asynchronous adversary can choose a next event that keeps the execution bivalent. This is not a claim that FLP uses an impoverished state model. FLP configurations are already rich enough to include process state and pending-message information. The collapse reading instead identifies the operation constrained by the theorem: a deterministic protocol cannot guarantee that every admissible execution eventually reaches a region where the terminal decision map is determined. Translation to the normal form. In this notation, the growing communication carrier is Ht . The protocol extracts decision-grade evidence Et , restricts attention to a horizon Et |R , and applies a collapse rule C : E t |R ⇀ P where, for binary consensus, P = {0, 1}. A univalent configuration is one where the remaining admissible histories already lie in one fiber of this collapse: all completions compatible with the current evidence lead to the same decision. A bivalent configuration is one where the current history and visible evidence are still compatible with multiple fibers of C.

8

What the adversary preserves. The FLP adversary does not need to corrupt messages or break safety. It exploits asynchrony: delay and crash are indistinguishable to finite local views. By choosing which pending message or process step becomes visible next, the adversary keeps the current Ht inside a region where both decision fibers remain reachable. The current carrier has not semantically closed over a single order-1 decision. Concrete reading. Suppose a process is about to take a step that would make decision 0 inevitable. FLP’s commutativity and indistinguishability argument shows that, in the asynchronous crash model, there is another admissible scheduling of independent or delayed events that cannot be distinguished locally but preserves the possibility of decision 1. The protocol state may grow, and messages may be delivered, but the evidence visible inside the current horizon still does not determine a unique collapse. The system can keep accumulating communication-induced evidence without reaching a point where every fair admissible continuation must project to the same terminal value. Order-1 progress condition. This is why FLP is central to the thesis. The safety condition says that if collapse happens, all correct processes must collapse compatibly. The termination condition says collapse must eventually happen. FLP says that, under full asynchrony and one crash failure, deterministic protocols cannot guarantee both for the order-1 consensus output. The obstruction is not communication itself; it is guaranteed terminal collapse. Common overreading. The overreading is to treat FLP as saying that distributed coordination itself cannot progress under asynchrony. That is too broad. Communication can still accumulate causal structure. Processes can still exchange evidence, form local views, build partial orders, and preserve alternatives. What FLP rules out is deterministic guaranteed collapse to a terminal decision under the asynchronous crash assumptions. Why this matters. Once consensus is viewed only from the terminal output, all pre-decision communication structure becomes protocol plumbing. Once the communication carrier is made explicit, FLP appears as a limit on guaranteed collapse, not as a denial that the order-2 carrier can grow. This is the key separation: evidence growth belongs to Ht , while decision belongs to C. FLP constrains the guarantee that C must become defined, not the existence of meaningful structure in Ht . Ways protocols escape the FLP setting. Protocols obtain progress by changing the problem setting or the collapse policy: adding partial synchrony [11], adding failure detectors [12], using randomization [31], relying on stronger timing/eventual-leader behavior, widening the output carrier, or deferring collapse until richer evidence is visible. These are not violations of FLP. They change the conditions under which C is allowed, expected, or required to produce an output.

5

Collapse Ladder in Consensus Theory

With FLP stated in normal form, the rest of the impossibility lineage can be read as a progressive exposure of collapse structure.

9

FLP: binary collapse. FLP is the binary base case. The decision set has width one: all correct processes must collapse to the same value, even though the value domain has two alternatives. The adversary preserves bivalence, so the collapse rule C cannot be guaranteed to become defined in every admissible execution [5]. Chaudhuri: collapse width. Set agreement makes the output width explicit. In k-set agreement, processes decide proposed values, but at most k distinct values may be decided. Consensus is the special case k = 1. Chaudhuri’s formulation therefore exposes k as the allowed residual ambiguity after collapse: more output width can absorb more unresolved alternatives. The possibility side already has this shape: there is a simple (k − 1)-resilient protocol for k-set agreement in a totally asynchronous system [6]. Borowsky–Gafni: resilient simulation. Borowsky and Gafni generalize the FLP pattern by showing that the obstruction scales with resilience [7]. In particular, the matching lower-bound reading is that k-set consensus cannot be guaranteed when the protocol must tolerate k crash failures. The useful reading here is not just “more impossibility.” It is that crash resilience gives the adversary scheduling power to preserve a space of alternatives too large for the requested output carrier. FLP is bivalence; the generalized picture is polyvalence. Herlihy–Shavit: topological factorization. Topological distributed computing gives the geometric form of the same claim. A task is solvable when the protocol complex, which records executions and local views, admits a suitable simplicial map into the output/task complex [8]. Saks and Zaharoglou’s public-knowledge proof gives the parallel topological impossibility for wait-free k-set agreement [9]. Impossibility means no structure-preserving collapse exists from the history/view carrier to the decision carrier. Interpretation. This ladder suggests a semantic diagnosis. Once the problem is framed as agreement on an order-1 artifact, protocol research naturally studies mechanisms for making that terminal artifact safe and live under adversarial uncertainty. Leaders, rounds, views, quorum certificates, locks, timeouts, waves, anchors, randomization, failure detectors, direct rules, indirect rules, and undecided slots can be read as ways of managing the boundary between a rich communication carrier and a narrower decision carrier.

6

From Impossibility to Protocol Mechanisms

The ladder above should not be read as a formal derivation of Paxos, PBFT, HotStuff, or DAG protocols. The models differ: FLP and Borowsky–Gafni are crash-failure impossibility results; topological computability is usually stated for wait-free read/write shared memory and colorless tasks; later BFT protocols handle Byzantine faults, partial synchrony, randomness, authentication, threshold evidence, and replicated logs. The connection is semantic rather than model-identical. The impossibility lineage identifies the obstruction to forcing collapse under adversarial uncertainty. Practical protocols then choose how to change the conditions around that obstruction: • add timing: partial synchrony and leader responsiveness make some evidence eventually timely; • add oracles: failure detectors and view-change logic introduce information not present in pure asynchrony; 10

• add randomness: randomized protocols prevent the adversary from deterministically preserving the same ambiguity forever; • add authentication and quorum evidence: certificates make local claims portable across processes and views; • delay collapse: DAG and wave protocols retain more communication-derived evidence before projecting to order; • refuse collapse: undecided slots, failed waves, and fallback paths avoid emitting a prefix across insufficient evidence. Thus the protocol comparison below is not a claim that every mechanism is an instance of one theorem. It is a normal-form comparison of how protocols manage the same semantic pressure: an order-2 communication carrier must eventually be interpreted as an order-1 value, log, or prefix.

7

Protocol Specifications and Readings

This section applies the normal form to representative protocols. The point is not that all protocols are identical. The point is that their apparent differences can be placed in the same comparison frame: legitimacy, horizon, collapse, and repair. The main text does not attempt to survey every consensus protocol in equal detail. Instead, it develops the denotational argument through cases that expose distinct semantic roles: causal projection, carrier enrichment, quorum recovery, certificate compression, admissible-future safety, and DAG collapse debt. The appendix then instantiates the same normal form for a broader set of protocols. Those appendix entries are not secondary in protocol importance; they are secondary in the proof strategy. They serve as coverage checks once the semantic argument has been established. Case Lamport ordering

HotStuff

Evidence domain events, messages, logical clocks oral or signed report histories ballots, promises, accepted values proposal tree, votes, QCs

CBC Casper

justified message sets

Semantic role causal carrier before total order carrier enrichment under equivocation crash-fault quorum recovery Byzantine certificate compression admissible-future safety

Cordial Miners

blocklace waves and ratifications slot DAG, anchors, support/skip evidence

backward evidence from final leaders explicit collapse debt at a slot frontier

Byzantine Generals Paxos

Mysticeti-C

Collapse witness total-order extension of happened-before loyal-consistent interpretation of reported values majority evidence plus highest accepted ballot certified-chain ancestry rule estimator invariance over future states final leader and ordering function τ direct or indirect slot classification

The section is organized spec-first. For each main case, the named carriers and maps state the semantic object; the protocol reading then explains how the protocol mechanisms realize that object. The comparative notes preserve the original protocol-by-protocol reading while making the specification the primary artifact. In the protocol specifications below, the displayed carriers are protocol-specific evidence domains. The purpose of each main case is to identify the witness by which the protocol establishes invariance of the terminal observation. Concrete realizations enter only through the realization law above: they must denote these specified carriers and preserve the specified collapse. 11

7.1

Reference baseline

The reference baseline keeps the communication carrier as the primary semantic object. A finalization rule commits causally closed subhistories rather than immediately projecting them to a single prefix. A prefix output may still be produced, but it is explicitly a projection from finalized history. This baseline is not presented as a practical protocol. It is the reference object against which information loss is measured: • carrier: labelled event DAG with causal and evidential edges; • legitimacy: threshold-valid evidence inside the DAG; • horizon: delayed until the relevant causal subhistory is visible; • collapse: optional projection to a prefix after order-2 finalization; • loss: only the loss introduced by the explicit projection, not by finalization itself.

7.2

Lamport causal ordering

The pre-consensus foundation is Lamport’s happened-before relation and logical clocks [1]. That paper is not a consensus protocol in the later Paxos/Raft/PBFT sense, but it is the starting point for this communication-history view. It identifies distributed execution as a partially ordered set of events and then shows how logical clocks can produce a total order extension of that partial order. In the normal form: • carrier: distributed events, process-local order, and message send/receive causality; • legitimacy: happened-before evidence induced by local order and communication; • horizon: events visible to a process through received messages and logical-clock updates; • collapse: logical timestamps plus tie-breaking extend a causal partial order into a total order; • discarded distinctions: concurrency is hidden when incomparable events are placed in an arbitrary total order; • repair mechanism: none at the consensus level; this is ordering machinery, not fault-tolerant agreement. This is the original carrier/projection pattern for distributed ordering. A communicationinduced partial order is the primary object, and a total order is a projection used when applications require a single sequence. Later consensus protocols add faults, quorums, certificates, leaders, and finality, but they still manage the same boundary: when can communication-induced evidence be collapsed into a terminal order or prefix?

7.3

Byzantine Generals as local-history collapse

The Byzantine Generals Problem is the Byzantine base case of the collapse view [10]. Lamport, Shostak, and Pease do not begin with a blockchain-style finalized prefix or even with a replicated log. They begin with a more primitive question: how can loyal participants obtain compatible information when faulty participants may send conflicting reports to different places?

12

The paper first frames the generals’ decision as a function of values v(1), . . . , v(n), where v(i) is the value communicated by general i. The difficulty is that a traitorous general may send different values to different loyal generals. Therefore, before any robust decision function such as majority can be applied, loyal generals must agree on which value of v(i) is to be used. This is precisely a local-history problem: different loyal participants may hold different communication histories that are locally plausible but cannot all be collapsed to the same decision. In the normal form: • carrier: oral reports or signed reports about who said what; • legitimacy: oral relay structure in the unsigned model, transferable signature evidence in the signed model; • horizon: recursive message depth for oral messages, or signature paths for signed messages; • collapse: a choice rule, such as majority, applied only after each v(i) has a loyal-consistent interpretation; • discarded distinctions: alternate reports and equivocations not retained by the final selected value; • repair mechanism: deeper oral recursion, or carrier enrichment by unforgeable signatures. This makes the role of signatures especially clear. A signed message is not merely an authentication optimization. It changes the semantic carrier: equivocation becomes portable evidence. In the oral-message model, a report about a report may need additional relay depth before loyal participants can interpret it consistently. In the signed-message model, conflicting signed statements can be carried forward as first-class evidence. Thus the Byzantine Generals Problem is not only the origin of Byzantine fault tolerance; it is an early instance of the pattern. Byzantine faults attack the communication carrier itself. The protocol must preserve or enrich enough of that carrier before collapse to a value is safe.

7.4

Paxos and Multi-Paxos

Consider one Paxos instance. A proposer enters ballot b and asks acceptors for promises. The carrier contains proposals, promises, accepted ballot/value pairs, and acceptor state. The legitimacy backbone is majority intersection: once a majority of acceptors has responded, later majorities intersect with earlier ones, so accepted evidence can be recovered. The horizon is the phase-1 response set. If that response set reveals that some acceptor has already accepted a value, the proposer cannot safely ignore it and propose something arbitrary. It must recover the value with the highest accepted ballot and then seek majority accepts for that value. Multi-Paxos repeats this across slots under a stable leader, which makes the log case a repetition of the same recovery logic. The repair path is therefore not "undo the history"; it is "lift the prior accepted evidence into the next ballot." Protocol vocabulary.

Proposer, ballot, promise, accepted value, acceptor state, majority.

13

Collapse-policy specification. HPaxos

:

EPaxos

:

VPaxos

:

PPaxos

:

proposals, ballots, promises, accepted values, acceptor state accepted ballot/value evidence from acceptors phase-1 evidence visible in ballot b, followed by phase-2 accepts chosen value for slot s

LPaxos (h) := {(a, b′ , x) | a accepted value x in ballot b′ in h} RPaxos,b (e) := ( {(a, b′ , x) ∈ e | a promised ballot b} x if (a, b′ , x) ∈ v has maximal b′ , SPaxos,x0 (v) := x0 if v contains no accepted value. CPaxos (v) := the value accepted by a majority in phase 2, when such a majority exists.

Protocol reading. Promises and accepted values carry the prior evidence, and the phase-1 response set is the horizon for choosing a safe proposal SPaxos . Majority accepts in phase 2 implement the collapse CPaxos . Multi-Paxos repeats the same specification across slots under a stable leader. Denotational reading. For one Paxos slot, h ⊑ h′ means that h′ extends the ballot history while preserving acceptor promises and accepted-value evidence already present in h. The admissibility predicate Adm restricts refinements to executions that respect the Paxos acceptor rules: an acceptor does not accept below a promised ballot, and majorities intersect. The terminal observation obs(h) is the value chosen for the slot, when such a value is forced by majority accept evidence. Phase 1 is therefore a meaning test, not the final collapse: the proposer asks whether the current evidence state already lies in a future cone where some prior value constrains all safe proposals. If so, the highest accepted value is the only value whose observation can remain invariant under admissible extension; collapse occurs only when phase 2 obtains a majority of accepts for that value. Comparative reading. Paxos turns majority quorum intersection into a crash-fault consensus mechanism [2, 3]. In the normal form: • carrier: proposals, ballots, promises, accepted values, acceptor state, and learner observations; • legitimacy: intersecting majorities of acceptors; • horizon: ballot phase and accepted-value evidence visible to a proposer; • collapse: a majority of accepts chooses a value for an instance; Multi-Paxos repeats this over log slots under a stable leader; • discarded distinctions: losing proposals, alternate proposer races, and timing histories not reflected in the chosen value; • repair mechanism: higher ballots recover prior accepted evidence before proposing a safe value. From the collapse view, Paxos is already a collapse-debt protocol. A proposer cannot safely choose an arbitrary value after earlier ballots may have made progress. It must first ask acceptors what evidence already exists, then collapse only through a value compatible with that evidence. 14

7.5

HotStuff

HotStuff’s concrete object is a proposal tree under rotating leaders. The carrier contains proposal edges, votes, quorum certificates, locks, highest-QC information, and timeout evidence in later variants. The legitimacy relation is a QC, which makes support for a block portable across validators and views. The horizon is the certified chain, classically the chain depth used by the three-chain commit rule. Collapse commits an ancestor of the certified chain and extends the ordered prefix. The QC chain compresses several rounds of evidence into a structure that can be carried and reused across view changes. If a leader fails to produce the needed chain, the protocol repairs by rotating leaders, propagating the highest QC, and using lock and timeout evidence to keep safety while preserving liveness. Protocol vocabulary. change, leader rotation.

Proposal tree, votes, quorum certificate, lock, highest QC, timeout, view

Collapse-policy specification. HHotStuff

:

EHotStuff VHotStuff PHotStuff

: : :

proposal tree, votes, QCs, locks, highest-QC state, timeout evidence certified proposal-chain evidence certified chain visible in the current view ordered prefix

LHotStuff (h) := {(b, q) | q is a quorum certificate for block b in h} RHotStuff,v (e) := {(b, q) ∈ e | (b, q) is carried into view v} CHotStuff (u) := {a | u contains a certified three-chain committing ancestor a}.

Protocol reading. The proposal tree is the carrier, the QC is the legitimacy witness, the certified chain is the horizon, and the three-chain rule collapses that chain into an ordered prefix while leader rotation preserves safety across failures. Denotational reading. For HotStuff, h ⊑ h′ means that h′ extends the proposal tree with additional votes, certificates, timeout evidence, and descendants while preserving certified ancestry already visible in h. The admissibility predicate Adm enforces validator voting rules, quorum thresholds, and lock-compatible extensions. The observation obs(h) is the committed prefix determined by certified ancestry. A quorum certificate is not itself the meaning of finality; it is a portable witness that a block has entered the evidence state strongly enough to constrain later admissible refinements. The three-chain rule is the point at which further lock-compatible refinements can no longer change the committed ancestor observation. Comparative reading. HotStuff keeps the Byzantine quorum threshold but compresses evidence into quorum-certificate chains under rotating leaders [19]. In the normal form: • carrier: proposal tree, votes, quorum certificates, locks, view changes, timeout evidence in later variants; • legitimacy: a quorum certificate for a proposed block; • horizon: a chain of certified proposals, classically the three-chain commit rule; 15

• collapse: the QC chain commits an ancestor block and extends the ordered prefix; • discarded distinctions: uncertified branches, alternate leader proposals, and causal details compressed into the QC chain; • repair mechanism: highest-QC propagation, leader rotation, view synchronization, and timeout certificates in practical variants. HotStuff keeps legitimacy in quorum certificates and changes the shape of the carrier. Multiphase evidence becomes a certified chain, so the commit rule reads ancestry in that chain rather than a standalone phase transcript. Two-chain descendants. The three-chain rule is the classical HotStuff point in this design space, not a claim that three certified links are semantically primitive. From the order perspective, the later two-chain variants expose a tradeoff that is easy to miss in a phase-count presentation. Jolteon uses a two-chain commit rule by accepting a quadratic view-change path, reducing the steady-state latency of standard three-chain HotStuff [23]. HotStuff-2 shows the same lesson in a sharper form: two phases can be enough while retaining the desired HotStuff properties when the synchronization and view-change evidence is organized differently [24]. If the minimum commit horizon is two certified order steps, then a three-chain rule is not a semantic necessity; it is a choice to keep more of the safety argument inside the visible proposal chain. Reducing the chain horizon to two requires the missing order constraints to be carried elsewhere, in the synchronization or view-change evidence. Thus the design parameter is not simply “two phases versus three phases”, but the distribution of order evidence between the proposal-chain carrier and the repair carrier.

7.6

CBC Casper

CBC Casper starts from a general proof shape. A protocol state σ is a set of messages. A message carries an estimate, a sender, and a justification. The justification is itself a set of earlier messages, so protocol states carry their own dependency structure. The estimator E maps a protocol state to a consensus estimate: in the blockchain instance, the GHOST fork choice. Faults are represented by equivocation evidence. A validator equivocates when it has two messages in the dependency closure of a state such that neither message depends on the other. The admissible protocol states Σt are those whose evidenced fault weight is at most t. A state transition is set extension inside Σt . Finality is then estimate safety: an estimate is safe when every admissible future state preserves it. Protocol vocabulary. Protocol state, message, estimate, sender, justification, dependency, latest message, estimator, GHOST, equivocation, fault weight, safety oracle, safe estimate.

16

Collapse-policy specification. HCBC ECBC

: :

VCBC PCBC

: :

sets of valid messages with justification dependencies latest-message, estimator, equivocation, fault-weight evidence candidate estimate with admissible-future analysis safe estimate or finalized block

LCBC (σ) := ⟨σ, E(σ), latest(σ), Eq(σ)⟩ Eq(σ) := {(m1 , m2 ) ∈ D(σ)2 | sender(m1 ) = sender(m2 ), m1 ̸≺ m2 , m2 ̸≺ m1 } Σt := {σ ⊆ M | F (σ) ≤ t} σ →t σ ′ := σ, σ ′ ∈ Σt ∧ σ ⊆ σ ′ Safet (e, σ) := ∀σ ′ ∈ Σt . σ →t σ ′ ⇒ e ≡ E(σ ′ ) RCBC,e (l) := ( the safety-oracle view of Safet (e, σ) where σ is carried by l e if u certifies Safet (e, σ), CCBC (u) := undefined otherwise.

For the blockchain instance, e ≡ E(σ ′ ) means that the candidate block e remains in the chain selected by the estimator E(σ ′ ). Thus finality is not equality with one current fork choice; it is invariance of the relevant prefix across all admissible future fork choices. Protocol reading. Messages and justifications are the carrier, the estimator supplies the current consensus proposition, equivocation evidence bounds admissible futures, and the safety oracle is the horizon test. CBC collapses only when the candidate estimate is invariant over those futures. If the oracle cannot certify safety, the protocol must keep the carrier open by receiving or producing more justified messages; the core CBC safety construction does not provide liveness by itself. Comparative reading. Correct-by-Construction Casper, in Vlad Zamfir’s Casper the Friendly Ghost presentation, starts from protocol states, estimates, and a safety theorem rather than from a leader, phase sequence, or commit certificate [30]. A protocol state is a set of valid messages. Each message carries an estimate, a sender, and a justification: the prior messages that make the new estimate meaningful. The estimator maps a protocol state to the current consensus proposition: a bit in the binary version, or a GHOST fork-choice block in the blockchain version. The collapse point is not the estimator by itself. The estimator gives the current estimate. Finality requires estimate safety: an estimate is safe in state σ when every admissible future state reachable from σ keeps the estimator compatible with that estimate. Equivocation evidence determines which future states are admissible under the fault threshold t. In the blockchain instance, a block is safe when it remains in the fork choice for every future protocol state with fault weight at most t. In the normal form: • carrier: sets of valid messages or blocks, each with estimate, sender, and justification dependencies; • legitimacy: estimator-valid messages, latest-message weight, and equivocation/fault evidence below threshold t; • horizon: the local protocol state σ, plus the safety oracle’s analysis of admissible future extensions of σ; 17

• collapse: decide an estimate or finalize a block only when it is safe across all admissible futures; • discarded distinctions: future branches or message extensions that can no longer change the safe estimate; • repair mechanism: if the safety oracle cannot certify safety, continue accumulating justified messages or equivocation evidence; the core safety construction does not by itself specify a liveness strategy. CBC Casper gives the cleanest set-theoretic presentation of the order-theoretic reading, because protocol-state extension is explicit set inclusion. But the set is not the semantic source of finality. It is a representation of communication evidence: messages carry justifications, justifications induce dependency order, and adding messages refines the state. The primitive object is still the growing communication structure, while set inclusion is the chosen mathematical presentation of its refinement order. For this reason, CBC is used here as evidence for the comparison method, not as the comparison method itself. Taking message sets as primitive would hide the broader point: different protocols present the same continuation question through different carriers of communication order. Finality is therefore not a special chain-depth pattern but invariance of the estimator over all admissible future extensions. In this sense CBC makes explicit what chain protocols encode operationally: collapse is justified when further admissible communication can no longer change the observation. Once protocol states, estimators, and admissible futures are named, finality can be stated as estimate safety rather than as a protocol-specific commit gadget. The collapse-policy view then asks the same questions across other carriers: why this carrier is needed, how the horizon is chosen, and what order distinctions are lost when it projects to a lower-order output.

7.7

Cordial Miners

Cordial Miners uses a blocklace to support dissemination, equivocation exclusion, and ordering. The carrier contains blocks, acknowledgment or ratification edges, equivocation evidence, and the partial order induced by the blocklace. The legitimacy relation is ratification and super-ratification by a supermajority of blocks. The horizon is the wave and the evidence for whether a final leader exists in that wave. Collapse applies the deterministic ordering function τ , walking from final leaders through ratified structure to emit ordered fragments. If no final leader exists, the protocol defers ordering rather than forcing a prefix. Later blocklace evidence may create a final leader and let τ settle earlier ambiguity. Protocol vocabulary. Blocklace, acknowledgment, ratification, super-ratification, wave, final leader, ordering function τ .

18

Collapse-policy specification. HCM

:

ECM VCM PCM

: : :

blocklace blocks, acknowledgments, ratification edges, equivocation evidence ratified and super-ratified blocklace evidence wave evidence with final-leader candidates ordered fragments

LCM (h) := {b ∈ blocks(h) | b is ratified or super-ratified in h} RCM,w (e) := {b ( ∈ e | b belongs to wave w or is reachable from it} τ (ℓ, u) if ℓ is a final leader visible in u, CCM (u) := undefined otherwise.

Protocol reading. The blocklace is the carrier, ratification and super-ratification are the legitimacy witnesses, the wave and final-leader evidence are the horizon, and τ collapses that evidence into ordered fragments when the leader is available. Denotational reading. For Cordial Miners, h ⊑ h′ means that h′ extends the blocklace with additional blocks, acknowledgments, ratification edges, and equivocation evidence while preserving the partial order already denoted by h. The admissibility predicate Adm keeps only refinements compatible with the blocklace validity and fault assumptions. The observation obs(h) is the ordered fragment emitted by τ , when a final leader is visible. If no final leader exists in the current wave, the horizon does not yet determine an ordered fragment; ordering is deferred until later blocklace evidence supplies a final-leader witness. Comparative reading. Cordial Miners uses a blocklace, a DAG-like structure, to support dissemination, equivocation exclusion, and ordering [37]. It organizes rounds into waves and uses final leaders ratified by supermajority evidence. In the normal form: • carrier: blocklace events, acknowledgments, ratification edges, equivocation evidence, and wave structure; • legitimacy: ratification and super-ratification by a supermajority of blocks; • horizon: wave length and the presence or absence of a final leader in a wave; • collapse: the deterministic function τ traverses from final leaders and emits newly ordered fragments; • discarded distinctions: blocklace concurrency after τ outputs a total order fragment; • repair mechanism: if no final leader exists in a wave, ordering is deferred rather than forced. Cordial Miners preserves history through the wave, collapses at final leaders, and defers when no final leader is visible. The blocklace perspective is broader than consensus: it treats partially ordered communication evidence as a reusable distributed object, with total-order consensus appearing as one possible collapse policy over that object [38].

19

7.8

Mysticeti-C

Consider a proposer slot s. The carrier is the uncertified slot DAG: proposals, signed blocks, references, anchors, equivocation evidence, and classifications of later slots. The legitimacy relation extracts support, skip, and implicit certificate patterns for s from the DAG itself rather than from explicit per-block certificates. The direct horizon is intentionally short, and the direct collapse rule classifies s as to-commit, to-skip, or undecided. If the slot remains undecided, the indirect horizon consults later anchor and causal evidence. The protocol does not treat the direct horizon as sufficient. It marks uncertainty at the slot frontier and later reads preserved evidence to repair that uncertainty. Protocol vocabulary. Slot, proposal, signed block, support pattern, skip pattern, implicit certificate pattern, anchor, direct rule, indirect rule, to-commit, to-skip, undecided. Collapse-policy specification. uncertified slot DAG, proposals, signed blocks, anchors, equivocation evidence EMysticeti : support, skip, and implicit certificate patterns for a proposer slot VMysticeti : direct horizon or later anchor horizon PMysticeti : {to-commit, to-skip, undecided}   {v | ∃b ∈ blocks(h). v authored b and b supports s}, LMysticeti,s (h) := {v | ∃b ∈ blocks(h). v authored b and b skips s} RMysticeti,dir (e) := the part of e visible to the direct rule RMysticeti,ind (e) := the  part of e visible through later anchors to-commit if u contains the required implicit certificate pattern for s,  CMysticeti (u) := to-skip if u contains the required skip pattern for s,   undecided otherwise. HMysticeti

:

Protocol reading. The slot DAG is the carrier, support/skip and implicit certificate patterns are the legitimacy witnesses, the direct rule is the first horizon, and the indirect anchor rule repairs undecided slots later. Denotational reading. For Mysticeti-C, h ⊑ h′ means that h′ extends the uncertified slot DAG with later signed blocks, anchors, support/skip patterns, implicit certificate patterns, and equivocation evidence while preserving the causal links visible in h. The admissibility predicate Adm restricts refinements to DAG extensions that satisfy block validity, pattern validity, quorum thresholds, and the protocol’s equivocation bounds. The observation obss (h) for a slot s is its classification: to-commit, to-skip, or still undefined for prefix advancement. The direct rule asks whether the short horizon already determines obss . The undecided outcome means exactly that admissible refinements can still change the slot observation. The indirect rule widens the horizon by reading later anchor evidence until the observation becomes invariant, or until the prefix frontier remains blocked. Comparative reading. Mysticeti-C names both the short-horizon rule and the later recovery path. It operates on a DAG of round-indexed proposer slots and classifies each slot as to-commit, to-skip, or undecided [36]. In the normal form: 20

• carrier: round-indexed DAG slots, signed blocks, causal links, anchors, and observed slot classifications; • legitimacy: support, skip, and implicit certificate patterns read from later DAG blocks; • horizon: the direct-rule visibility surface for a slot, extended later by anchors; • collapse: a slot is classified as to-commit or to-skip, and the ordered output advances until the first undecided slot; • discarded distinctions: causal evidence outside the direct rule’s immediate horizon is not part of the direct classification surface; • repair mechanism: the indirect rule consults later anchor evidence, causal links, and implicit certificate patterns; undecided slots prevent unsafe prefix collapse. The direct rule intentionally uses a short evidence horizon. If that horizon is not sufficient, the protocol does not recover information from the emitted prefix. It either refuses to collapse by leaving the slot undecided, or it uses later preserved DAG evidence through an indirect anchor rule. The indirect rule pays collapse debt created by the limited direct horizon. Mysticeti does not merely add a protocol fallback. Progress cannot always be computed from the information visible to the direct rule, so the later rule reads more of the communication carrier. Mysticeti also pipelines the collapse frontier: slot decisions are evaluated in a steady flow rather than only at isolated waves. This makes Mysticeti closer to HotStuff’s chained/pipelined style, but the pipeline runs over a DAG slot structure rather than a single leader chain. Its to-skip rule is a negative collapse rule: the protocol can advance by deciding that a slot should not contribute to the prefix, not only by positively committing a slot. The undecided state marks the remaining collapse debt.

7.9

Worked derivation: one Mysticeti-C slot

This subsection instantiates the preceding collapse-policy specification for one slot in Mysticeti-C. It is not an additional protocol definition or proof; it shows how the normal form names the direct rule, the undecided state, and the later indirect rule. Consider a proposer slot s in round r. Let Ht be the local DAG visible to a validator at logical time t. The relevant events include proposals for s, signed blocks in later rounds, references between blocks, support or non-support for proposals, implicit certificate patterns, observed equivocations, and the classifications already assigned to later slots. L

R

C

s dir Ht −−→ Et (s) −−− → Et (s)|Rdir −−dir −→ {to-commit, to-skip, undecided}.

Here Ls extracts support patterns relevant to slot s, such as enough later blocks witnessing an implicit certificate pattern, or a skip pattern showing that the slot should not contribute to the output. The direct horizon Rdir is intentionally short: it asks whether the local DAG already contains enough nearby evidence to classify s. The direct collapse rule Cdir has three outcomes: • to-commit: the direct horizon contains sufficient support for a proposal in s; • to-skip: the direct horizon contains sufficient evidence that no proposal in s should contribute to the output; • undecided: the direct horizon does not justify either positive or negative collapse. 21

The third outcome is a refusal to project across insufficient evidence. It is not a terminal prefix decision. If slot s remains undecided, the protocol consults a later horizon: L

R

C

s Ht −−→ Et (s) −−ind −→ Et (s)|Rind −−ind −→ {to-commit, to-skip, undecided}.

The indirect horizon Rind includes later committed-anchor information, causal links, and implicit certificate patterns. If the relevant later anchor is itself undecided, the earlier slot may remain undecided. If a later committed anchor causally references a certificate pattern over s, the slot can be classified to-commit. A to-skip classification is justified only relative to that committed-anchor horizon: the later anchor must be sufficient for the protocol’s indirect rule to conclude that no relevant certificate pattern for s is present. Thus the indirect rule does not repair the prefix after the fact. It reads evidence that was preserved in the DAG but not visible, or not decisive, inside the direct horizon. Two local histories can therefore agree on the currently emitted prefix while differing in later DAG evidence about an earlier undecided slot. A pure prefix output cannot distinguish them. Mysticeti-C keeps the communication carrier available long enough for the indirect rule to distinguish them later. This is the concrete form of collapse debt: the short direct horizon buys latency when evidence is clear, and the undecided/indirect path preserves safety when it is not.

8

Synthesis

8.1

Shared semantic shape

The main case studies expose a repeated shape. Each protocol accumulates an order-2 communication carrier, extracts decision-grade evidence, restricts attention to a horizon, and then either collapses to an order-1 output or applies a repair/deferral rule. The terminal artifact is the endpoint of this semantic operation, not the object from which the safety argument begins. The appendix checks the same shape across a wider protocol landscape. The surface terminology differs; the semantic control problem is shared. Carrier first. Lamport clocks and the Byzantine Generals Problem are the base cases. Lamport starts from causally ordered events and projects them to a total order only when a total order is needed. Byzantine Generals starts from local report histories and shows that collapse to a common value is unsafe until loyal participants have compatible interpretations of who said what. In both cases, the terminal value or order is not the primitive object. The communication carrier is. Quorum recovery. Paxos uses majority evidence to protect a value across later attempts to collapse. It carries prior accepted values through higher ballots, so the repair rule is not to restart history but to recover the evidence that may already constrain future collapse. Raft, treated in the appendix, gives the replicated-log version of the same crash-fault pattern. Certificate compression. HotStuff moves the argument into Byzantine quorum evidence. It compresses multi-phase support into quorum-certificate chains, making view change and pipelining cheaper. PBFT, treated in the appendix, is the phase-certificate predecessor. The shared pattern is not the specific phase structure; it is portable threshold evidence that narrows what later views may safely forget.

22

Alternative legitimacy carriers. The appendix shows that legitimacy need not always be a fixed validator-set quorum certificate. Stellar derives quorum evidence from local quorum slices. Algorand uses VRF-selected committees. Ouroboros uses stake-weighted leader evidence and chain stability. GRANDPA and Casper FFG overlay finality votes on a block tree or checkpoint tree. Avalanche and Snowman accumulate sampled preference evidence until a choice becomes stable enough to expose. Semantic closure. CBC Casper states the collapse condition most directly. A protocol state is a justified message carrier, and a decision is safe only when the estimator is invariant over all admissible future states. In this family, the horizon is not just a round or view. It is an analysis of future extensions of the carrier. DAG interpretation. Cordial Miners and Mysticeti-C make the modern DAG/blocklace version of the carrier explicit in the main text. Cordial Miners walks backward from final leaders through a blocklace. Mysticeti-C classifies proposer slots with direct and indirect horizons. The appendix adds DAG-Rider, Hashgraph, Aleph, and Narwhal/Tusk/Bullshark as broader instances. These protocols differ in commit rules, but they share the same semantic move: preserve a partial order long enough for a later local interpretation to emit a prefix.

8.2

Cordial Miners and Mysticeti-C

Cordial Miners and Mysticeti-C are especially close in the collapse view. Both use later partially ordered communication evidence to resolve earlier ordering ambiguity. In Cordial Miners, a later super-ratified leader anchors finality, and the ordering function τ walks backward through ratified structure. In Mysticeti-C, later anchor evidence, causal links, and implicit certificate patterns can indirectly decide earlier slots when the direct rule is insufficient. Their difference is the granularity of collapse: • Cordial Miners: sparse wave-anchor collapse. If a final leader exists, a fragment is finalized; if no final leader exists, ordering is deferred. • Mysticeti-C: pipelined slot-frontier collapse. Each slot may be classified as to-commit, to-skip, or undecided, and the output frontier advances until the first undecided slot. Thus Mysticeti-C can be read as a finer-grained slot-level analogue of the same backwardevidence pattern, with two extra collapse controls. Multiple proposer/leader slots per round densify the evidence horizon, and the skip rule supplies a negative decision that Cordial Miners does not expose at the same per-slot level. Pipeline overlap then turns these slot decisions into a continuous frontier, analogous in spirit to HotStuff’s pipelined QC chain but lifted into a DAG carrier. The apparent terminology gap is smaller than it looks. “Super-ratified leader,” “anchor,” “direct rule,” “indirect rule,” and “skip pattern” are different protocol terms for related choices about when later order-2 evidence is strong enough to settle earlier history, and whether failure to settle should produce deferral, skipping, or an undecided frontier.

8.3

Axes of difference

Where legitimacy lives. Legitimacy may be implicit in causality, as in Lamport ordering; reconstructed through relay or signatures, as in Byzantine Generals; supplied by majority intersection, as in Paxos and Raft; compressed into certificates, as in PBFT and HotStuff; derived from slices 23

or committee credentials, as in Stellar and Algorand; accumulated as confidence, as in Snowman; checked as estimator safety, as in CBC Casper; or read from DAG/blocklace structure, as in the DAG protocols. How wide the horizon is. Leader protocols tend to choose narrow horizons: a ballot, a term, a view, or a QC chain. DAG protocols often retain wider local visibility: waves, witness rounds, certified DAG windows, anchors, or blocklace waves. Wider horizons preserve more order-2 distinctions but usually increase dissemination, storage, or interpretation cost. When collapse is refused. The repair path is the clearest diagnostic of the chosen horizon. Paxos starts a higher ballot. Raft elects a new leader and repairs log suffixes. PBFT changes view. HotStuff rotates leaders and carries the highest QC. CBC Casper waits for more justified messages or fault evidence. DAG protocols keep extending the DAG, choose later waves, decide witness fame later, defer a final leader, or leave a Mysticeti slot undecided. What gets discarded. Every collapse hides distinctions. Logical clocks hide concurrency by imposing a total order. Paxos hides losing proposals. Raft hides failed leader histories and overwritten uncommitted suffixes. PBFT and HotStuff hide uncertified branches and timing histories. DAG protocols hide event/block concurrency once they expose a total order fragment. The question is not whether information is discarded, but whether the discarded distinctions can still affect the correctness property being claimed.

8.4

Communication Surface and Compression

The same collapse view also separates two quantities that are often conflated: how much order-2 evidence exists, and how expensively that evidence is disseminated. Full-gossip DAG surface. In the usual DAG style, each validator produces blocks or vertices and disseminates them broadly so that other validators can independently observe the causal structure. If n validators each broadcast to n validators in a round, the message surface is quadratic, O(n2 ), before counting payload size, signatures, or retransmission. The benefit is rich local visibility: each validator can interpret much of the DAG without relying on a single relay. Metric caveat. The asymptotic vocabulary in the literature is easy to misread because papers count different units. A DAG round may have an O(n2 ) message surface because O(n) validators each send to O(n) recipients, yet the amortized cost per block can be reported as O(n) because the round carries O(n) blocks. Hashgraph shifts much of the voting cost into local computation by gossiping the causal history from which virtual votes are computed [32]. Reliable Broadcast can add another layer: Cordial Miners notes that Bracha Reliable Broadcast has O(n2 ) message complexity per broadcast message, and that DAG-Rider and Bullshark use Reliable Broadcast as a building block [37]. Mysticeti-C states the tradeoff even more directly: it prioritizes low latency and DAG amortization while embracing a higher, cubic cost compared with linear-communication protocols [36]. Thus the precise claim is not that every DAG protocol has the same complexity, but that full local DAG visibility is bought by a broader communication surface unless the protocol compresses or relays evidence.

24

Leader/QC compression surface. HotStuff-style protocols compress evidence through a leader path [19]. Validators send votes to a leader or proposer, the leader aggregates them into a quorum certificate, and the certificate is broadcast back. With threshold signatures or compact aggregation, the message surface per step is linear, O(n): O(n) votes to the leader and O(n) dissemination from the leader. The semantic price is that visibility is leader-mediated. Evidence not carried by the leader path is not part of the immediate collapse horizon. DAGs can use the same compression. A DAG-shaped protocol is not forced to use full-gossip dissemination. It can choose a dissemination leader or relay for a round, slot, or wave. Validators send DAG blocks, references, votes, or availability evidence to that leader; the leader recomposes, certifies, or aggregates the evidence; and then broadcasts the compressed result to the rest of the validators. The resulting message count can be linear in n, much like HotStuff, while retaining a DAG-shaped object at the protocol boundary. But this is no longer the same semantic point as full-gossip DAG exposure. It is a leadercompressed DAG: • message count: can move from O(n2 ) broad dissemination toward O(n) leader relay; • evidence size: can be compressed by quorum certificates, threshold signatures, bitmaps, or aggregate availability witnesses; • visibility: becomes filtered through the leader or relay path; • risk: faulty, slow, or censoring leaders can hide or delay parts of the DAG unless fallback or view-change rules recover them; • semantic effect: the protocol preserves DAG syntax but moves its collapse horizon closer to a leader-mediated BFT design. Thus the main distinction is not “DAG versus linear BFT.” It is the degree and location of evidence compression before collapse. Full-gossip DAG protocols and leader/QC protocols sit near opposite ends of this spectrum, while many practical designs occupy intermediate points: they retain a DAG-shaped carrier, but vary how dissemination, visibility, anchors, certificates, relays, reputation, or leaders compress the evidence used for collapse.

8.5

Output-First and Communication-First Readings

The formal statements of the protocols are not at issue. The difference is the direction from which they are read. Output-first reading. From the output-first direction, each protocol appears to solve a different problem with different terminology: Paxos ballots, Raft terms, PBFT phases, Stellar quorum slices, HotStuff chains, Tendermint/Streamlet rounds, Algorand sortition committees, Ouroboros stable prefixes, GRANDPA and Casper FFG finality justifications, Avalanche/Snowman confidence thresholds, Jolteon/Ditto fallback, CBC Casper safety oracles, DAG waves, Hashgraph virtual voting, Aleph poset ordering, Cordial blocklace traversal, and Mysticeti direct and indirect rules. The common object is hidden because the analysis starts at the value or prefix.

25

Communication-first reading. From the communication-first direction, the protocols discussed here are variants of one normal form. They all ask: Given a growing communication carrier, when is enough evidence visible to safely stop preserving alternatives and emit an order-1 output? This question explains why fallback rules keep appearing. A fallback is not an accidental complication. It is evidence that the original horizon sometimes cannot support the requested collapse. Mysticeti as the diagnostic case. Mysticeti’s direct and indirect rules make the phenomenon explicit. The direct rule uses one visibility horizon. The indirect rule uses later anchor evidence. The undecided state marks the refusal to project a prefix across insufficient evidence. Thus the protocol itself reveals the order distinction: progress may require information not present in the direct rule’s chosen carrier.

9

Related Work and Positioning

Impossibility and progress assumptions. FLP gives the classical asynchronous crash-failure boundary for deterministic consensus [5]. Dwork, Lynch, and Stockmeyer show how partial synchrony changes the progress setting [11]. Chandra and Toueg introduce failure detectors as additional information that can make consensus solvable in asynchronous crash-failure systems [12]. Ben-Or, Rabin, Canetti–Rabin, and HoneyBadgerBFT show the randomized asynchronous lineage: progress is obtained not by timing assumptions, but by random choices, common coins, reliable broadcast, and asynchronous agreement structure [13, 14, 15, 16]. In this vocabulary, these works characterize when the terminal collapse rule can be required, expected, or made to terminate with probability one. Set agreement and topology. Chaudhuri’s set agreement exposes output width as a parameter: consensus is the k = 1 case, while k-set agreement permits bounded residual disagreement [6]. Borowsky–Gafni resilient simulation generalizes the obstruction through crash resilience [7]. Herlihy–Shavit and Saks–Zaharoglou give the topological form: protocol complexes record views/executions, task complexes record outputs, and solvability depends on an appropriate map between them [8, 9]. These works are the formal background for the carrier-to-output reading. Classical quorum/certificate protocols. Paxos, Raft, PBFT, HotStuff, Tendermint, Streamlet, Jolteon, and Ditto are not treated here as equivalent protocols. They differ in fault model, leader structure, view change, responsiveness, fallback path, and proof obligations [2, 3, 4, 17, 19, 20, 21, 23]. Their shared legitimacy backbone is quorum or certificate evidence: majority evidence in the crash-fault case, supermajority evidence in the Byzantine case, and corresponding threshold witnesses in optimized variants. The protocol-specific variation is how that evidence is carried, bounded by horizons, compressed, adapted, and projected into a terminal value, log position, or prefix. Federated and committee-selected quorums. Stellar and Algorand change how the quorum carrier is chosen [18, 22]. Stellar lets each participant choose quorum slices, so legitimacy is induced by overlapping local trust choices. Algorand uses VRF sortition to select committees privately for each agreement step, so eligibility evidence travels with the vote. Both still collapse communication 26

evidence to a value or block, but the legitimacy layer is no longer simply a fixed global validator quorum. Proof-of-stake chains and finality gadgets. Ouroboros, GRANDPA, and Casper FFG expose another split in the collapse-policy space [25, 26, 27, 28]. Ouroboros uses proof-of-stake leader election and chain selection to make a stable prefix meaningful under probabilistic/common-prefix security. GRANDPA takes a block tree from a separate production mechanism and applies weighted prevote/precommit evidence to finalize a prefix. Casper FFG uses source-target checkpoint votes and slashing conditions to justify and finalize checkpoints. In each case, the output is a prefix, but the evidence horizon differs: chain growth and stability in Ouroboros, round-local ancestry voting in GRANDPA, and checkpoint-link voting in Casper FFG. Metastable sampling. Avalanche and Snowman use repeated randomized sampling rather than quorum certificates, finality checkpoints, or DAG waves [29]. The carrier is a history of sampled preferences and confidence counters. Collapse happens when local confidence has accumulated enough support for a choice or chain prefix. The horizon is a confidence threshold over observations, not a fixed round, wave, or certificate depth. Estimator-based blockchain consensus. CBC Casper starts from protocol states, estimators, admissible futures, and safety of estimates [30]. Its blockchain instance uses GHOST as an estimator, but its finality condition is not simply “follow GHOST.” A block is finalized only when it is safe: compatible with the estimator over all admissible future protocol states under the fault threshold. The result is semantic closure rather than only a mechanism for reaching a prefix. DAG-based consensus and atomic broadcast. DAG-Rider, Hashgraph, Aleph, Narwhal/Tusk, Bullshark, Cordial Miners, and Mysticeti-C make communication history more explicit than singlechain protocols [31, 32, 33, 34, 35, 37, 36]. DAG-Rider separates reliable-broadcast DAG construction from local ordering. Hashgraph records gossip-about-gossip and computes votes virtually from the resulting event DAG. Aleph builds a partially ordered set and computes a common total-order extension with randomized asynchronous machinery. Narwhal separates dissemination/storage of causal transaction histories from ordering. Cordial Miners uses a blocklace for dissemination, equivocation exclusion, and ordering. Mysticeti-C exposes direct and indirect classification of slots. These protocols are the closest operational relatives of the collapse-policy view. Position of this paper. This paper is not a replacement for protocol-specific correctness proofs or performance analyses. It is a semantic comparison layer over them. Its normal form asks which evidence is retained, which horizon is inspected, which projection is emitted, and which repair path exists when the horizon is insufficient.

10

Discussion

The collapse view does not imply that all protocols are equally good. It gives a better basis for comparing them. • A protocol may be faster because it collapses earlier. • A protocol may be safer under equivocation because it preserves more causal evidence. 27

• A protocol may reduce communication by compressing evidence through leaders or quorum certificates. • A protocol may improve liveness by adding randomness, timing assumptions, or deferral rules. • A protocol may look DAG-like syntactically while semantically behaving like leader-mediated evidence compression. These are different achievements. Calling all of them “consensus improvements” hides the tradeoff. The normal form separates them: legitimacy, horizon, compression, collapse, and repair. Leader compression. Leader-based protocols often reduce communication surfaces by concentrating evidence flow. That is not merely an engineering optimization. It changes which participants see which order-2 distinctions before collapse. A leader can coordinate a prefix cheaply, but the price is stronger dependence on leader-mediated visibility. DAG exposure. DAG-based protocols preserve more communication history explicitly. That can make local interpretation cheaper once evidence is visible, and can support later fallback rules that read causal structure not available to shorter horizons. The price is usually larger dissemination, storage, or verification surface. Design implication. Protocol specifications and comparisons benefit from stating the collapse policy explicitly: what evidence makes communication decision-grade, what history is retained, what horizon is inspected, what distinctions are discarded at output, and what repair rule applies when the horizon is insufficient.

11

Future Work

The collapse-policy view also suggests a design space for new protocols. Instead of beginning with a fixed message pattern or commit rule, a protocol can begin by choosing its communication carrier H, then choosing legitimacy L, horizon R, collapse C, and repair/deferral rules. One direction is adaptive horizons: collapse early when the carrier contains clean decision-grade evidence, widen the horizon when ambiguity or equivocation remains, and leave explicit collapse debt when neither positive nor negative collapse is justified. Another is carrier-preserving finality, where the protocol finalizes a causally closed subhistory and exposes a linear prefix only as a projection. A third is leader-compressed DAG design: retain a DAG-shaped semantic carrier while using quorum certificates, threshold aggregation, or relays to reduce the communication surface. These directions treat protocol design as semantic resource management. The resources are not only messages, signatures, and latency, but also preserved distinctions, visible evidence, and valid points of collapse.

12

Conclusion

Consensus protocols are usually described by their final artifact. This paper describes them by the semantic operation that produces that artifact: lawful collapse of a communication carrier into a value, log, or prefix. The resulting picture is more uniform than the protocol vocabulary suggests. Lamport clocks, Byzantine oral/signed reports, Paxos ballots, Raft terms, PBFT phases, Stellar quorum slices, 28

HotStuff quorum-certificate chains, Tendermint/Streamlet rounds, Algorand committee certificates, Ouroboros stable-prefix rules, GRANDPA and Casper FFG finality justifications, Avalanche/Snowman confidence thresholds, Jolteon/Ditto fallback, CBC Casper safety oracles, DAG-Rider waves, Hashgraph virtual voting, Aleph poset ordering, Cordial Miners ratification, and Mysticeti direct/indirect rules are read here as managing related versions of the same underlying problem: when does a growing order-2 communication carrier contain enough decision-grade evidence for safe projection to an order-1 output? This does not refute FLP and does not introduce a new impossibility theorem. It relocates the insight. FLP constrains deterministic guaranteed terminal collapse under full asynchrony and one crash failure. Chaudhuri, Borowsky–Gafni, and topological distributed computing show that the obstruction scales: the issue is not merely one binary decision, but the relationship between adversarially preserved alternatives and the width/topology of the output carrier. The collapse view explains why practical protocols keep adding horizons, certificates, leaders, randomness, timeouts, anchors, waves, and fallback rules: they are mechanisms for deciding when history is allowed to stop mattering. The practical consequence is a specification method. Instead of asking only which protocol agrees fastest, we should ask what evidence it accepts, what history it preserves, what it compresses, when it collapses, and how it repairs insufficient evidence. Nontrivial distributed consensus protocols decide when a growing communication carrier contains enough evidence to project safely to a value, log, or prefix.

Acknowledgments I thank Ehud Shapiro for correspondence regarding Cordial Miners and its relation to Mysticetistyle DAG consensus, and Kushal Babel for clarifying the role of the direct and indirect rules in Mysticeti. Any remaining errors or interpretations are my own.

A

Broader Protocol Instantiations

The main text develops the semantic argument through cases that expose distinct roles: causal projection, carrier enrichment, quorum recovery, certificate compression, admissible-future safety, and DAG collapse debt. The following entries are not secondary in protocol importance. They are secondary in the proof strategy: they instantiate the same normal form across a broader protocol landscape once the denotational reading has been established. The appendix entries are schematic normal-form readings, not standalone correctness proofs of the protocols.

A.1

HoneyBadgerBFT and randomized asynchronous agreement

Randomized asynchronous agreement changes the progress side of the collapse policy without adding timing assumptions. Ben-Or’s protocol uses private random choices to prevent the adversary from deterministically preserving bivalence forever [13]. Rabin’s Byzantine agreement and Canetti–Rabin’s optimally resilient asynchronous Byzantine agreement strengthen this line with shared/random-coin machinery and cryptographic structure [14, 15]. HoneyBadgerBFT provides the concrete ACS/batch carrier: encrypted inputs are reliably broadcast, binary agreement and a common coin choose the batch, and threshold decryption opens only the selected outputs [16].

29

Protocol vocabulary. Epoch, encrypted input, reliable broadcast, binary agreement, common coin, ACS instance, decryption share, batch. Collapse-policy specification. HHB

:

EHB

:

VHB PHB

: :

enc. inputs, RBC transcripts, BA messages, coins, decryption shares RBC outputs, BA decisions, coin/decryption evidence one epoch’s ACS/decryption horizon ordered transaction batch

LHB (h) := {(i, x) | RBCi delivers x in h} RHB,e (a) := {(i, ( x) ∈ a | BAe (i) = 1} order(decrypt(u)) if decryption shares are valid, CHB (u) := undefined otherwise.

Protocol reading. Reliable broadcast makes encrypted inputs available, binary agreement/ACS chooses which inputs enter the epoch batch, and threshold decryption opens only the selected batch. The common coin is not a terminal output; it is repair evidence for making the ACS horizon progress in asynchrony. Comparative reading.

In the normal form:

• carrier: encrypted inputs, reliable-broadcast delivery evidence, binary-agreement messages, coin shares, and decryption shares; • legitimacy: reliable-broadcast delivery, ACS agreement evidence, and valid threshold decryption shares; • horizon: one epoch’s ACS instance and decryption step; • collapse: decrypt and order the ACS-selected inputs as a batch; • discarded distinctions: inputs not selected for the epoch and schedules that did not affect the ACS output; • repair mechanism: common-coin and repeated asynchronous agreement steps until ACS completes. The broader Ben-Or/Rabin/Canetti–Rabin lineage explains why this progress path works: randomness prevents the adversary from deterministically preserving the same ambiguity forever. The HoneyBadger-style spec above keeps the carrier concrete.

A.2

Raft

Raft makes the leader path explicit. A leader in term T wants to commit log index j. The carrier contains RequestVote evidence, AppendEntries messages, follower logs, match indices, current terms, and commit indices. The legitimacy condition is majority election plus majority replication. Election restriction and log matching ensure that later leaders cannot safely overwrite committed entries. 30

The horizon is the leader’s current term, its local log, and the follower match-index frontier it learns from AppendEntries responses. When a log entry is replicated on a majority under Raft’s rules, the leader may advance the commit index. If a leader fails, a new election reestablishes the evidence horizon; if a follower has a conflicting suffix, AppendEntries conflict repair overwrites uncommitted suffixes while preserving the committed prefix. That is the collapse policy in concrete form. Protocol vocabulary. index, commit index.

Term, RequestVote, leader election, AppendEntries, follower log, match

Collapse-policy specification. HRaft

:

ERaft VRaft

: :

PRaft

:

terms, votes, AppendEntries, logs, match indices, commit indices majority election and replication evidence current-term leader horizon and match-index frontier committed prefix

LRaft (h) := {(i, j, T ) | follower i stores log index j in term T in h} RRaft,T (e) := {(i, j, T ′ ) ∈ e | T ′ = T and i is visible to the leader} CRaft (v) := max{j | |{i | (i, j, T ) ∈ v}| is a majority}.

Protocol reading. The term and match-index frontier are the visible cut, the commit index is the collapse point, and conflict repair only touches uncommitted suffixes. Comparative reading. Raft reorganizes the Paxos lineage around understandability by separating leader election, log replication, and safety [4]. Its terminal output is a replicated log, and its communication carrier is deliberately structured around terms and a leader-maintained prefix. In the normal form: • carrier: terms, votes, AppendEntries messages, replicated log entries, commit indices, and leader-election evidence; • legitimacy: majority election and majority replication; • horizon: current term, leader log, and follower match indices; • collapse: a leader commits a log entry once it is replicated on a majority under Raft’s safety rules; • discarded distinctions: concurrent client requests, failed leader proposals, and overwritten uncommitted suffixes; • repair mechanism: election restriction, log matching, leader completeness, and conflict repair in AppendEntries. Raft makes leader-mediated collapse explicit. It narrows the communication carrier so that one leader orders commands into a log, while majority evidence protects already-committed prefixes across leader changes.

31

A.3

PBFT

PBFT fixes a request m and sequence number n inside a view v. The carrier contains the primary’s pre-prepare, prepare votes, commit votes, checkpoints, and any view-change evidence. The legitimacy relation is Byzantine quorum evidence over the same request and sequence number. The horizon is the current view’s pre-prepare/prepare/commit phase sequence. Once enough prepare and commit evidence is visible, the protocol collapses the phase history into a committed log position. If the primary is faulty or the view stalls, replicas do not throw away the safety evidence. They move it into the next view through view change, carrying prepared certificates and checkpoints so that a conflicting request cannot be safely committed later. The repair path is therefore explicit state transfer across views. Protocol vocabulary. prepared certificate.

Primary, view, pre-prepare, prepare, commit, checkpoint, view change,

Collapse-policy specification. HPBFT

:

EPBFT

:

VPBFT PPBFT

: :

pre-prepare, prepare, commit, checkpoint, and view-change messages Byzantine quorum evidence for request/sequence pairs current-view phase horizon committed log position

LPBFT (h) := {(r, n, v, ϕ) | ϕ ∈ {preprepare, prepare, commit} appears in h} RPBFT,v (e) := {(r, n, v ′ , ϕ) ∈ e | v ′ = v} CPBFT (u) := {(r, n) | u contains sufficient prepare and commit evidence for (r, n)}.

Protocol reading. The phase history is the carrier, quorum evidence is the legitimacy layer, the current view is the horizon, and view change preserves prepared evidence across views. Comparative reading. PBFT-style protocols use a primary/view structure and phase certificates to commit sequence numbers [17]. In the normal form: • carrier: requests, pre-prepare messages, prepare votes, commit votes, checkpoints, view-change evidence; • legitimacy: quorum evidence over a request and sequence number; • horizon: the current view and its pre-prepare/prepare/commit phases; • collapse: a commit certificate projects the phase history into a log position; • discarded distinctions: competing proposals, alternate request orderings, and timing histories that did not enter the committed certificate; • repair mechanism: view change carries enough evidence to preserve safety when the current primary or horizon fails. PBFT therefore does not merely “agree on a value.” It constructs a bounded evidence horizon and collapses that horizon into an order-1 log position once the phase evidence is sufficient.

32

A.4

Stellar

The Stellar Consensus Protocol changes where quorum legitimacy lives [18]. Classical BFT protocols usually assume a globally known validator set and fixed quorum threshold. Stellar uses federated Byzantine agreement: each node chooses quorum slices, and system-level quorums arise from overlapping local trust choices. The carrier therefore includes not only votes and nominations, but also the quorum-slice structure needed to decide whether those statements count as quorum evidence at all. Protocol vocabulary. Federated Byzantine agreement, quorum slice, quorum, nomination, ballot, prepared, committed, externalized value. Collapse-policy specification. HSCP

:

ESCP

:

VSCP

:

PSCP

:

statements, nominations, ballots, quorum slices, local node views federated quorum evidence and blocking-set evidence for statements local ballot horizon with visible quorum-slice structure externalized value for a slot

LSCP (h) := {(q, x) | q is a quorum under the slice relation in h and supports statement x} RSCP,b (e) := ( {(q, x) ∈ e | x is visible in ballot horizon b} x if u justifies externalizing value x, CSCP (u) := undefined otherwise.

Protocol reading. Quorum slices are part of the communication carrier because they determine which sets of statements count as legitimate evidence. Nomination proposes candidate values, the ballot protocol refines them, and externalization is collapse to the value supported by sufficient federated quorum evidence. Comparative reading.

In the normal form:

• carrier: node statements, quorum slices, nominations, ballots, prepared/committed evidence, and local views; • legitimacy: quorum and blocking-set evidence induced by participant-chosen quorum slices; • horizon: the local ballot state and visible slice-derived quorum structure; • collapse: externalize a value when federated quorum evidence makes it safe; • discarded distinctions: unsuccessful nominations, losing ballots, and local trust alternatives not reflected in the externalized value; • repair mechanism: continue nomination/ballot progression until federated quorum evidence closes over a value. Stellar makes the legitimacy relation visible inside the carrier. Collapse still emits an order1 value, but a reader cannot judge the supporting votes without also reading the quorum-slice network that turns local trust choices into federated quorum evidence. 33

A.5

Tendermint

Tendermint sits close to PBFT and HotStuff in the collapse-policy map. Its height/round structure gives a compact blockchain instance of the same design: within one height, each round has a proposer, prevote/precommit evidence, and lock state that determines whether a block can become part of the committed chain [20]. Protocol vocabulary. ted block.

Height, round, proposer, prevote, precommit, lock, valid value, commit-

Collapse-policy specification. HTendermint

:

ETendermint

:

VTendermint PTendermint

: :

proposals, prevotes, precommits, locks, valid values, height/round state quorum prevote/precommit evidence for a block at a height current height and round-local vote horizon committed block for a height

LTendermint (h) := {(b, r, ϕ) | ϕ ∈ {prevote, precommit} has quorum support for b in round r} ′ ′ RTendermint,r (e) := {(b, ( r , ϕ) ∈ e | r = r and ϕ is visible at the current height} b if u contains quorum precommit evidence for b, CTendermint (u) := undefined otherwise.

Protocol reading. The height and round provide the visibility horizon, prevotes and precommits provide legitimacy, and locks preserve earlier evidence across later proposer attempts. Comparative reading.

In the normal form:

• carrier: proposed blocks, prevotes, precommits, locks, valid values, and height/round state; • legitimacy: Byzantine quorum prevote/precommit evidence; • horizon: one height and round; • collapse: commit a block for the height when quorum precommit evidence is visible; • discarded distinctions: losing proposals, skipped leaders, and non-finalized forks; • repair mechanism: move to later rounds while preserving lock and valid-value evidence. Tendermint is a clean round-local horizon case. The relevant cut is not just “a round” in the abstract; it is the current height and round together with the prevote/precommit evidence and lock state carried from earlier rounds.

A.6

Streamlet

Streamlet gives a streamlined pedagogical form of notarized-chain finality [21]. The carrier is a block tree with votes and notarizations. Collapse occurs when a short chain of notarized blocks satisfies the finalization rule. Protocol vocabulary.

Epoch, leader, vote, notarized block, notarized chain, finalized block. 34

Collapse-policy specification. HStreamlet

:

EStreamlet VStreamlet PStreamlet

: : :

block tree, epoch leaders, votes, notarizations, and ancestry notarized block evidence notarized-chain horizon finalized block prefix

LStreamlet (h) := {(b, e) | b has quorum votes and is notarized in epoch e} RStreamlet,e (a) := {(b, e′ ) ∈ a | e′ ≤ e and b lies on a visible notarized chain} CStreamlet (u) := {b | u contains a notarized-chain pattern finalizing b}.

Protocol reading. Votes produce notarizations, notarizations form the visible chain horizon, and the finalization rule collapses a notarized-chain pattern into a finalized prefix. Comparative reading.

In the normal form:

• carrier: block tree, epoch leaders, votes, notarizations, and ancestry; • legitimacy: quorum notarization for a block; • horizon: a short visible chain of notarized blocks; • collapse: finalize the block justified by the notarized-chain rule; • discarded distinctions: losing leader proposals and non-notarized forks; • repair mechanism: continue epochs until the notarized-chain horizon satisfies finalization. Streamlet expresses the same notarized-chain pattern with a short chain rule: votes produce notarizations, and a brief notarized chain is enough to finalize a prefix.

A.7

Algorand

Algorand uses cryptographic sortition to choose small committees for Byzantine agreement on each block [22]. The communication carrier therefore includes not only proposals and votes, but also verifiable random function evidence showing that a participant was eligible to speak in a particular step. Collapse is mediated by committee certificates rather than a fixed all-validator quorum. Protocol vocabulary. vote, block certificate.

VRF sortition, committee, credential, proposer, BA step, soft vote, certify

Collapse-policy specification. HAlgorand

:

EAlgorand

:

VAlgorand PAlgorand

: :

block proposals, VRF credentials, committee votes, steps, certificates eligible committee votes with valid sortition evidence round and BA-step committee horizon certified block for a round

LAlgorand (h) := {(v, b, s, c) | c proves voter v is eligible in step s and votes for b} RAlgorand,r,s (e) := ( {(v, b, s′ , c) ∈ e | s′ = s and the vote belongs to round r} b if u contains sufficient eligible committee votes certifying b, CAlgorand (u) := undefined otherwise.

35

Protocol reading. VRF credentials make committee membership portable evidence. The round and step define the horizon, committee votes supply decision-grade evidence, and certification collapses the visible committee history into a block decision. Comparative reading.

In the normal form:

• carrier: proposed blocks, VRF credentials, committee votes, BA steps, and certificates; • legitimacy: valid sortition evidence and sufficient eligible committee support; • horizon: one round and its BA-step committee views; • collapse: certify one block for the round and extend the prefix; • discarded distinctions: non-selected users, losing proposals, and committee votes outside the certified block path; • repair mechanism: advance BA steps or rounds when the current committee horizon does not certify a block. Algorand shifts the carrier into privately selected committees. Instead of routing evidence through a stable leader or broad validator set, the protocol carries eligibility proof with each vote and collapses each BA step through committee certificates.

A.8

Ouroboros

Ouroboros is the proof-of-stake longest-chain branch of the blockchain consensus lineage [25, 26]. It does not expose finality through the same immediate quorum-certificate interface as HotStuff or Tendermint. Instead, slot leaders extend a block tree, validators apply a chain-selection rule, and the stable prefix of the selected chain becomes the terminal artifact. Protocol vocabulary. Slot, epoch, stake distribution, slot leader, leader eligibility, block tree, chain-selection rule, stability parameter, common prefix. Collapse-policy specification. HOuroboros

:

EOuroboros

:

VOuroboros POuroboros

: :

slot-indexed block tree, leader evidence, stake distribution, local chain views valid blocks with eligible-leader and ancestry evidence locally selected best chain with a stability window stable chain prefix

LOuroboros (h) := {b ∈ blocks(h) | b has valid slot, leader, stake, and parent evidence in h} ROuroboros,k (e) := bestChain(e) together with the k-slot or k-block stability horizon COuroboros,k (v) := prefixk (v),

where prefixk (v) means the selected chain with its unstable suffix removed. Protocol reading. The block tree is the carrier, leader eligibility and block validity supply legitimacy, the chain-selection rule chooses the visible chain, and the stability parameter determines which prefix is old enough to expose as final for the protocol’s security claim. 36

Comparative reading.

In the normal form:

• carrier: slot-indexed block tree, stake distribution, leader evidence, block headers, and local chain views; • legitimacy: valid leader election or eligibility evidence, valid ancestry, and stake assumptions; • horizon: chain-selection view plus a stability window; • collapse: expose the stable prefix of the selected chain; • discarded distinctions: losing forks, withheld blocks, and unstable suffix alternatives outside the stable prefix; • repair mechanism: continue extending the block tree and recompute the selected chain until the common-prefix horizon makes earlier blocks stable. Ouroboros makes stable-prefix projection explicit over a stake-selected chain/tree. It does not require every block to carry a direct finality certificate; instead, the selected chain is exposed through a stability window under the protocol’s stake and synchrony assumptions.

A.9

GRANDPA

GRANDPA is a finality gadget: it finalizes prefixes of a block tree produced by an underlying block-production mechanism [27]. Its communication carrier is not just the produced chain. It includes validator prevotes, precommits, rounds, and ancestry relations, so votes for descendants also count as evidence for ancestors. Protocol vocabulary. Finality gadget, round, prevote, precommit, estimate, block tree, ancestry, supermajority, justification, finalized prefix. Collapse-policy specification. HGRANDPA

:

EGRANDPA

:

VGRANDPA PGRANDPA

: :

block tree, rounds, prevotes, precommits, voter weights, ancestry weighted vote evidence over blocks and descendants round-local vote graph projected through ancestry finalized block prefix

LGRANDPA (h) := {(v, b, ϕ, r) | v casts valid ϕ ∈ {prevote, precommit} for b in round r} RGRANDPA,r (e) :=  {(v, b, ϕ, r′ ) ∈ e | r′ = r and b is interpreted through block ancestry}  if b is the highest block justified by b CGRANDPA (u) := supermajority precommit evidence in u,   undefined otherwise.

Protocol reading. GRANDPA separates block production from finality. The block tree supplies the candidate carrier, validator votes supply decision-grade evidence, ancestry lifts votes on descendants to support ancestors, and a round finalizes the highest block whose prefix is justified by sufficient precommit evidence.

37

Comparative reading.

In the normal form:

• carrier: block tree, validator votes, rounds, weights, ancestry, and finality justifications; • legitimacy: weighted supermajority prevote/precommit evidence; • horizon: a GRANDPA round and the ancestry closure of votes in that round; • collapse: finalize the highest block whose prefix is justified by supermajority precommit evidence; • discarded distinctions: competing block-tree branches outside the finalized prefix; • repair mechanism: move to later rounds with updated estimates when the current round cannot justify a new prefix. GRANDPA leaves block production as the source of candidate history and uses weighted prevote/precommit evidence to decide when a prefix of that history can stop being provisional.

A.10

Casper FFG

Casper the Friendly Finality Gadget is another overlay finality mechanism [28]. It organizes finality around checkpoint votes. Validators vote for source-target checkpoint links, and justified checkpoints can become finalized when later votes extend them in the required way. The carrier is therefore a checkpoint tree plus validator votes and slashing-relevant evidence. Protocol vocabulary. Checkpoint, epoch, source, target, vote, justification, finalization, slashing condition, validator deposit. Collapse-policy specification. HFFG

:

EFFG

:

VFFG PFFG

: :

checkpoint tree, source-target votes, validator weights, slashing evidence weighted checkpoint-link evidence and justified-checkpoint evidence epoch-local checkpoint horizon finalized checkpoint prefix

LFFG (h) := {(v, s, t) | v casts a valid vote from source checkpoint s to target t} RFFG,e (x) := {(v, ( s, t) ∈ x | t is visible in epoch horizon e} t if u justifies and finalizes checkpoint t, CFFG (u) := undefined otherwise.

Protocol reading. Checkpoint votes are the communication evidence, stake weight supplies legitimacy, and slashing conditions make conflicting evidence costly. Collapse happens when the checkpoint graph contains enough weighted votes to justify and then finalize a checkpoint prefix. Comparative reading.

In the normal form:

• carrier: checkpoint tree, validator votes, source-target links, stake weights, and slashing evidence; • legitimacy: weighted supermajority votes respecting slashing conditions; 38

• horizon: an epoch-local view of justified checkpoints and target votes; • collapse: finalize a checkpoint and expose the prefix below it; • discarded distinctions: competing checkpoint branches and votes outside the finalized prefix; • repair mechanism: continue voting in later epochs until checkpoint evidence justifies and finalizes a prefix. Casper FFG separates block production from finality through checkpoint links and slashingaware validator votes. Its collapse horizon is a checkpoint tree rather than GRANDPA’s round-local prevote/precommit ancestry rule.

A.11

Snowman and Avalanche

Avalanche-style consensus uses repeated random sampling to drive local preferences into a metastable common choice [29]. Snowman specializes the family to a linear-chain setting. The communication carrier is a sequence of sampled preference observations and confidence counters for competing chain choices, and the chain choice becomes stable once the confidence threshold is met. Protocol vocabulary. Repeated sampling, preference, query, response, confidence counter, metastability, block conflict, Snowman chain. Collapse-policy specification. HSnowman

:

ESnowman

:

VSnowman PSnowman

: :

block proposals, sampled responses, preferences, conflicts, ancestry, confidence counters sample-majority evidence for a block or chain extension local sampling window for a conflicting block choice accepted chain prefix

LSnowman (h) := {(b, m) | m is sampled support for block b or its chain ancestry in h} RSnowman,β (e) := ( {(b, m) ∈ e | b has visible sample support contributing to confidence threshold β} b if b reaches the required confidence threshold in u, CSnowman (u) := undefined otherwise.

Protocol reading. Sampling responses are the evidence carrier. The horizon is not a view, round certificate, or finality checkpoint, but a confidence threshold over repeated local observations for a conflicting block choice. Collapse occurs when one block preference has accumulated enough sampled support to extend the accepted chain prefix. Comparative reading.

In the normal form:

• carrier: sampled queries and responses, block preferences, conflict sets, confidence counters, and chain ancestry; • legitimacy: sample-majority support under Snowman’s sampling and adversary assumptions; • horizon: a local confidence window and threshold for a block choice; • collapse: accept a chain extension once confidence is high enough; 39

• discarded distinctions: losing block preferences and sampled histories that no longer affect the accepted prefix; • repair mechanism: continue sampling until confidence accumulates or preferences shift. Snowman and the broader Avalanche family use repeated randomized sampling instead of quorum intersection, certificate chains, or finality votes. The carrier grows as sampled observations update local preference and confidence order; collapse happens when that order has a stable maximal choice.

A.12

Jolteon and Ditto

Jolteon and Ditto sharpen the HotStuff lineage by making network adaptation explicit. Jolteon optimizes the fast path under favorable network behavior, while Ditto adds an asynchronous fallback path when the optimistic path cannot safely make progress [23]. Protocol vocabulary. Fast path, fallback path, proposal, vote, quorum certificate, timeout certificate, view, certified chain. Collapse-policy specification. HJD

:

EJD VJD PJD

: : :

proposals, votes, QCs, timeout/fallback evidence, block ancestry certified proposal-chain and fallback evidence optimistic view horizon or asynchronous fallback horizon committed block prefix

LJD (h) := {(b, q) | q is a QC, timeout certificate, or fallback certificate for b in h} RJD,v (e) :=  {(b, q) ∈ e | (b, q) is visible to the fast path or fallback path in view v}  if u satisfies the optimistic commit rule, commitFast(u) CJD (u) := commitFallback(u) if u satisfies the fallback commit rule,   undefined otherwise.

Protocol reading. The fast path uses a narrow leader/view horizon when timely evidence is available. The fallback path widens or changes the horizon when the optimistic collapse rule cannot safely produce a prefix. Comparative reading.

In the normal form:

• carrier: proposals, votes, quorum certificates, timeout/fallback evidence, and block ancestry; • legitimacy: quorum certificates and fallback certificates that carry decision-grade evidence across views; • horizon: the optimistic leader/view path when timely, or the fallback horizon when synchrony assumptions are not currently useful; • collapse: the fast path commits through certified chains when the network cooperates; • discarded distinctions: failed fast-path attempts and uncertified branches once a fallback or later certified path commits; 40

• repair mechanism: asynchronous fallback preserves progress when the short optimistic horizon is insufficient. Jolteon/Ditto makes horizon selection adaptive. The protocol does not choose once between “synchronous” and “asynchronous” consensus. It changes the collapse policy depending on whether the fast horizon currently carries enough evidence.

A.13

DAG-Rider

DAG-Rider first builds a reliable-broadcast DAG and then interprets it in waves. The carrier is the local DAG of reliably broadcast vertices, round edges, and parent references. The legitimacy relation is reliable-broadcast validity plus sufficient round support, typically a threshold-sized set of vertices. The horizon is the wave: a bounded set of rounds used for local interpretation. The collapse step selects or interprets leaders in the wave and emits an ordered sequence. If the wave does not yield progress, the protocol does not discard the DAG carrier. Later waves and randomized leader selection are the repair path, providing expected progress while preserving already disseminated causal evidence. The DAG is not transport noise; it is the object the ordering rule reads. Protocol vocabulary.

Reliable broadcast, DAG, vertex, round, wave, leader selection.

Collapse-policy specification. HDAG-Rider

:

EDAG-Rider VDAG-Rider PDAG-Rider

: : :

reliable-broadcast DAG, vertices, rounds, parent references RB-valid vertices with threshold round support wave-local DAG evidence ordered output sequence

LDAG-Rider (h) := {x ∈ vertices(h) | x is RB-valid and threshold-supported} RDAG-Rider,w (e) := {x ∈ e | x lies in wave w} CDAG-Rider (u) := order(leaders(u), u).

Protocol reading. The DAG is the carrier, reliable-broadcast validity and round support are the legitimacy witnesses, the wave is the horizon, and later waves plus randomness serve as the repair path for progress. Comparative reading. DAG-Rider separates dissemination from ordering by first building a reliable-broadcast DAG and then locally interpreting the DAG in waves [31]. In the normal form: • carrier: a round-based DAG of reliably broadcast vertices; • legitimacy: sufficient round evidence, typically 2f + 1 vertices, and reliable broadcast validity; • horizon: waves over the DAG; • collapse: local wave interpretation and random leader selection produce a total order output; • discarded distinctions: DAG concurrency and unchosen wave alternatives after the output order is emitted;

41

• repair mechanism: randomized leader selection and later waves provide expected progress in asynchrony. DAG-Rider separates the two layers cleanly: build communication history first, interpret it second. The reliable-broadcast DAG is not a transport detail; it is the object read by the wave rule.

A.14

Hashgraph

Hashgraph builds a signed event DAG by gossip-about-gossip. Each event records transactions plus hashes of a self-parent and an other-parent, so the graph records the causal path by which gossip spread. The interpretation layer assigns rounds, identifies witnesses, decides witness fame by virtual voting, and then orders events by receipt round and consensus timestamp. The horizon is not a leader view or a fixed wave selected by an external coordinator. It is the witness-round evidence visible in the hashgraph. If a witness’s fame is not yet decided, the protocol does not force an order from the current cut. Later gossip extends the carrier, and later rounds provide the virtual-vote evidence needed to decide fame. Protocol vocabulary. Event, self-parent, other-parent, gossip-about-gossip, seeing, strongly seeing, witness, famous witness, virtual voting, consensus timestamp. Collapse-policy specification. signed events with self-parent and other-parent edges witness, seeing, strongly seeing, and fame evidence witness-round horizon used for virtual voting total order of events or transactions   {w ∈ events(h) | w is a witness}, LHashgraph (h) := {(x, w) | x strongly sees witness w in h} RHashgraph,r (e) := the witness evidence in and after round r used to decide fame CHashgraph (u) := order(famous(u), u). HHashgraph EHashgraph VHashgraph PHashgraph

: : : :

Protocol reading. The signed event DAG is the carrier, strongly seeing relations provide the supermajority evidence, witness rounds form the horizon, and virtual voting collapses the DAG into a total order once famous witnesses and receipt information are determined. Comparative reading. Hashgraph also makes communication history explicit, but with a different interpretation layer [32]. Participants gossip signed events, and each event names a self-parent and an other-parent. The resulting hashgraph records not only transactions, but who learned what from whom and when. Consensus is then computed by virtual voting over this shared causal structure rather than by sending separate vote messages. In the normal form: • carrier: signed hashgraph events with self-parent and other-parent edges, transactions, timestamps, and creator identities; • legitimacy: supermajority evidence expressed through seeing, strongly seeing, witnesses, and famous witnesses; • horizon: rounds of witnesses and later witness evidence used to decide fame; 42

• collapse: virtual voting decides famous witnesses, then receipt rounds and consensus timestamps produce a total order; • discarded distinctions: event-DAG concurrency and non-famous witness alternatives after the consensus order is emitted; • repair mechanism: continued gossip extends the hashgraph until later rounds contain enough virtual-vote evidence to decide fame and order. In Hashgraph, gossip-about-gossip builds an order-2 record of communication. Virtual voting reads that record as evidence and collapses it into an order-1 total order only after witness fame and receipt information are determined.

A.15

Aleph

Aleph is another explicit DAG/partial-order instance of the carrier/projection pattern [33]. It constructs a partially ordered set of units and then computes a common extension to a total order using local interpretation and randomized common-coin machinery. In this respect it connects Hashgraph’s gossip-about-gossip style with the later DAG-BFT protocols: the communication carrier is a partial order, and the terminal artifact is a linear order of messages or transactions. Protocol vocabulary. total-order extension.

Unit, partial order, fork, creator, level, common coin, randomness beacon,

Collapse-policy specification. HAleph EAleph

: :

VAleph PAleph

: :

units/messages with creator identities and dependency edges validated units, fork evidence, threshold support, randomness evidence locally visible poset layer plus coin evidence total order of units or transactions

LAleph (h) := {u ∈ units(h) | u is valid and not excluded by fork evidence in h} RAleph,ℓ (e) := {u ∈ e | u is visible in layer/horizon ℓ with the relevant coin evidence} CAleph (v) := extendOrder(v) when v determines the next common total-order fragment.

Protocol reading. The partial order of units is the carrier, validation and fork evidence determine admissible units, and common-coin evidence helps validators compute the same total-order extension from their local copies. Comparative reading.

In the normal form:

• carrier: units/messages arranged in a locally observed partial order, with creator identity and dependency edges; • legitimacy: validation of units, fork/equivocation checks, threshold support, and randomnessbeacon evidence; • horizon: locally visible layers of the partial order together with common-coin decisions used for ordering;

43

• collapse: a common deterministic interpretation, aided by randomness, extends the partial order into a total order; • discarded distinctions: concurrency among incomparable units after the final total order is emitted; • repair mechanism: continue extending the poset and invoking randomized ordering steps until enough common evidence is available. Aleph first builds an order-2 poset carrier and only later computes an order-1 atomic-broadcast sequence. Randomness helps local interpretations converge on the same extension when the asynchronous carrier has enough evidence.

A.16

Narwhal, Tusk, and Bullshark

Narwhal and Tusk split data availability and causal dissemination into a mempool layer. Bullshark keeps the DAG shape but adds deterministic commit rules under partial synchrony. The carrier is the certified DAG block graph: batches, certificates, and parent references. The legitimacy relation is certification of blocks and sufficient parent support, which makes data availability and ancestry portable. The horizon is a round or commit-rule window over certified DAG structure. Collapse maps the available DAG into ordered output, either through selected leaders, Tusk-style local interpretation, or Bullshark-style deterministic rules. If a block is available but not yet orderable, the protocol preserves it for later rules instead of forcing an early prefix decision. Dissemination and order are decoupled, but the DAG still carries the evidence that later ordering consumes. Protocol vocabulary. Narwhal, Tusk, Bullshark, mempool, data availability, causal histories, parent support, commit rules. Collapse-policy specification. HNTB

:

ENTB VNTB PNTB

: : :

certified DAG blocks, batches, causal references, mempool data block certificates and parent-support evidence round or commit-rule window ordered output

LNTB (h) := {b ∈ blocks(h) | b is certified and parent-supported} RNTB,w (e) := {b ∈ e | b is visible to commit window w} CNTB (u) := {b ∈ u | dagRule(u, b) orders b}.

Protocol reading. Dissemination and causal history are carried in the certified DAG, certification and parent support are the legitimacy witnesses, and the commit-rule window determines when preserved evidence becomes orderable. Comparative reading. Narwhal and Tusk separate the DAG mempool from consensus, making data availability and causal dissemination a first-class layer [34]. Bullshark continues the DAG-BFT line with deterministic commit rules under partial synchrony [35]. In the normal form: • carrier: certified DAG blocks carrying batches and references to prior blocks;

44

• legitimacy: certificates over DAG blocks and sufficient parent support; • horizon: rounds and commit rules over certified DAG structure; • collapse: selected leaders or commit rules map DAG availability into ordered output; • discarded distinctions: concurrent data availability relations once a final order is exposed; • repair mechanism: DAG accumulation lets later commit rules use evidence that was not ready at an earlier output point. For Narwhal, Tusk, and Bullshark, dissemination history is not mere transport. It is the certified DAG object from which ordering decisions are derived.

References [1] Leslie Lamport. Time, Clocks, and the Ordering of Events in a Distributed System. Communications of the ACM 21(7):558–565, 1978. DOI: https://doi.org/10.1145/359545.359563. URL: https://lamport.azurewebsites.net/pubs/time-clocks.pdf. [2] Leslie Lamport. The Part-Time Parliament. ACM Transactions on Computer Systems 16(2):133–169, 1998. DOI: https://doi.org/10.1145/279227.279229. [3] Leslie Lamport. Paxos Made Simple. ACM SIGACT News 32(4):51–58, 2001. URL: https: //lamport.azurewebsites.net/pubs/paxos-simple.pdf. [4] Diego Ongaro and John Ousterhout. In Search of an Understandable Consensus Algorithm. In Proceedings of the 2014 USENIX Annual Technical Conference, 2014. URL: https://www. usenix.org/conference/atc14/technical-sessions/presentation/ongaro. [5] Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson. Impossibility of distributed consensus with one faulty process. Journal of the ACM 32(2):374–382, 1985. DOI: https: //doi.org/10.1145/3149.214121. URL: https://groups.csail.mit.edu/tds/papers/ Lynch/jacm85.pdf. [6] Soma Chaudhuri. Agreement is harder than consensus: Set consensus problems in totally asynchronous systems. In Proceedings of the 9th Annual ACM Symposium on Principles of Distributed Computing, pages 311–324, 1990. DOI: https://doi.org/10.1145/93385.93428. [7] Elizabeth Borowsky and Eli Gafni. Generalized FLP impossibility result for t-resilient asynchronous computations. In Proceedings of the 25th Annual ACM Symposium on Theory of Computing, pages 91–100, 1993. DOI: https://doi.org/10.1145/167088.167119. [8] Maurice Herlihy and Nir Shavit. The topological structure of asynchronous computability. Journal of the ACM 46(6):858–923, 1999. DOI: https://doi.org/10.1145/331524. 331529. URL: https://www.cs.yale.edu/homes/aspnes/pinewiki/attachments/CS425% 282f%29Schedule/HerlihyShavit1999.pdf. [9] Michael Saks and Fotios Zaharoglou. Wait-free k-set agreement is impossible: The topology of public knowledge. In Proceedings of the 25th Annual ACM Symposium on Theory of Computing, pages 101–110, 1993. DOI: https://doi.org/10.1145/167088.167122.

45

[10] Leslie Lamport, Robert Shostak, and Marshall Pease. The Byzantine Generals Problem. ACM Transactions on Programming Languages and Systems 4(3):382–401, 1982. DOI: https:// doi.org/10.1145/357172.357176. [11] Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer. Consensus in the presence of partial synchrony. Journal of the ACM 35(2):288–323, 1988. DOI: https://doi.org/10.1145/ 42282.42283. URL: https://groups.csail.mit.edu/tds/papers/Lynch/jacm88.pdf. [12] Tushar Deepak Chandra and Sam Toueg. Unreliable failure detectors for reliable distributed systems. Journal of the ACM 43(2):225–267, 1996. DOI: https://doi.org/10.1145/226643. 226647. [13] Michael Ben-Or. Another Advantage of Free Choice: Completely Asynchronous Agreement Protocols. In Proceedings of the 2nd Annual ACM Symposium on Principles of Distributed Computing, pages 27–30, 1983. DOI: https://doi.org/10.1145/800221.806707. [14] Michael O. Rabin. Randomized Byzantine Generals. In Proceedings of the 24th Annual Symposium on Foundations of Computer Science, pages 403–409, 1983. DOI: https://doi.org/ 10.1109/SFCS.1983.48. [15] Ran Canetti and Tal Rabin. Fast Asynchronous Byzantine Agreement with Optimal Resilience. In Proceedings of the 25th Annual ACM Symposium on Theory of Computing, pages 42–51, 1993. DOI: https://doi.org/10.1145/167088.167105. [16] Andrew Miller, Yu Xia, Kyle Croman, Elaine Shi, and Dawn Song. The Honey Badger of BFT Protocols. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pages 31–42, 2016. DOI: https://doi.org/10.1145/2976749. 2978399. URL: https://eprint.iacr.org/2016/199. [17] Miguel Castro and Barbara Liskov. Practical Byzantine Fault Tolerance. In Proceedings of the 3rd Symposium on Operating Systems Design and Implementation, 1999. URL: https://www.usenix.org/conference/osdi-99/presentation/ practical-byzantine-fault-tolerance. [18] David Mazieres. The Stellar Consensus Protocol: A Federated Model for Internet-level Consensus. Stellar Development Foundation, 2015. URL: https://stellar.org/papers/ stellar-consensus-protocol.pdf. [19] Maofan Yin, Dahlia Malkhi, Michael K. Reiter, Guy Golan Gueta, and Ittai Abraham. HotStuff: BFT Consensus in the Lens of Blockchain. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, 2019. arXiv:1803.05069. URL: https: //arxiv.org/abs/1803.05069. DOI: https://doi.org/10.1145/3293611.3331591. [20] Jae Kwon. Tendermint: Consensus without Mining. Technical report, 2014. URL: https: //tendermint.com/static/docs/tendermint.pdf. [21] Benjamin Y. Chan and Elaine Shi. Streamlet: Textbook Streamlined Blockchains. In Proceedings of the 2nd ACM Conference on Advances in Financial Technologies, 2020. DOI: https://doi.org/10.1145/3419614.3423256. URL: https://eprint.iacr.org/2020/088. [22] Yossi Gilad, Rotem Hemo, Silvio Micali, Georgios Vlachos, and Nickolai Zeldovich. Algorand: Scaling Byzantine Agreements for Cryptocurrencies. In Proceedings of the 26th Symposium on 46

Operating Systems Principles, pages 51–68, 2017. DOI: https://doi.org/10.1145/3132747. 3132757. URL: https://eprint.iacr.org/2017/454. [23] Rati Gelashvili, Lefteris Kokoris-Kogias, Alberto Sonnino, Alexander Spiegelman, and Zhuolun Xiang. Jolteon and Ditto: Network-Adaptive Efficient Consensus with Asynchronous Fallback. In Financial Cryptography and Data Security, pages 296–315, 2022. DOI: https: //doi.org/10.1007/978-3-031-18283-9_14. arXiv:2106.10362v4. URL: https://arxiv. org/abs/2106.10362. [24] Dahlia Malkhi and Kartik Nayak. HotStuff-2: Optimal Two-Phase Responsive BFT. Cryptology ePrint Archive, Paper 2023/397, 2023. URL: https://eprint.iacr.org/2023/397. [25] Aggelos Kiayias, Alexander Russell, Bernardo David, and Roman Oliynykov. Ouroboros: A Provably Secure Proof-of-Stake Blockchain Protocol. In Advances in Cryptology – CRYPTO 2017, pages 357–388, 2017. DOI: https://doi.org/10.1007/978-3-319-63688-7_12. URL: https://eprint.iacr.org/2016/889. [26] Bernardo David, Peter Gazi, Aggelos Kiayias, and Alexander Russell. Ouroboros Praos: An Adaptively-Secure, Semi-synchronous Proof-of-Stake Blockchain. In Advances in Cryptology – EUROCRYPT 2018, pages 66–98, 2018. DOI: https://doi.org/10.1007/ 978-3-319-78375-8_3. URL: https://eprint.iacr.org/2017/573. [27] Alistair Stewart and Eleftherios Kokoris-Kogias. GRANDPA: a Byzantine Finality Gadget. arXiv:2007.01560, 2020. DOI: https://doi.org/10.48550/arXiv.2007.01560. URL: https: //arxiv.org/abs/2007.01560. [28] Vitalik Buterin and Virgil Griffith. Casper the Friendly Finality Gadget. arXiv:1710.09437, 2017. DOI: https://doi.org/10.48550/arXiv.1710.09437. URL: https://arxiv.org/ abs/1710.09437. [29] Team Rocket, Maofan Yin, Kevin Sekniqi, Robbert van Renesse, and Emin Gun Sirer. Scalable and Probabilistic Leaderless BFT Consensus through Metastability. arXiv:1906.08936, 2019. DOI: https://doi.org/10.48550/arXiv.1906.08936. URL: https://arxiv.org/ abs/1906.08936. [30] Vlad Zamfir. Casper the Friendly Ghost: A Correct-by-Construction Blockchain Consensus Protocol. Draft v0.1, Ethereum Foundation, 2017. URL: https://raw.githubusercontent. com/vladzamfir/research/master/papers/CasperTFG/CasperTFG.pdf. [31] Idit Keidar, Eleftherios Kokoris-Kogias, Oded Naor, and Alexander Spiegelman. All You Need is DAG. arXiv:2102.08325v2, 2021. URL: https://arxiv.org/abs/2102.08325. [32] Leemon Baird. The Swirlds Hashgraph Consensus Algorithm: Fair, Fast, Byzantine Fault Tolerance. Swirlds Technical Report SWIRLDS-TR-2016-01, 2016. URL: https://www.swirlds. com/downloads/SWIRLDS-TR-2016-01.pdf. [33] Adam Gagol, Damian Lesniak, Damian Straszak, and Michal Swietek. Aleph: Efficient Atomic Broadcast in Asynchronous Networks with Byzantine Nodes. In Proceedings of the 1st ACM Conference on Advances in Financial Technologies, pages 214–228, 2019. DOI: https://doi. org/10.1145/3318041.3355467. URL: https://arxiv.org/abs/1908.05156.

47

[34] George Danezis, Lefteris Kokoris-Kogias, Alberto Sonnino, and Alexander Spiegelman. Narwhal and Tusk: A DAG-based Mempool and Efficient BFT Consensus. In Proceedings of EuroSys 2022, 2022. arXiv:2105.11827v4. URL: https://arxiv.org/abs/2105.11827. DOI: https://doi.org/10.1145/3492321.3519594. [35] Alexander Spiegelman, Neil Giridharan, Alberto Sonnino, and Lefteris Kokoris-Kogias. Bullshark: DAG BFT Protocols Made Practical. arXiv:2201.05677v3, 2022. URL: https: //arxiv.org/abs/2201.05677. [36] Kushal Babel, Andrey Chursin, George Danezis, Anastasios Kichidis, Lefteris Kokoris-Kogias, Arun Koshy, Alberto Sonnino, and Mingwei Tian. Mysticeti: Reaching the Limits of Latency with Uncertified DAGs. arXiv:2310.14821v6, 2025. URL: https://arxiv.org/abs/2310. 14821. [37] Idit Keidar, Oded Naor, Ouri Poupko, and Ehud Shapiro. Cordial Miners: Fast and Efficient Consensus for Every Eventuality. In 37th International Symposium on Distributed Computing, LIPIcs 281:26:1–26:22, 2023. arXiv:2205.09174v6. URL: https://arxiv.org/abs/2205. 09174. DOI: https://doi.org/10.4230/LIPIcs.DISC.2023.26. [38] Paulo Sérgio Almeida and Ehud Shapiro. The Blocklace: A Byzantine-repelling and Universal Conflict-free Replicated Data Type. arXiv:2402.08068, 2024. URL: https://arxiv.org/abs/ 2402.08068.

48