Search Results

Documents authored by Vaidya, Nitin H.

Document
DOI: 10.4230/LIPIcs.DISC.2021.26
Byzantine Consensus with Local Multicast Channels

Authors: Muhammad Samir Khan and Nitin H. Vaidya

Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)

Abstract
Byzantine consensus is a classical problem in distributed computing. Each node in a synchronous system starts with a binary input. The goal is to reach agreement in the presence of Byzantine faulty nodes. We consider the setting where communication between nodes is modelled via an undirected communication graph. In the classical point-to-point communication model all messages sent on an edge are private between the two endpoints of the edge. This allows a faulty node to equivocate, i.e., lie differently to its different neighbors. Different models have been proposed in the literature that weaken equivocation. In the local broadcast model, every message transmitted by a node is received identically and correctly by all of its neighbors. In the hypergraph model, every message transmitted by a node on a hyperedge is received identically and correctly by all nodes on the hyperedge. Tight network conditions are known for each of the three cases. We introduce a more general model that encompasses all three of these models. In the local multicast model, each node u has one or more local multicast channels. Each channel consists of multiple neighbors of u in the communication graph. When node u sends a message on a channel, it is received identically by all of its neighbors on the channel. For this model, we identify tight network conditions for consensus. We observe how the local multicast model reduces to each of the three models above under specific conditions. In each of the three cases, we relate our network condition to the corresponding known tight conditions. The local multicast model also encompasses other practical network models of interest that have not been explored previously, as elaborated in the paper.
Cite as

Muhammad Samir Khan and Nitin H. Vaidya. Byzantine Consensus with Local Multicast Channels. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 26:1-26:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{khan_et_al:LIPIcs.DISC.2021.26,
  author =	{Khan, Muhammad Samir and Vaidya, Nitin H.},
  title =	{{Byzantine Consensus with Local Multicast Channels}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{26:1--26:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-210-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{209},
  editor =	{Gilbert, Seth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.26},
  URN =		{urn:nbn:de:0030-drops-148285},
  doi =		{10.4230/LIPIcs.DISC.2021.26},
  annote =	{Keywords: Byzantine fault, distributed algorithm, consensus, broadcast, multicast}
}
Document
DOI: 10.4230/LIPIcs.DISC.2020.28
Improved Extension Protocols for Byzantine Broadcast and Agreement

Authors: Kartik Nayak, Ling Ren, Elaine Shi, Nitin H. Vaidya, and Zhuolun Xiang

Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)

Abstract
Byzantine broadcast (BB) and Byzantine agreement (BA) are two most fundamental problems and essential building blocks in distributed computing, and improving their efficiency is of interest to both theoreticians and practitioners. In this paper, we study extension protocols of BB and BA, i.e., protocols that solve BB/BA with long inputs of l bits using lower costs than l single-bit instances. We present new protocols with improved communication complexity in almost all settings: authenticated BA/BB with t < n/2, authenticated BB with t < (1-ε)n, unauthenticated BA/BB with t < n/3, and asynchronous reliable broadcast and BA with t < n/3. The new protocols are advantageous and significant in several aspects. First, they achieve the best-possible communication complexity of Θ(nl) for wider ranges of input sizes compared to prior results. Second, the authenticated extension protocols achieve optimal communication complexity given the current best available BB/BA protocols for short messages. Third, to the best of our knowledge, our asynchronous and authenticated protocols in the setting are the first extension protocols in that setting.
Cite as

Kartik Nayak, Ling Ren, Elaine Shi, Nitin H. Vaidya, and Zhuolun Xiang. Improved Extension Protocols for Byzantine Broadcast and Agreement. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 28:1-28:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{nayak_et_al:LIPIcs.DISC.2020.28,
  author =	{Nayak, Kartik and Ren, Ling and Shi, Elaine and Vaidya, Nitin H. and Xiang, Zhuolun},
  title =	{{Improved Extension Protocols for Byzantine Broadcast and Agreement}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{28:1--28:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-168-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{179},
  editor =	{Attiya, Hagit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.28},
  URN =		{urn:nbn:de:0030-drops-131064},
  doi =		{10.4230/LIPIcs.DISC.2020.28},
  annote =	{Keywords: Byzantine agreement, Byzantine broadcast, extension protocol, communication complexity}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2019.30
Exact Byzantine Consensus on Arbitrary Directed Graphs Under Local Broadcast Model

Authors: Muhammad Samir Khan, Lewis Tseng, and Nitin H. Vaidya

Published in: LIPIcs, Volume 153, 23rd International Conference on Principles of Distributed Systems (OPODIS 2019)

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.
Cite as

Muhammad Samir Khan, Lewis Tseng, and Nitin H. Vaidya. Exact Byzantine Consensus on Arbitrary Directed Graphs Under Local Broadcast Model. In 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, pp. 30:1-30:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{khan_et_al:LIPIcs.OPODIS.2019.30,
  author =	{Khan, Muhammad Samir and Tseng, Lewis and Vaidya, Nitin H.},
  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 =	{Felber, Pascal and Friedman, Roy and Gilbert, Seth and Miller, Avery},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2019.30},
  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}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2018.14
Effects of Topology Knowledge and Relay Depth on Asynchronous Appoximate Consensus

Authors: Dimitris Sakavalas, Lewis Tseng, and Nitin H. Vaidya

Published in: LIPIcs, Volume 125, 22nd International Conference on Principles of Distributed Systems (OPODIS 2018)

Abstract
Consider a point-to-point message-passing network. We are interested in the asynchronous crash-tolerant consensus problem in incomplete networks. We study the feasibility and efficiency of approximate consensus under different restrictions on topology knowledge and the relay depth, i.e., the maximum number of hops any message can be relayed. These two constraints are common in large-scale networks, and are used to avoid memory overload and network congestion respectively. Specifically, for positive integer values k and k', we consider that each node knows all its neighbors of at most k-hop distance (k-hop topology knowledge), and the relay depth is k'. We consider both directed and undirected graphs. More concretely, we answer the following question in asynchronous systems: "What is a tight condition on the underlying communication graphs for achieving approximate consensus if each node has only a k-hop topology knowledge and relay depth k'?" To prove that the necessary conditions presented in the paper are also sufficient, we have developed algorithms that achieve consensus in graphs satisfying those conditions: - The first class of algorithms requires k-hop topology knowledge and relay depth k. Unlike prior algorithms, these algorithms do not flood the network, and each node does not need the full topology knowledge. We show how the convergence time and the message complexity of those algorithms is affected by k, providing the respective upper bounds. - The second set of algorithms requires only one-hop neighborhood knowledge, i.e., immediate incoming and outgoing neighbors, but needs to flood the network (i.e., relay depth is n, where n is the number of nodes). One result that may be of independent interest is a topology discovery mechanism to learn and "estimate" the topology in asynchronous directed networks with crash faults.
Cite as

Dimitris Sakavalas, Lewis Tseng, and Nitin H. Vaidya. Effects of Topology Knowledge and Relay Depth on Asynchronous Appoximate Consensus. In 22nd International Conference on Principles of Distributed Systems (OPODIS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 125, pp. 14:1-14:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{sakavalas_et_al:LIPIcs.OPODIS.2018.14,
  author =	{Sakavalas, Dimitris and Tseng, Lewis and Vaidya, Nitin H.},
  title =	{{Effects of Topology Knowledge and Relay Depth on Asynchronous Appoximate Consensus}},
  booktitle =	{22nd International Conference on Principles of Distributed Systems (OPODIS 2018)},
  pages =	{14:1--14:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-098-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{125},
  editor =	{Cao, Jiannong and Ellen, Faith and Rodrigues, Luis and Ferreira, Bernardo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2018.14},
  URN =		{urn:nbn:de:0030-drops-100744},
  doi =		{10.4230/LIPIcs.OPODIS.2018.14},
  annote =	{Keywords: Asynchrony, crash, consensus, incomplete graphs, topology knowledge}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2018.51
Brief Announcement: Effects of Topology Knowledge and Relay Depth on Asynchronous Consensus

Authors: Dimitris Sakavalas, Lewis Tseng, and Nitin H. Vaidya

Published in: LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018)

Abstract
Consider an asynchronous incomplete directed network. We study the feasibility and efficiency of approximate crash-tolerant consensus under different restrictions on topology knowledge and relay depth, i.e., the maximum number of hops any message can be relayed.
Cite as

Dimitris Sakavalas, Lewis Tseng, and Nitin H. Vaidya. Brief Announcement: Effects of Topology Knowledge and Relay Depth on Asynchronous Consensus. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 51:1-51:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{sakavalas_et_al:LIPIcs.DISC.2018.51,
  author =	{Sakavalas, Dimitris and Tseng, Lewis and Vaidya, Nitin H.},
  title =	{{Brief Announcement: Effects of Topology Knowledge and Relay Depth on Asynchronous Consensus}},
  booktitle =	{32nd International Symposium on Distributed Computing (DISC 2018)},
  pages =	{51:1--51:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-092-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{121},
  editor =	{Schmid, Ulrich and Widder, Josef},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2018.51},
  URN =		{urn:nbn:de:0030-drops-98405},
  doi =		{10.4230/LIPIcs.DISC.2018.51},
  annote =	{Keywords: Asynchrony, crash fault, consensus, topology knowledge, relay}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2016.26
Relaxed Byzantine Vector Consensus

Authors: Zhuolun Xiang and Nitin H. Vaidya

Published in: LIPIcs, Volume 70, 20th International Conference on Principles of Distributed Systems (OPODIS 2016)

Abstract
Byzantine vector consensus requires that non-faulty processes reach agreement on adecision (or output) that is in the convex hull of the inputs at the non-faulty processes. Recent work has shown that, for n processes with up to f Byzantine failures, when the inputs are d-dimensional vectors of reals, n >= max (3f + 1, (d + 1)f + 1) is the tight bound for synchronous systems, and n >= (d + 2)f + 1 is tight for approximate consensus in asynchronous systems. Due to the dependence of the lower bound on vector dimension d, the number of processes necessary becomes large when the vector dimension is large. With the hope of reducing the lower bound on n, we propose relaxed versions of Byzantine vector consensus: k-relaxed Byzantine vector consensus and (delta, p)-relaxed Byzantine vector consensus. k-relaxed consensus only requires consensus for projections of inputs on every subset of k dimensions. (delta, p)-relaxed consensus requires that the output be within distance d of the convex hull of the non-faulty inputs, where distance is defined using the L_{p}-norm. An input-dependent delta allows the distance from the non-faulty convex hull to be dependent on the maximum distance between the non-faulty inputs. We show that for k-relaxed consensus with k > 1, and for (delta, p)-relaxed consensus with constant delta >= 0, the bound on n is identical to the bound stated above for the original vector consensus problem. On the other hand, when k = 1 or d depends on the inputs, we show that the bound on n is smaller when d >= 3. Input-dependent delta may be of interest in practice. In essence, input-dependent delta scales with the spread of the inputs.
Cite as

Zhuolun Xiang and Nitin H. Vaidya. Relaxed Byzantine Vector Consensus. In 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, pp. 26:1-26:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{xiang_et_al:LIPIcs.OPODIS.2016.26,
  author =	{Xiang, Zhuolun and Vaidya, Nitin H.},
  title =	{{Relaxed Byzantine Vector Consensus}},
  booktitle =	{20th International Conference on Principles of Distributed Systems (OPODIS 2016)},
  pages =	{26:1--26:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-031-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{70},
  editor =	{Fatourou, Panagiota and Jim\'{e}nez, Ernesto and Pedone, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2016.26},
  URN =		{urn:nbn:de:0030-drops-70958},
  doi =		{10.4230/LIPIcs.OPODIS.2016.26},
  annote =	{Keywords: Byzantine consensus, vector inputs, relaxed validity conditions}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact