首页    期刊浏览 2024年11月05日 星期二
登录注册

文章基本信息

  • 标题:Which Broadcast Abstraction Captures k-Set Agreement?
  • 本地全文:下载
  • 作者:Damien Imbs ; Achour Most{\'e}faoui ; Matthieu Perrin
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2017
  • 卷号:91
  • 页码:27:1-27:16
  • DOI:10.4230/LIPIcs.DISC.2017.27
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要:It is well-known that consensus (one-set agreement) and total order broadcast are equivalent in asynchronous systems prone to process crash failures. Considering wait-free systems, this article addresses and answers the following question: which is the communication abstraction that "captures" k-set agreement? To this end, it introduces a new broadcast communication abstraction, called k-BO-Broadcast, which restricts the disagreement on the local deliveries of the messages that have been broadcast (1-BO-Broadcast boils down to total order broadcast). Hence, in this context, k=1 is not a special number, but only the first integer in an increasing integer sequence. This establishes a new "correspondence" between distributed agreement problems and communication abstractions, which enriches our understanding of the relations linking fundamental issues of fault-tolerant distributed computing.
  • 关键词:Agreement problem; Antichain; Asynchronous system; Communication abstraction; Consensus; Message-passing system; Partially ordered set; Process crash
国家哲学社会科学文献中心版权所有