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

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

The Control-History Cost of Exact DAG-Rider Delivery

Vera Plischke
Zenodo (CERN European Organization for Nuclear Research)
Distributed systems and fault tolerance
preprint

The Control-History Cost of Exact DAG-Rider Delivery

Vera Plischke
preprint en

Abstract

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.

Zenodo (CERN European Organization for Nuclear Research)
Distributed systems and fault tolerance
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon
The Control-History Cost of Exact DAG-Rider Delivery — Vera Plischke · Zenodo (CERN European Organization for Nuclear Research) (2026) | TGRS Research Map | TGRS