Hagit Attiya

Hagit Attiya, Itay Flam, Jennifer L. Welch

Canonical asynchronous rounds are a widely used abstraction for structuring distributed algorithms, making asynchronous executions appear synchronous and enabling modular reasoning. We show that this abstraction is fundamentally incompatible with optimal resilience in the Byzantine setting, even when randomization is allowed. Specifically, we prove that when $3f < n \le 5f$, where $n$ is the number of processes and at most $f$ may be Byzantine faulty, no randomized canonical-round algorithm can solve consensus with bounded expected round complexity, and that communication-closed variants fail to solve consensus altogether in this regime. We establish these lower bounds via a unifying notion of nontrivial convergence, which captures consensus as well as classical relaxations, such as approximate agreement and connected consensus. Using simple reductions, the same impossibility extends to fundamental communication primitives such as reliable broadcast and gather. Our results identify a sharp boundary: while bounded canonical-round algorithms for these problems exist when $n > 5f$, they cannot when $n \le 5f$. Thus optimal resilience, $n > 3f$, cannot be achieved within the canonical-round framework. On the positive side, we show that the gather primitive captures the content-dependent communication needed to bypass this limitation. We use gather to obtain a simple and modular algorithm for connected consensus with optimal resilience, clarifying the communication structures required for optimal resilience.

Hagit Attiya, Armando Castañeda, Dhrubajyoti Ghosh et al.

We revisit the relationship between two fundamental models of distributed computation: the asynchronous message-passing model with up to $f$ crash failures ($\operatorname{AMP}_f$) and the Heard-Of model with up to $f$ message omissions ($\operatorname{HO}_f$). We show that for $n > 2f$, the two models are equivalent with respect to the solvability of colorless tasks, and that for colored tasks the equivalence holds only when $f = 1$ (and $n > 2$). The separation for larger $f$ arises from the presence of silenced processes in $\operatorname{HO}_f$, which may lead to incompatible decisions. The proofs proceed through bidirectional simulations between $\operatorname{AMP}_f$ and $\operatorname{HO}_f$ via an intermediate model that captures this notion of silencing. The results extend to randomized protocols against a non-adaptive adversary, indicating that the expressive limits of canonical rounds are structural rather than probabilistic. Together, these results delineate precisely where round-based abstractions capture asynchronous computation, and where they do not.