LIPIcs, Volume 121
DISC 2018, October 15-19, 2018, New Orleans, USA
Editors: Ulrich Schmid and Josef Widder
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
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)
@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} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
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)
@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} }
Published in: LIPIcs, Volume 184, 24th International Conference on Principles of Distributed Systems (OPODIS 2020)
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)
@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} }
Published in: LIPIcs, Volume 153, 23rd International Conference on Principles of Distributed Systems (OPODIS 2019)
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)
@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} }
Published in: LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018)
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)
@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} }
Published in: LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018)
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)
@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} }
Published in: LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018)
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)
@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} }
Published in: LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018)
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)
@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} }
Published in: LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018)
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)
@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} }
Published in: LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018)
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)
@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} }
Published in: LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018)
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)
@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} }
Published in: LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018)
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)
@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} }
Published in: LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018)
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)
@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} }
Published in: LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018)
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)
@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} }
Feedback for Dagstuhl Publishing