文章基本信息

标题：On the Uncontended Complexity of Anonymous Consensus
本地全文：下载
作者：Claire Capdevielle ; Colette Johnen ; Petr Kuznetsov 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2016
卷号：46
页码：1-16
DOI：10.4230/LIPIcs.OPODIS.2015.12
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Consensus is one of the central distributed abstractions. By enabling a collection of processes to agree on one of the values they propose, consensus can be used to implement any generic replicated service in a consistent and fault-tolerant way. In this paper, we study uncontended complexity of anonymous consensus algorithms, counting the number of memory locations used and the number of memory updates performed in operations that encounter no contention. We assume that contention-free operations on a consensus object perform "fast" reads and writes, and resort to more expensive synchronization primitives, such as CAS, only when contention is detected. We call such concurrent implementations interval-solo-fast and derive one of the first nontrivial tight bounds on space complexity of anonymous interval-solo-fast consensus.
关键词：space and time complexity; lower bounds; consensus; interval contention; solo-fast