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.2016.5
URN: urn:nbn:de:0030-drops-70742
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7074/
Go to the corresponding LIPIcs Volume Portal

Yu Cheng Chan, David ; Hadzilacos, Vassos ; Toueg, Sam

Bounded Disagreement

pdf-format:
LIPIcs-OPODIS-2016-5.pdf (0.5 MB)

Abstract

A well-known generalization of the consensus problem, namely, set agreement (SA), limits the number of distinct decision values that processes decide. In some settings, it may be more important to limit the number of "disagreers". Thus, we introduce another natural generalization of the consensus problem, namely, bounded disagreement (BD), which limits the number of processes that decide differently from the plurality. More precisely, in a system with n processes, the (n, l)-BD task has the following requirement: there is a value v such that at most l processes (the disagreers) decide a value other than v. Despite their apparent similarities, the results described below show that bounded disagreement, consensus, and set agreement are in fact fundamentally different problems.

We investigate the relationship between bounded disagreement, consensus, and set agreement. In particular, we determine the consensus number for every instance of the BD task. We also determine values of n, l, m, and k such that the (n, l)-BD task can solve the (m, k)-SA task (where m processes can decide at most k distinct values). Using our results and a previously known impossibility result for set agreement, we prove that for all n >= 2, there is a BD task (and a corresponding BD object) that has consensus number n but can not be solved using n-consensus and registers. Prior to our paper, the only objects known to have this unusual characteristic for n >= 2 (which shows that the consensus number of an object is not sufficient to fully capture its power) were artificial objects crafted solely for the purpose of exhibiting this behaviour.

BibTeX - Entry

@InProceedings{yuchengchan_et_al:LIPIcs:2017:7074,
  author =	{David Yu Cheng Chan and Vassos Hadzilacos and Sam Toueg},
  title =	{{Bounded Disagreement}},
  booktitle =	{20th International Conference on Principles of Distributed Systems (OPODIS 2016)},
  pages =	{5:1--5:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-031-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{70},
  editor =	{Panagiota Fatourou and Ernesto Jim{\'e}nez and Fernando Pedone},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7074},
  URN =		{urn:nbn:de:0030-drops-70742},
  doi =		{10.4230/LIPIcs.OPODIS.2016.5},
  annote =	{Keywords: Consensus, Set Agreement, Asynchronous System, Distributed Algorithms, Shared Memory}
}

Keywords: Consensus, Set Agreement, Asynchronous System, Distributed Algorithms, Shared Memory
Collection: 20th International Conference on Principles of Distributed Systems (OPODIS 2016)
Issue Date: 2017
Date of publication: 06.04.2017

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