{"ID":2836584,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.21859","arxiv_id":"2511.21859","title":"Equivalence and Separation between Heard-Of and Asynchronous Message-Passing Models","abstract":"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 \u003e 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 \u003e 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.","short_abstract":"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 \u003e 2f$, the two models are equivalent w...","url_abs":"https://arxiv.org/abs/2511.21859","url_pdf":"https://arxiv.org/pdf/2511.21859v2","authors":"[\"Hagit Attiya\",\"Armando Castañeda\",\"Dhrubajyoti Ghosh\",\"Thomas Nowak\"]","published":"2025-11-26T19:35:34Z","proceeding":"cs.DC","tasks":"[\"cs.DC\"]","methods":"[]","has_code":false}