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.2019.30
URN: urn:nbn:de:0030-drops-118161
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/11816/
Go to the corresponding LIPIcs Volume Portal

Khan, Muhammad Samir ; Tseng, Lewis ; Vaidya, Nitin H.

Exact Byzantine Consensus on Arbitrary Directed Graphs Under Local Broadcast Model

pdf-format:
LIPIcs-OPODIS-2019-30.pdf (0.5 MB)

Abstract

We consider Byzantine consensus in a synchronous system where nodes are connected by a network modeled as a directed graph, i.e., communication links between neighboring nodes are not necessarily bi-directional. The directed graph model is motivated by wireless networks wherein asymmetric communication links can occur. In the classical point-to-point communication model, a message sent on a communication link is private between the two nodes on the link. This allows a Byzantine faulty node to equivocate, i.e., send inconsistent information to its neighbors. This paper considers the local broadcast model of communication, wherein transmission by a node is received identically by all of its outgoing neighbors, effectively depriving the faulty nodes of the ability to equivocate.
Prior work has obtained sufficient and necessary conditions on undirected graphs to be able to achieve Byzantine consensus under the local broadcast model. In this paper, we obtain tight conditions on directed graphs to be able to achieve Byzantine consensus with binary inputs under the local broadcast model. The results obtained in the paper provide insights into the trade-off between directionality of communication links and the ability to achieve consensus.

BibTeX - Entry

@InProceedings{khan_et_al:LIPIcs:2020:11816,
  author =	{Muhammad Samir Khan and Lewis Tseng and Nitin H. Vaidya},
  title =	{{Exact Byzantine Consensus on Arbitrary Directed Graphs Under Local Broadcast Model}},
  booktitle =	{23rd International Conference on Principles of Distributed Systems (OPODIS 2019)},
  pages =	{30:1--30:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-133-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{153},
  editor =	{Pascal Felber and Roy Friedman and Seth Gilbert and Avery Miller},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/11816},
  URN =		{urn:nbn:de:0030-drops-118161},
  doi =		{10.4230/LIPIcs.OPODIS.2019.30},
  annote =	{Keywords: complexity and impossibility results for distributed computing, fault-tolerance, reliability}
}

Keywords: complexity and impossibility results for distributed computing, fault-tolerance, reliability
Collection: 23rd International Conference on Principles of Distributed Systems (OPODIS 2019)
Issue Date: 2020
Date of publication: 11.02.2020

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