Master Thesis
Gather
The Gather protocol, introduced by Canetti and Rabin [1] (see [6] for an accessible introduction), lets asynchronous processes assemble sets of values with a strong common-core guarantee: every non-faulty party outputs a set of values such that all these outputs contain a common core of at least n − t values. Unlike agreement on a core set (ACS) [2], the outputs need not be identical, and parties need not even know which values belong to the core. This relaxation is precisely what makes Gather attractive: ACS requires solving consensus, which is impossible deterministically in asynchrony and therefore needs randomization, terminating only in expected constant rounds. Gather, in contrast, is deterministic and terminates in a fixed constant number of rounds. This is also why a gather-like structure underlies each round of DAG-based consensus protocols such as DAG-Rider [3] and Bullshark [4].
Canetti and Rabin proved the correctness of the three-round gather protocol in the threshold setting, where any f < n/3 parties may be faulty, using an elegant combinatorial counting argument. In the asymmetric-trust setting, the same structure yields a protocol whose round complexity grows logarithmically in the number of parties [5].
In this thesis we study the Gather problem in the generalized symmetric setting, where trust is specified not by a threshold but by a Byzantine quorum system, or equivalently a general adversary structure satisfying the Q³ condition, in the sense of Malkhi and Reiter [7]. Concretely, the thesis will address the following questions:
Does the Canetti–Rabin structure yield a constant-round Gather protocol under generalized quorums, or does its round complexity degrade (e.g., to logarithmic, as in the asymmetric setting [5])? If the structure degrades, is there an alternative protocol that solves Gather in a constant number of rounds, or is a super-constant number of rounds inherent to the generalized setting?
Depending on progress and interest, natural extensions include verifiable or binding variants of Gather (the form actually needed for leader election in DAG-Rider-style protocols), the communication complexity of Gather under generalized quorums, and integrating the resulting primitive into a DAG-based consensus protocol with generalized trust, connecting back to [3–5].
References
[1] Fast Asynchronous Byzantine Agreement with Optimal Resilience
[2] Asynchronous secure computations with optimal resilience (extended abstract)
[4] Bullshark: DAG BFT Protocols Made Practical
[5] DAG-based Consensus with Asymmetric Trust
[6] Living with Asynchrony: the Gather protocol