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.22
URN: urn:nbn:de:0030-drops-65911
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6591/
Go to the corresponding LIPIcs Volume Portal

Stolz, David ; Wattenhofer, Roger

Byzantine Agreement with Median Validity

pdf-format:
LIPIcs-OPODIS-2015-22.pdf (0.5 MB)

Abstract

We introduce a stronger validity property for the byzantine agreement problem with orderable initial values: The median validity property. In particular, the decision value is required to be close to the median of the initial values of the non-byzantine nodes. The proximity to the median scales with the desired level of fault-tolerance: If no fault-tolerance is required, algorithms have to decide for the true median. If the number of failures is maximal, algorithms must still decide on a value within the range of the input values of the non-byzantine nodes. We present a deterministic algorithm satisfying this property for n >= 3t+1 within t+1 phases, where t is the maximum number of byzantine nodes and n is the total number of nodes.

BibTeX - Entry

@InProceedings{stolz_et_al:LIPIcs:2016:6591,
  author =	{David Stolz and Roger Wattenhofer},
  title =	{{Byzantine Agreement with Median Validity}},
  booktitle =	{19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
  pages =	{1--14},
  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/6591},
  URN =		{urn:nbn:de:0030-drops-65911},
  doi =		{10.4230/LIPIcs.OPODIS.2015.22},
  annote =	{Keywords: Reliability, fault-tolerance, median, consensus}
}

Keywords: Reliability, fault-tolerance, median, consensus
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