We revisit the relationship between two fundamental models of distributed computation: the asynchronous message-passing model with up to f crash failures ( \(\textrm{AMP}_f\) ) and the Heard-Of model with up to f message omissions ( \(\textrm{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 \(\textrm{HO}_f\) , which may lead to incompatible decisions. The results are proved through bidirectional simulations between \(\textrm{AMP}_f\) and \(\textrm{HO}_f\) , using 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 help to delineate where round-based abstractions capture asynchronous computation, and where they do not.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Equivalence and Separation Between Heard-Of and Asynchronous Message-Passing Models

  • Hagit Attiya,
  • Armando Castañeda,
  • Dhrubajyoti Ghosh,
  • Thomas Nowak

摘要

We revisit the relationship between two fundamental models of distributed computation: the asynchronous message-passing model with up to f crash failures ( \(\textrm{AMP}_f\) ) and the Heard-Of model with up to f message omissions ( \(\textrm{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 \(\textrm{HO}_f\) , which may lead to incompatible decisions. The results are proved through bidirectional simulations between \(\textrm{AMP}_f\) and \(\textrm{HO}_f\) , using 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 help to delineate where round-based abstractions capture asynchronous computation, and where they do not.