67 Search Results for "Schmid, Ulrich"

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/DagRep.13.7.34
Epistemic and Topological Reasoning in Distributed Systems (Dagstuhl Seminar 23272)

Authors: Armando Castañeda, Hans van Ditmarsch, Roman Kuznets, Yoram Moses, and Ulrich Schmid

Published in: Dagstuhl Reports, Volume 13, Issue 7 (2024)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 23272 "Epistemic and Topological Reasoning in Distributed Systems." The seminar brought together experts in combinatorial topology and epistemic logic interested in distributed systems, with the aim of exploring the directions that the recent interaction between those approaches can take, identifying challenges and opportunities.
Cite as

Armando Castañeda, Hans van Ditmarsch, Roman Kuznets, Yoram Moses, and Ulrich Schmid. Epistemic and Topological Reasoning in Distributed Systems (Dagstuhl Seminar 23272). In Dagstuhl Reports, Volume 13, Issue 7, pp. 34-65, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@Article{castaneda_et_al:DagRep.13.7.34,
  author =	{Casta\~{n}eda, Armando and van Ditmarsch, Hans and Kuznets, Roman and Moses, Yoram and Schmid, Ulrich},
  title =	{{Epistemic and Topological Reasoning in Distributed Systems (Dagstuhl Seminar 23272)}},
  pages =	{34--65},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2024},
  volume =	{13},
  number =	{7},
  editor =	{Casta\~{n}eda, Armando and van Ditmarsch, Hans and Kuznets, Roman and Moses, Yoram and Schmid, Ulrich},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.13.7.34},
  URN =		{urn:nbn:de:0030-drops-197742},
  doi =		{10.4230/DagRep.13.7.34},
  annote =	{Keywords: combinatorial topology, distributed systems, epistemic logic, multi-agent systems, interpreted systems, dynamic epistemic logic, simplicial semantics, knowledge-based approach, distributed computing}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2023.20
Flooding with Absorption: An Efficient Protocol for Heterogeneous Bandits over Complex Networks

Authors: Junghyun Lee, Laura Schmid, and Se-Young Yun

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

Abstract
Multi-armed bandits are extensively used to model sequential decision-making, making them ubiquitous in many real-life applications such as online recommender systems and wireless networking. We consider a multi-agent setting where each agent solves their own bandit instance endowed with a different set of arms. Their goal is to minimize their group regret while collaborating via some communication protocol over a given network. Previous literature on this problem only considered arm heterogeneity and networked agents separately. In this work, we introduce a setting that encompasses both features. For this novel setting, we first provide a rigorous regret analysis for a standard flooding protocol combined with the classic UCB policy. Then, to mitigate the issue of high communication costs incurred by flooding in complex networks, we propose a new protocol called Flooding with Absorption (FwA). We provide a theoretical analysis of the resulting regret bound and discuss the advantages of using FwA over flooding. Lastly, we experimentally verify on various scenarios, including dynamic networks, that FwA leads to significantly lower communication costs despite minimal regret performance loss compared to other network protocols.
Cite as

Junghyun Lee, Laura Schmid, and Se-Young Yun. Flooding with Absorption: An Efficient Protocol for Heterogeneous Bandits over Complex Networks. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 20:1-20:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{lee_et_al:LIPIcs.OPODIS.2023.20,
  author =	{Lee, Junghyun and Schmid, Laura and Yun, Se-Young},
  title =	{{Flooding with Absorption: An Efficient Protocol for Heterogeneous Bandits over Complex Networks}},
  booktitle =	{27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
  pages =	{20:1--20:25},
  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.20},
  URN =		{urn:nbn:de:0030-drops-195100},
  doi =		{10.4230/LIPIcs.OPODIS.2023.20},
  annote =	{Keywords: multi-armed bandits, multi-agent systems, collaborative learning, network protocol, flooding}
}
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

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

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}
}
  • Refine by Author
  • 8 Schmid, Ulrich
  • 5 Ghaffari, Mohsen
  • 4 Kuhn, Fabian
  • 3 Afek, Yehuda
  • 3 Czumaj, Artur
  • Show More...

  • Refine by Classification
  • 26 Theory of computation → Distributed algorithms
  • 15 Theory of computation → Distributed computing models
  • 5 Computing methodologies → Distributed algorithms
  • 4 Networks → Network algorithms
  • 3 Mathematics of computing → Graph algorithms
  • Show More...

  • Refine by Keyword
  • 5 Distributed Graph Algorithms
  • 5 fault tolerance
  • 3 Consensus
  • 3 Distributed Algorithms
  • 3 consensus
  • Show More...

  • Refine by Type
  • 66 document
  • 1 volume

  • Refine by Publication Year
  • 55 2018
  • 6 2009
  • 2 2024
  • 1 2020
  • 1 2021
  • Show More...

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 Imprint Privacy Contact