Search Results

Documents authored by Stolz, David

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)

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

  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 =		{},
  URN =		{urn:nbn:de:0030-drops-65911},
  doi =		{10.4230/LIPIcs.OPODIS.2015.22},
  annote =	{Keywords: Reliability, fault-tolerance, median, consensus}
Questions / Remarks / Feedback

Feedback for Dagstuhl Publishing

Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail