DROPS

Document

DOI: 10.4230/LIPIcs.DISC.2020.30

Fast Agreement in Networks with Byzantine Nodes

Authors: Bogdan S. Chlebus, Dariusz R. Kowalski, and Jan Olkowski

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

Abstract

We study Consensus in synchronous networks with arbitrary connected topologies. Nodes may be faulty, in the sense of either Byzantine or proneness to crashing. Let t denote a known upper bound on the number of faulty nodes, and D_s denote a maximum diameter of a network obtained by removing up to s nodes, assuming the network is (s+1)-connected. We give an algorithm for Consensus running in time t + D_{2t} with nodes subject to Byzantine faults. We show that, for any algorithm solving Consensus for Byzantine nodes, there is a network G and an execution of the algorithm on this network that takes Ω(t + D_{2t}) rounds. We give an algorithm solving Consensus in t + D_{t} communication rounds with Byzantine nodes using authenticated messages of polynomial size. We show that for any numbers t and d > 4, there exists a network G and an algorithm solving Consensus with Byzantine nodes using authenticated messages in fewer than t + 3 rounds on G, but all algorithms solving Consensus without message authentication require at least t + d rounds on G. This separates Consensus with Byzantine nodes from Consensus with Byzantine nodes using message authentication, with respect to asymptotic time performance in networks of arbitrary connected topologies, which is unlike complete networks. Let f denote the number of failures actually occurring in an execution and unknown to the nodes. We develop an algorithm solving Consensus against crash failures and running in time 𝒪(f + D_{f}), assuming only that nodes know their names and can differentiate among ports; this algorithm is also communication-efficient, by using messages of size 𝒪(mlog n), where n is the number of nodes and m is the number of edges. We give a lower bound t+D_t-2 on the running time of any deterministic solution to Consensus in (t+1)-connected networks, if t nodes may crash.

Cite as

Bogdan S. Chlebus, Dariusz R. Kowalski, and Jan Olkowski. Fast Agreement in Networks with Byzantine Nodes. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 30:1-30:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{chlebus_et_al:LIPIcs.DISC.2020.30,
  author =	{Chlebus, Bogdan S. and Kowalski, Dariusz R. and Olkowski, Jan},
  title =	{{Fast Agreement in Networks with Byzantine Nodes}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{30:1--30:18},
  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.30},
  URN =		{urn:nbn:de:0030-drops-131088},
  doi =		{10.4230/LIPIcs.DISC.2020.30},
  annote =	{Keywords: distributed algorithm, network, Consensus, Byzantine fault, message authentication, node crash, lower bound}
}

Document

DOI: 10.4230/LIPIcs.OPODIS.2017.15

Anonymous Processors with Synchronous Shared Memory: Monte Carlo Algorithms

Authors: Bogdan S. Chlebus, Gianluca De Marco, and Muhammed Talo

Published in: LIPIcs, Volume 95, 21st International Conference on Principles of Distributed Systems (OPODIS 2017)

Abstract

We consider synchronous distributed systems in which processors communicate by shared read- write variables. Processors are anonymous and do not know their number n. The goal is to assign individual names by all the processors to themselves. We develop algorithms that accomplish this for each of the four cases determined by the following independent properties of the model: concurrently attempting to write distinct values into the same shared memory register either is allowed or not, and the number of shared variables either is a constant or it is unbounded. For each such a case, we give a Monte Carlo algorithm that runs in the optimum expected time and uses the expected number of O(n log n) random bits. All our algorithms produce correct output upon termination with probabilities that are 1−n^{−Ω(1)}, which is best possible when terminating almost surely and using O(n log n) random bits.

Cite as

Bogdan S. Chlebus, Gianluca De Marco, and Muhammed Talo. Anonymous Processors with Synchronous Shared Memory: Monte Carlo Algorithms. In 21st International Conference on Principles of Distributed Systems (OPODIS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 95, pp. 15:1-15:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{chlebus_et_al:LIPIcs.OPODIS.2017.15,
  author =	{Chlebus, Bogdan S. and De Marco, Gianluca and Talo, Muhammed},
  title =	{{Anonymous  Processors with Synchronous Shared Memory:  Monte Carlo Algorithms}},
  booktitle =	{21st International Conference on Principles of Distributed Systems (OPODIS 2017)},
  pages =	{15:1--15:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-061-3},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{95},
  editor =	{Aspnes, James and Bessani, Alysson and Felber, Pascal and Leit\~{a}o, Jo\~{a}o},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2017.15},
  URN =		{urn:nbn:de:0030-drops-86502},
  doi =		{10.4230/LIPIcs.OPODIS.2017.15},
  annote =	{Keywords: anonymous processors, synchrony, shared memory, read-write registers, naming, Monte Carlo algorithms}
}

Search Results

Documents authored by Chlebus, Bogdan S.

Fast Agreement in Networks with Byzantine Nodes

Abstract

Cite as

Anonymous Processors with Synchronous Shared Memory: Monte Carlo Algorithms

Abstract

Cite as

Thanks for your feedback!

Could not send message