文章基本信息

标题：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