文章基本信息

标题：Brief Announcement: Wait-Free Universality of Consensus in the Infinite Arrival Model
本地全文：下载
作者：Grgoire Bonin ; Achour Mostfaoui ; Matthieu Perrin 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：146
页码：1-3
DOI：10.4230/LIPIcs.DISC.2019.38
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：In classical asynchronous distributed systems composed of a fixed number n of processes where some proportion may fail by crashing, many objects do not have a wait-free linearizable implementation (e.g. stacks, queues, etc.). It has been proved that consensus is universal in such systems, which means that this system augmented with consensus objects allows to implement any object that has a sequential specification. In this paper, we consider a more general system model called infinite arrival model where infinitely many processes may arrive and leave or crash during a run. We prove that consensus is still universal in this more general model. For that, we propose a universal construction based on a weak log that can be implementated using consensus objects.
关键词：Concurrent object; Consensus; Infinite arrival model; Linearizability; Universal construction; Wait-freedom