DROPS

Document

DOI: 10.4230/LIPIcs.OPODIS.2023.19

Probable Approximate Coordination

Authors: Ariel Livshits and Yoram Moses

Published in: LIPIcs, Volume 286, 27th International Conference on Principles of Distributed Systems (OPODIS 2023)

Abstract

We study the problem of how to coordinate the actions of independent agents in a distributed system where message arrival times are unbounded, but are determined by an exponential probability distribution. Asynchronous protocols executed in such a model are guaranteed to succeed with probability 1. We demonstrate a case in which the best asynchronous protocol can be improved on significantly. Specifically, we focus on the task of performing actions by different agents in a linear temporal order - a problem known in the literature as Ordered Response. In asynchronous systems, ensuring such an ordering requires the construction of a message chain that passes through each acting agent, in order. Solving Ordered Response in this way in our model will terminate in time that grows linearly in the number of participating agents n, in expectation. We show that relaxing the specification slightly allows for a significant saving in time. Namely, if Ordered Response should be guaranteed with high probability (arbitrarily close to 1), it is possible to significantly shorten the expected execution time of the protocol. We present two protocols that adhere to the relaxed specification. One of our protocols executes exponentially faster than a message chain, when the number of participating agents n is large, while the other is roughly quadratically faster. For small values of n, it is also possible to achieve similar results by using a hybrid protocol.

Cite as

Ariel Livshits and Yoram Moses. Probable Approximate Coordination. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 19:1-19:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{livshits_et_al:LIPIcs.OPODIS.2023.19,
  author =	{Livshits, Ariel and Moses, Yoram},
  title =	{{Probable Approximate Coordination}},
  booktitle =	{27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
  pages =	{19:1--19:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-308-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{286},
  editor =	{Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.19},
  URN =		{urn:nbn:de:0030-drops-195090},
  doi =		{10.4230/LIPIcs.OPODIS.2023.19},
  annote =	{Keywords: Distributed coordination, ordered response, exponentially distributed delay}
}

Document

Brief Announcement

DOI: 10.4230/LIPIcs.DISC.2021.59

Brief Announcement: Simple Majority Consensus in Networks with Unreliable Communication

Authors: Ariel Livshits, Yonatan Shadmi, and Ran Tamir (Averbuch)

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

Abstract

In this work, we consider a synchronous model of n faultless agents, with a complete communication graph and messages that are lost with some constant probability q ∈ (0,1). In this model we show that there exists a protocol, called the Simple Majority Protocol, that solves consensus in 3 communication rounds with probability of agreement converging to 1 as n → ∞. We also prove that 3 communication rounds are necessary for the SMP to achieve consensus, with high probability.

Cite as

Ariel Livshits, Yonatan Shadmi, and Ran Tamir (Averbuch). Brief Announcement: Simple Majority Consensus in Networks with Unreliable Communication. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 59:1-59:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{livshits_et_al:LIPIcs.DISC.2021.59,
  author =	{Livshits, Ariel and Shadmi, Yonatan and Tamir (Averbuch), Ran},
  title =	{{Brief Announcement: Simple Majority Consensus in Networks with Unreliable Communication}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{59:1--59:4},
  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.59},
  URN =		{urn:nbn:de:0030-drops-148617},
  doi =		{10.4230/LIPIcs.DISC.2021.59},
  annote =	{Keywords: Majority consensus, probabilistic message loss, distributed systems}
}

Search Results

Documents authored by Livshits, Ariel

Probable Approximate Coordination

Abstract

Cite as

Brief Announcement: Simple Majority Consensus in Networks with Unreliable Communication

Abstract

Cite as

Thanks for your feedback!

Could not send message