The Control-History Cost of Exact DAG-Rider Delivery
Exact DAG-Rider delivery can require unbounded control history, even when only two batches carry transactions and the protocol keeps committing. At the cut, all correct replicas have both batches and the vertices that contain the recorded choices. A later reference to a stable slot selects one of $m$ bits from that history. A correct leader's commit then reveals the bit in the relative order of the two batches, and both come from a correct author. For each index, the ordinary continuation supplies identical inputs across prefixes, so exact delivery forces the correct replicas to retain $m$ bits between them. The probability of the required coin event is independent of $m$, and the argument holds for every sequence of earlier coin outcomes. We then require each author to link to its previous vertex. A table of first occurrences answers weak references of any age, and after a direct commit the collector retires all rounds through that wave without another agreement step. With a fixed committee and a bounded number of pending payloads, the state of the collector grows linearly with the uncommitted suffix, apart from identifier widths. We prove a matching lower bound for two payloads. Even a strong edge to the previous round can leak old order information when the child shows up late.
Authors
- Vera Plischke (ORCID: https://orcid.org/0009-0000-8411-6550)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-21
- DOI
- https://doi.org/10.5281/zenodo.24407067
- Primary Topic
- Distributed systems and fault tolerance
- Type
- preprint