DROPS

Document

DOI: 10.4230/LIPIcs.OPODIS.2015.22

Byzantine Agreement with Median Validity

Authors: David Stolz and Roger Wattenhofer

Published in: LIPIcs, Volume 46, 19th International Conference on Principles of Distributed Systems (OPODIS 2015)

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.

Cite as

David Stolz and Roger Wattenhofer. Byzantine Agreement with Median Validity. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 22:1-22:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{stolz_et_al:LIPIcs.OPODIS.2015.22,
  author =	{Stolz, David and Wattenhofer, Roger},
  title =	{{Byzantine Agreement with Median Validity}},
  booktitle =	{19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
  pages =	{22:1--22:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-98-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{46},
  editor =	{Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.22},
  URN =		{urn:nbn:de:0030-drops-65911},
  doi =		{10.4230/LIPIcs.OPODIS.2015.22},
  annote =	{Keywords: Reliability, fault-tolerance, median, consensus}
}

Search Results

Documents authored by Stolz, David

Byzantine Agreement with Median Validity

Abstract

Cite as

Thanks for your feedback!

Could not send message