License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.OPODIS.2015.32
URN: urn:nbn:de:0030-drops-66217
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6621/
Go to the corresponding LIPIcs Volume Portal

Talmage, Edward ; Welch, Jennifer

Generic Proofs of Consensus Numbers for Abstract Data Types

pdf-format:
LIPIcs-OPODIS-2015-32.pdf (0.4 MB)

Abstract

The power of shared data types to solve consensus in asynchronous wait-free systems is a fundamental question in distributed computing, but is largely considered only for specific data types. We consider general classes of abstract shared data types, and classify types of operations on those data types by the knowledge about past operations that processes can extract from the state of the shared object. We prove upper and lower bounds on the number of processes which can use data types in these classes to solve consensus. Our results generalize the consensus numbers known for a wide variety of specific shared data types, such as compare-and-swap, augmented queues and stacks, registers, and cyclic queues. Further, since the classification is based directly on the semantics of operations, one can use the bounds we present to determine the consensus number of a new data type from its specification.

We show that, using sets of operations which can detect the first change to the shared object state, or even one at a fixed distance from the beginning of the execution, any number of processes can solve consensus. However, if instead of one of the first changes, operations can only detect one of the most recent changes, then fewer processes can solve consensus. In general, if each operation can either change shared state or read it, but not both, then the number of processes which can solve consensus is limited by the number of consecutive recent operations which can be viewed by a single operation. Allowing operations that both change and read the shared state can allow consensus algorithms with more processes, but if the operations can only see one change a fixed number of operations in the past, we upper bound the number of processes which can solve consensus with a small constant.

BibTeX - Entry

@InProceedings{talmage_et_al:LIPIcs:2016:6621,
  author =	{Edward Talmage and Jennifer Welch},
  title =	{{Generic Proofs of Consensus Numbers for Abstract Data Types}},
  booktitle =	{19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
  pages =	{1--16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-98-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{46},
  editor =	{Emmanuelle Anceaume and Christian Cachin and Maria Potop-Butucaru},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6621},
  URN =		{urn:nbn:de:0030-drops-66217},
  doi =		{10.4230/LIPIcs.OPODIS.2015.32},
  annote =	{Keywords: Distributed Data Structures, Abstract Data Types, Consensus Numbers, Distributed Computing, Crash Failures}
}

Keywords: Distributed Data Structures, Abstract Data Types, Consensus Numbers, Distributed Computing, Crash Failures
Collection: 19th International Conference on Principles of Distributed Systems (OPODIS 2015)
Issue Date: 2016
Date of publication: 13.10.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI