DROPS

Volume

LIPIcs, Volume 121

32nd International Symposium on Distributed Computing (DISC 2018)

DISC 2018, October 15-19, 2018, New Orleans, USA

Editors: Ulrich Schmid and Josef Widder

Document

DOI: 10.4230/LIPIcs.ITCS.2023.100

The Time Complexity of Consensus Under Oblivious Message Adversaries

Authors: Kyrill Winkler, Ami Paz, Hugo Rincon Galeana, Stefan Schmid, and Ulrich Schmid

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Abstract

We study the problem of solving consensus in synchronous directed dynamic networks, in which communication is controlled by an oblivious message adversary that picks the communication graph to be used in a round from a fixed set of graphs 𝐃 arbitrarily. In this fundamental model, determining consensus solvability and designing efficient consensus algorithms is surprisingly difficult. Enabled by a decision procedure that is derived from a well-established previous consensus solvability characterization for a given set 𝐃, we study, for the first time, the time complexity of solving consensus in this model: We provide both upper and lower bounds for this time complexity, and also relate it to the number of iterations required by the decision procedure. Among other results, we find that reaching consensus under an oblivious message adversary can take exponentially longer than both deciding consensus solvability and broadcasting the input value of some unknown process to all other processes.

Cite as

Kyrill Winkler, Ami Paz, Hugo Rincon Galeana, Stefan Schmid, and Ulrich Schmid. The Time Complexity of Consensus Under Oblivious Message Adversaries. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 100:1-100:28, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{winkler_et_al:LIPIcs.ITCS.2023.100,
  author =	{Winkler, Kyrill and Paz, Ami and Rincon Galeana, Hugo and Schmid, Stefan and Schmid, Ulrich},
  title =	{{The Time Complexity of Consensus Under Oblivious Message Adversaries}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{100:1--100:28},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.100},
  URN =		{urn:nbn:de:0030-drops-176030},
  doi =		{10.4230/LIPIcs.ITCS.2023.100},
  annote =	{Keywords: dynamic networks, oblivious message adversaries, consensus, time complexity}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2022.73

Continuous Tasks and the Asynchronous Computability Theorem

Authors: Hugo Rincon Galeana, Sergio Rajsbaum, and Ulrich Schmid

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract

The celebrated 1999 Asynchronous Computability Theorem (ACT) of Herlihy and Shavit characterized distributed tasks that are wait-free solvable and uncovered deep connections with combinatorial topology. We provide an alternative characterization of those tasks by means of the novel concept of continuous tasks, which have an input/output specification that is a continuous function between the geometric realizations of the input and output complex: We state and prove a precise characterization theorem (CACT) for wait-free solvable tasks in terms of continuous tasks. Its proof utilizes a novel chromatic version of a foundational result in algebraic topology, the simplicial approximation theorem, which is also proved in this paper. Apart from the alternative proof of the ACT implied by our CACT, we also demonstrate that continuous tasks have an expressive power that goes beyond classic task specifications, and hence open up a promising venue for future research: For the well-known approximate agreement task, we show that one can easily encode the desired proportion of the occurrence of specific outputs, namely, exact agreement, in the continuous task specification.

Cite as

Hugo Rincon Galeana, Sergio Rajsbaum, and Ulrich Schmid. Continuous Tasks and the Asynchronous Computability Theorem. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 73:1-73:27, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{galeana_et_al:LIPIcs.ITCS.2022.73,
  author =	{Galeana, Hugo Rincon and Rajsbaum, Sergio and Schmid, Ulrich},
  title =	{{Continuous Tasks and the Asynchronous Computability Theorem}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{73:1--73:27},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.73},
  URN =		{urn:nbn:de:0030-drops-156696},
  doi =		{10.4230/LIPIcs.ITCS.2022.73},
  annote =	{Keywords: Wait-free computability, topology, distributed computing, decision tasks, shared memory}
}

Document

DOI: 10.4230/LIPIcs.OPODIS.2020.18

Locally Solvable Tasks and the Limitations of Valency Arguments

Authors: Hagit Attiya, Armando Castañeda, and Sergio Rajsbaum

Published in: LIPIcs, Volume 184, 24th International Conference on Principles of Distributed Systems (OPODIS 2020)

Abstract

An elegant strategy for proving impossibility results in distributed computing was introduced in the celebrated FLP consensus impossibility proof. This strategy is local in nature as at each stage, one configuration of a hypothetical protocol for consensus is considered, together with future valencies of possible extensions. This proof strategy has been used in numerous situations related to consensus, leading one to wonder why it has not been used in impossibility results of two other well-known tasks: set agreement and renaming. This paper provides an explanation of why impossibility proofs of these tasks have been of a global nature. It shows that a protocol can always solve such tasks locally, in the following sense. Given a configuration and all its future valencies, if a single successor configuration is selected, then the protocol can reveal all decisions in this branch of executions, satisfying the task specification. This result is shown for both set agreement and renaming, implying that there are no local impossibility proofs for these tasks.

Cite as

Hagit Attiya, Armando Castañeda, and Sergio Rajsbaum. Locally Solvable Tasks and the Limitations of Valency Arguments. In 24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, pp. 18:1-18:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{attiya_et_al:LIPIcs.OPODIS.2020.18,
  author =	{Attiya, Hagit and Casta\~{n}eda, Armando and Rajsbaum, Sergio},
  title =	{{Locally Solvable Tasks and the Limitations of Valency Arguments}},
  booktitle =	{24th International Conference on Principles of Distributed Systems (OPODIS 2020)},
  pages =	{18:1--18:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-176-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{184},
  editor =	{Bramas, Quentin and Oshman, Rotem and Romano, Paolo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2020.18},
  URN =		{urn:nbn:de:0030-drops-135037},
  doi =		{10.4230/LIPIcs.OPODIS.2020.18},
  annote =	{Keywords: Wait-freedom, Set agreement, Weak symmetry breaking, Impossibility proofs}
}

Document

DOI: 10.4230/LIPIcs.OPODIS.2019.17

A Characterization of Consensus Solvability for Closed Message Adversaries

Authors: Kyrill Winkler, Ulrich Schmid, and Yoram Moses

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

Abstract

Distributed computations in a synchronous system prone to message loss can be modeled as a game between a (deterministic) distributed algorithm versus an omniscient message adversary. The latter determines, for each round, the directed communication graph that specifies which messages can reach their destination. Message adversary definitions range from oblivious ones, which pick the communication graphs arbitrarily from a given set of candidate graphs, to general message adversaries, which are specified by the set of sequences of communication graphs (called admissible communication patterns) that they may generate. This paper provides a complete characterization of consensus solvability for closed message adversaries, where every inadmissible communication pattern has a finite prefix that makes all (infinite) extensions of this prefix inadmissible. Whereas every oblivious message adversary is closed, there are also closed message adversaries that are not oblivious. We provide a tight non-topological, purely combinatorial characterization theorem, which reduces consensus solvability to a simple condition on prefixes of the communication patterns. Our result not only non-trivially generalizes the known combinatorial characterization of the consensus solvability for oblivious message adversaries by Coulouma, Godard, and Peters (Theor. Comput. Sci., 2015), but also provides the first combinatorial characterization for this important class of message adversaries that is formulated directly on the prefixes of the communication patterns.

Cite as

Kyrill Winkler, Ulrich Schmid, and Yoram Moses. A Characterization of Consensus Solvability for Closed Message Adversaries. In 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, pp. 17:1-17:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{winkler_et_al:LIPIcs.OPODIS.2019.17,
  author =	{Winkler, Kyrill and Schmid, Ulrich and Moses, Yoram},
  title =	{{A Characterization of Consensus Solvability for Closed Message Adversaries}},
  booktitle =	{23rd International Conference on Principles of Distributed Systems (OPODIS 2019)},
  pages =	{17:1--17: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.17},
  URN =		{urn:nbn:de:0030-drops-118038},
  doi =		{10.4230/LIPIcs.OPODIS.2019.17},
  annote =	{Keywords: Dynamic networks, Consensus, Message Adversary}
}

Document

Complete Volume

DOI: 10.4230/LIPIcs.DISC.2018

LIPIcs, Volume 121, DISC'18, Complete Volume

Authors: Ulrich Schmid and Josef Widder

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

Abstract

LIPIcs, Volume 121, DISC'18, Complete Volume

Cite as

Ulrich Schmid and Josef Widder. LIPIcs, Volume 121, DISC'18, Complete Volume. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@Proceedings{schmid_et_al:LIPIcs.DISC.2018,
  title =	{{LIPIcs, Volume 121, DISC'18, Complete Volume}},
  booktitle =	{32nd International Symposium on Distributed Computing (DISC 2018)},
  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},
  URN =		{urn:nbn:de:0030-drops-98456},
  doi =		{10.4230/LIPIcs.DISC.2018},
  annote =	{Keywords: Software and its engineering, Distributed systems organizing principles, Computing methodologies, Distributed computing methodologies}
}

Document

Front Matter

DOI: 10.4230/LIPIcs.DISC.2018.0

Front Matter, Table of Contents, Preface, Conference Organization, Awards

Authors: Ulrich Schmid and Josef Widder

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

Abstract

Front Matter, Table of Contents, Preface, Conference Organization, Awards

Cite as

Ulrich Schmid and Josef Widder. Front Matter, Table of Contents, Preface, Conference Organization, Awards. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 0:i-0:xx, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{schmid_et_al:LIPIcs.DISC.2018.0,
  author =	{Schmid, Ulrich and Widder, Josef},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization, Awards}},
  booktitle =	{32nd International Symposium on Distributed Computing (DISC 2018)},
  pages =	{0:i--0:xx},
  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.0},
  URN =		{urn:nbn:de:0030-drops-97899},
  doi =		{10.4230/LIPIcs.DISC.2018.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization, Awards}
}

Document

Invited Talk

DOI: 10.4230/LIPIcs.DISC.2018.1

Autonomous Vehicles: From Individual Navigation to Challenges of Distributed Swarms (Invited Talk)

Authors: Sándor P. Fekete

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

Abstract

Recent years have seen impressive advancements in the development of robots on four wheels: autonomous cars. While much of this progress is owed to a combination of breakthroughs in artificial intelligence and improved sensors, dealing with complex, non-ideal scenarios, where errors or failures can turn out to be catastrophic is still largely unsolved; this will require combining "fast", heuristic approaches of machine learning with "slow", more deliberate methods of discrete algorithms and mathematical optimization. However, many of the real challenges go beyond performance guarantees for individual vehicles and aim at the behavior of swarms: How can we control the complex interaction of a distributed swarm of vehicles, such that the overall behavior can measure up to and go beyond the capabilities of humans? Even though many of our engineering colleagues do not fully realize this yet, there is no doubt that this will have to be based to no small part on expertise in distributed algorithms. I will present a multi-level overview of results and challenges, ranging from information exchanges of small groups all the way to game-theoretic mechanisms for large-scale control. Application scenarios do not just arise from road traffic (where short response times, large numbers of vehicles and individual interests give rise to many difficulties), but also from swarms of autonomous space vehicles (where huge distances, times and energies make distributed methods indispensable).

Cite as

Sándor P. Fekete. Autonomous Vehicles: From Individual Navigation to Challenges of Distributed Swarms (Invited Talk). In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, p. 1:1, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{fekete:LIPIcs.DISC.2018.1,
  author =	{Fekete, S\'{a}ndor P.},
  title =	{{Autonomous Vehicles: From Individual Navigation to Challenges of Distributed Swarms}},
  booktitle =	{32nd International Symposium on Distributed Computing (DISC 2018)},
  pages =	{1:1--1:1},
  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.1},
  URN =		{urn:nbn:de:0030-drops-97904},
  doi =		{10.4230/LIPIcs.DISC.2018.1},
  annote =	{Keywords: Autonomous vehicles, interaction, robot swarms, game theory}
}

Document

Invited Talk

DOI: 10.4230/LIPIcs.DISC.2018.2

Challenges for Machine Learning on Distributed Platforms (Invited Talk)

Authors: Tom Goldstein

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

Abstract

Deep neural networks are trained by solving huge optimization problems with large datasets and millions of variables. On the surface, it seems that the size of these problems makes them a natural target for distributed computing. Despite this, most deep learning research still takes place on a single compute node with a small number of GPUs, and only recently have researchers succeeded in unlocking the power of HPC. In this talk, we'll give a brief overview of how deep networks are trained, and use HPC tools to explore and explain deep network behaviors. Then, we'll explain the problems and challenges that arise when scaling deep nets over large system, and highlight reasons why naive distributed training methods fail. Finally, we'll discuss recent algorithmic innovations that have overcome these limitations, including "big batch" training for tightly coupled clusters and supercomputers, and "variance reduction" strategies to reduce communication in high latency settings.

Cite as

Tom Goldstein. Challenges for Machine Learning on Distributed Platforms (Invited Talk). In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 2:1-2:3, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{goldstein:LIPIcs.DISC.2018.2,
  author =	{Goldstein, Tom},
  title =	{{Challenges for Machine Learning on Distributed Platforms}},
  booktitle =	{32nd International Symposium on Distributed Computing (DISC 2018)},
  pages =	{2:1--2:3},
  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.2},
  URN =		{urn:nbn:de:0030-drops-97910},
  doi =		{10.4230/LIPIcs.DISC.2018.2},
  annote =	{Keywords: Machine learning, distributed optimization}
}

Document

Invited Talk

DOI: 10.4230/LIPIcs.DISC.2018.3

Logical Analysis of Distributed Systems: The Importance of Being Constructive (Invited Talk)

Authors: Michael Mendler

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

Abstract

The design and analysis of complex distributed systems proceeds along numerous levels of abstractions. One key abstraction step for reducing complexity is the passage from analog transistor electronics to synchronously clocked digital circuits. This significantly simplifies the modelling from continuous differential equations over the real numbers to discrete Mealy automata over two-valued Boolean algebra. Although typically taken for granted, this step is magic. How do we obtain clock synchronization from asynchronous communication of continuous values? How do we decide on the discrete meaning of continuous signals without a synchronization clock? From a logical perspective, the possibility of synchronization is paradoxical and appears "out of thin air." The chicken-or-egg paradox persists at higher levels abstraction for distributed software. We cannot achieve globally consistent state from local communications without synchronization. At the same time we cannot synchronize without access to globally consistent state. From this perspective, distributed algorithms such as for leader election, consensus or mutual exclusion do not strictly solve their task but merely reduce one synchronization problem to another. This talk revisits the logical justification of the synchronous abstraction claiming that correctness arguments, in so far as they are not merely reductions, must intrinsically depend on reasoning in classical logic. This is studied at the circuit level, where all software reductions must end. The well-known result that some synchronization elements cannot be implemented in delay-insensitive circuits is related to Berry's Thesis according to which digital circuits are delay-insensitive if and only if they are provably correct in constructive logic. More technically, the talk will show how non-inertial delays give rise to a constructive modal logic while inertial delays are inherently non-constructive. This gives a logical explanation for why inertial delays can be used to build arbiters, memory-cells and other synchronization elements, while non-inertial delays are not powerful enough. Though these results are tentative, they indicate the importance of logical constructiveness for metastable-free discrete abstractions of physical behavior. This also indicates that metastability is an unavoidable artifact of the digital abstraction in classical logic.

Cite as

Michael Mendler. Logical Analysis of Distributed Systems: The Importance of Being Constructive (Invited Talk). In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, p. 3:1, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{mendler:LIPIcs.DISC.2018.3,
  author =	{Mendler, Michael},
  title =	{{Logical Analysis of Distributed Systems: The Importance of Being Constructive}},
  booktitle =	{32nd International Symposium on Distributed Computing (DISC 2018)},
  pages =	{3:1--3:1},
  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.3},
  URN =		{urn:nbn:de:0030-drops-97925},
  doi =		{10.4230/LIPIcs.DISC.2018.3},
  annote =	{Keywords: Hardware synchronisation, inertial delays, delay-insensitive circuits, constructive circuits, metastability, constructive modal logic}
}

Document

DOI: 10.4230/LIPIcs.DISC.2018.4

Selecting a Leader in a Network of Finite State Machines

Authors: Yehuda Afek, Yuval Emek, and Noa Kolikant

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

Abstract

This paper studies a variant of the leader election problem under the stone age model (Emek and Wattenhofer, PODC 2013) that considers a network of n randomized finite automata with very weak communication capabilities (a multi-frequency asynchronous generalization of the beeping model's communication scheme). Since solving the classic leader election problem is impossible even in more powerful models, we consider a relaxed variant, referred to as k-leader selection, in which a leader should be selected out of at most k initial candidates. Our main contribution is an algorithm that solves k-leader selection for bounded k in the aforementioned stone age model. On (general topology) graphs of diameter D, this algorithm runs in O~(D) time and succeeds with high probability. The assumption that k is bounded turns out to be unavoidable: we prove that if k = omega (1), then no algorithm in this model can solve k-leader selection with a (positive) constant probability.

Cite as

Yehuda Afek, Yuval Emek, and Noa Kolikant. Selecting a Leader in a Network of Finite State Machines. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 4:1-4:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{afek_et_al:LIPIcs.DISC.2018.4,
  author =	{Afek, Yehuda and Emek, Yuval and Kolikant, Noa},
  title =	{{Selecting a Leader in a Network of Finite State Machines}},
  booktitle =	{32nd International Symposium on Distributed Computing (DISC 2018)},
  pages =	{4:1--4:17},
  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.4},
  URN =		{urn:nbn:de:0030-drops-97933},
  doi =		{10.4230/LIPIcs.DISC.2018.4},
  annote =	{Keywords: stone age model, beeping communication scheme, leader election, k-leader selection, randomized finite state machines, asynchronous scheduler}
}

Document

DOI: 10.4230/LIPIcs.DISC.2018.5

The Role of A-priori Information in Networks of Rational Agents

Authors: Yehuda Afek, Shaked Rafaeli, and Moshe Sulamy

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

Abstract

Until now, distributed algorithms for rational agents have assumed a-priori knowledge of n, the size of the network. This assumption is challenged here by proving how much a-priori knowledge is necessary for equilibrium in different distributed computing problems. Duplication - pretending to be more than one agent - is the main tool used by agents to deviate and increase their utility when not enough knowledge about n is given. We begin by proving that when no information on n is given, equilibrium is impossible for both Coloring and Knowledge Sharing. We then provide new algorithms for both problems when n is a-priori known to all agents. However, what if agents have partial knowledge about n? We provide tight upper and lower bounds that must be a-priori known on n for equilibrium to be possible in Leader Election, Knowledge Sharing, Coloring, Partition and Orientation.

Cite as

Yehuda Afek, Shaked Rafaeli, and Moshe Sulamy. The Role of A-priori Information in Networks of Rational Agents. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 5:1-5:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{afek_et_al:LIPIcs.DISC.2018.5,
  author =	{Afek, Yehuda and Rafaeli, Shaked and Sulamy, Moshe},
  title =	{{The Role of A-priori Information in Networks of Rational Agents}},
  booktitle =	{32nd International Symposium on Distributed Computing (DISC 2018)},
  pages =	{5:1--5:18},
  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.5},
  URN =		{urn:nbn:de:0030-drops-97945},
  doi =		{10.4230/LIPIcs.DISC.2018.5},
  annote =	{Keywords: rational agents, distributed game theory, coloring, knowledge sharing}
}

Document

DOI: 10.4230/LIPIcs.DISC.2018.6

Distributed Approximate Maximum Matching in the CONGEST Model

Authors: Mohamad Ahmadi, Fabian Kuhn, and Rotem Oshman

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

Abstract

We study distributed algorithms for the maximum matching problem in the CONGEST model, where each message must be bounded in size. We give new deterministic upper bounds, and a new lower bound on the problem. We begin by giving a distributed algorithm that computes an exact maximum (unweighted) matching in bipartite graphs, in O(n log n) rounds. Next, we give a distributed algorithm that approximates the fractional weighted maximum matching problem in general graphs. In a graph with maximum degree at most Delta, the algorithm computes a (1-epsilon)-approximation for the problem in time O(log(Delta W)/epsilon^2), where W is a bound on the ratio between the largest and the smallest edge weight. Next, we show a slightly improved and generalized version of the deterministic rounding algorithm of Fischer [DISC '17]. Given a fractional weighted maximum matching solution of value f for a given graph G, we show that in time O((log^2(Delta)+log^*n)/epsilon), the fractional solution can be turned into an integer solution of value at least (1-epsilon)f for bipartite graphs and (1-epsilon) * (g-1)/g * f for general graphs, where g is the length of the shortest odd cycle of G. Together with the above fractional maximum matching algorithm, this implies a deterministic algorithm that computes a (1-epsilon)* (g-1)/g-approximation for the weighted maximum matching problem in time O(log(Delta W)/epsilon^2 + (log^2(Delta)+log^* n)/epsilon). On the lower-bound front, we show that even for unweighted fractional maximum matching in bipartite graphs, computing an (1 - O(1/sqrt{n}))-approximate solution requires at least Omega~(D+sqrt{n}) rounds in CONGEST. This lower bound requires the introduction of a new 2-party communication problem, for which we prove a tight lower bound.

Cite as

Mohamad Ahmadi, Fabian Kuhn, and Rotem Oshman. Distributed Approximate Maximum Matching in the CONGEST Model. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 6:1-6:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{ahmadi_et_al:LIPIcs.DISC.2018.6,
  author =	{Ahmadi, Mohamad and Kuhn, Fabian and Oshman, Rotem},
  title =	{{Distributed Approximate Maximum Matching in the CONGEST Model}},
  booktitle =	{32nd International Symposium on Distributed Computing (DISC 2018)},
  pages =	{6:1--6:17},
  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.6},
  URN =		{urn:nbn:de:0030-drops-97950},
  doi =		{10.4230/LIPIcs.DISC.2018.6},
  annote =	{Keywords: distributed graph algorithms, maximum matching, deterministic rounding, communication complexity}
}

Document

DOI: 10.4230/LIPIcs.DISC.2018.7

State Machine Replication Is More Expensive Than Consensus

Authors: Karolos Antoniadis, Rachid Guerraoui, Dahlia Malkhi, and Dragos-Adrian Seredinschi

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

Abstract

Consensus and State Machine Replication (SMR) are generally considered to be equivalent problems. In certain system models, indeed, the two problems are computationally equivalent: any solution to the former problem leads to a solution to the latter, and vice versa. In this paper, we study the relation between consensus and SMR from a complexity perspective. We find that, surprisingly, completing an SMR command can be more expensive than solving a consensus instance. Specifically, given a synchronous system model where every instance of consensus always terminates in constant time, completing an SMR command does not necessarily terminate in constant time. This result naturally extends to partially synchronous models. Besides theoretical interest, our result also corresponds to practical phenomena we identify empirically. We experiment with two well-known SMR implementations (Multi-Paxos and Raft) and show that, indeed, SMR is more expensive than consensus in practice. One important implication of our result is that - even under synchrony conditions - no SMR algorithm can ensure bounded response times.

Cite as

Karolos Antoniadis, Rachid Guerraoui, Dahlia Malkhi, and Dragos-Adrian Seredinschi. State Machine Replication Is More Expensive Than Consensus. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 7:1-7:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{antoniadis_et_al:LIPIcs.DISC.2018.7,
  author =	{Antoniadis, Karolos and Guerraoui, Rachid and Malkhi, Dahlia and Seredinschi, Dragos-Adrian},
  title =	{{State Machine Replication Is More Expensive Than Consensus}},
  booktitle =	{32nd International Symposium on Distributed Computing (DISC 2018)},
  pages =	{7:1--7:18},
  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.7},
  URN =		{urn:nbn:de:0030-drops-97961},
  doi =		{10.4230/LIPIcs.DISC.2018.7},
  annote =	{Keywords: Consensus, State machine replication, Synchronous model}
}

Document

DOI: 10.4230/LIPIcs.DISC.2018.8

Allocate-On-Use Space Complexity of Shared-Memory Algorithms

Authors: James Aspnes, Bernhard Haeupler, Alexander Tong, and Philipp Woelfel

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

Abstract

Many fundamental problems in shared-memory distributed computing, including mutual exclusion [James E. Burns and Nancy A. Lynch, 1993], consensus [Leqi Zhu, 2016], and implementations of many sequential objects [Prasad Jayanti et al., 2000], are known to require linear space in the worst case. However, these lower bounds all work by constructing particular executions for any given algorithm that may be both very long and very improbable. The significance of these bounds is justified by an assumption that any space that is used in some execution must be allocated for all executions. This assumption is not consistent with the storage allocation mechanisms of actual practical systems. We consider the consequences of adopting a per-execution approach to space complexity, where an object only counts toward the space complexity of an execution if it is used in that execution. This allows us to show that many known randomized algorithms for fundamental problems in shared-memory distributed computing have expected space complexity much lower than the worst-case lower bounds, and that many algorithms that are adaptive in time complexity can also be made adaptive in space complexity. For the specific problem of mutual exclusion, we develop a new algorithm that illustrates an apparent trade-off between low expected space complexity and low expected RMR complexity. Whether this trade-off is necessary is an open problem. For some applications, it may be helpful to pay only for objects that are updated, as opposed to those that are merely read. We give a data structure that requires no space to represent objects that are not updated at the cost of a small overhead on those that are.

Cite as

James Aspnes, Bernhard Haeupler, Alexander Tong, and Philipp Woelfel. Allocate-On-Use Space Complexity of Shared-Memory Algorithms. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 8:1-8:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{aspnes_et_al:LIPIcs.DISC.2018.8,
  author =	{Aspnes, James and Haeupler, Bernhard and Tong, Alexander and Woelfel, Philipp},
  title =	{{Allocate-On-Use Space Complexity of Shared-Memory Algorithms}},
  booktitle =	{32nd International Symposium on Distributed Computing (DISC 2018)},
  pages =	{8:1--8:17},
  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.8},
  URN =		{urn:nbn:de:0030-drops-97974},
  doi =		{10.4230/LIPIcs.DISC.2018.8},
  annote =	{Keywords: Space complexity, memory allocation, mutual exclusion}
}

65 Search Results for "Schmid, Ulrich"

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Thanks for your feedback!

Could not send message