LIPIcs, Volume 246
DISC 2022, October 25-27, 2022, Augusta, Georgia, USA
Editors: Christian Scheideler
Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)
36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 1-790, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@Proceedings{scheideler:LIPIcs.DISC.2022, title = {{LIPIcs, Volume 246, DISC 2022, Complete Volume}}, booktitle = {36th International Symposium on Distributed Computing (DISC 2022)}, pages = {1--790}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-255-6}, ISSN = {1868-8969}, year = {2022}, volume = {246}, editor = {Scheideler, Christian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022}, URN = {urn:nbn:de:0030-drops-171908}, doi = {10.4230/LIPIcs.DISC.2022}, annote = {Keywords: LIPIcs, Volume 246, DISC 2022, Complete Volume} }
Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)
36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 0:i-0:xx, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{scheideler:LIPIcs.DISC.2022.0, author = {Scheideler, Christian}, title = {{Front Matter, Table of Contents, Preface, Conference Organization}}, booktitle = {36th International Symposium on Distributed Computing (DISC 2022)}, pages = {0:i--0:xx}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-255-6}, ISSN = {1868-8969}, year = {2022}, volume = {246}, editor = {Scheideler, Christian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.0}, URN = {urn:nbn:de:0030-drops-171917}, doi = {10.4230/LIPIcs.DISC.2022.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization} }
Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)
Sepehr Assadi. Graph Coloring, Palette Sparsification, and Beyond (Invited Talk). In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, p. 1:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{assadi:LIPIcs.DISC.2022.1, author = {Assadi, Sepehr}, title = {{Graph Coloring, Palette Sparsification, and Beyond}}, booktitle = {36th International Symposium on Distributed Computing (DISC 2022)}, pages = {1:1--1:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-255-6}, ISSN = {1868-8969}, year = {2022}, volume = {246}, editor = {Scheideler, Christian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.1}, URN = {urn:nbn:de:0030-drops-171920}, doi = {10.4230/LIPIcs.DISC.2022.1}, annote = {Keywords: Graph coloring, Palette Sparsification, Sublinear Algorithms} }
Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)
Roberto Baldoni. Managing the Cyber Risk in a Decoupled World: Does This Bring Potential Opportunities in Computer Science? (Invited Talk). In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{baldoni:LIPIcs.DISC.2022.2, author = {Baldoni, Roberto}, title = {{Managing the Cyber Risk in a Decoupled World: Does This Bring Potential Opportunities in Computer Science?}}, booktitle = {36th International Symposium on Distributed Computing (DISC 2022)}, pages = {2:1--2:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-255-6}, ISSN = {1868-8969}, year = {2022}, volume = {246}, editor = {Scheideler, Christian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.2}, URN = {urn:nbn:de:0030-drops-171931}, doi = {10.4230/LIPIcs.DISC.2022.2}, annote = {Keywords: Supply chain decoupling, technology risk, cyber attacks, computing paradigms and methodologies} }
Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)
Jennifer L. Welch. Using Linearizable Objects in Randomized Concurrent Programs (Invited Talk). In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, p. 3:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{welch:LIPIcs.DISC.2022.3, author = {Welch, Jennifer L.}, title = {{Using Linearizable Objects in Randomized Concurrent Programs}}, booktitle = {36th International Symposium on Distributed Computing (DISC 2022)}, pages = {3:1--3:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-255-6}, ISSN = {1868-8969}, year = {2022}, volume = {246}, editor = {Scheideler, Christian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.3}, URN = {urn:nbn:de:0030-drops-171946}, doi = {10.4230/LIPIcs.DISC.2022.3}, annote = {Keywords: Concurrent objects, strong linearizability, impossibility proofs, message-passing systems, randomized algorithms} }
Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)
Timothé Albouy, Davide Frey, Michel Raynal, and François Taïani. Good-Case Early-Stopping Latency of Synchronous Byzantine Reliable Broadcast: The Deterministic Case. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 4:1-4:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{albouy_et_al:LIPIcs.DISC.2022.4, author = {Albouy, Timoth\'{e} and Frey, Davide and Raynal, Michel and Ta\"{i}ani, Fran\c{c}ois}, title = {{Good-Case Early-Stopping Latency of Synchronous Byzantine Reliable Broadcast: The Deterministic Case}}, booktitle = {36th International Symposium on Distributed Computing (DISC 2022)}, pages = {4:1--4:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-255-6}, ISSN = {1868-8969}, year = {2022}, volume = {246}, editor = {Scheideler, Christian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.4}, URN = {urn:nbn:de:0030-drops-171953}, doi = {10.4230/LIPIcs.DISC.2022.4}, annote = {Keywords: Reliable Broadcast, Byzantine Faults, Synchronous Systems, Good-case latency, Deterministic Algorithms} }
Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)
Gal Amram, Avi Hayoun, Lior Mizrahi, and Gera Weiss. Polynomial-Time Verification and Testing of Implementations of the Snapshot Data Structure. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 5:1-5:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{amram_et_al:LIPIcs.DISC.2022.5, author = {Amram, Gal and Hayoun, Avi and Mizrahi, Lior and Weiss, Gera}, title = {{Polynomial-Time Verification and Testing of Implementations of the Snapshot Data Structure}}, booktitle = {36th International Symposium on Distributed Computing (DISC 2022)}, pages = {5:1--5:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-255-6}, ISSN = {1868-8969}, year = {2022}, volume = {246}, editor = {Scheideler, Christian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.5}, URN = {urn:nbn:de:0030-drops-171964}, doi = {10.4230/LIPIcs.DISC.2022.5}, annote = {Keywords: Snapshot, Linearizability, Verification, Formal Methods} }
Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)
Ioannis Anagnostides, Christoph Lenzen, Bernhard Haeupler, Goran Zuzic, and Themis Gouleakis. Almost Universally Optimal Distributed Laplacian Solvers via Low-Congestion Shortcuts. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 6:1-6:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{anagnostides_et_al:LIPIcs.DISC.2022.6, author = {Anagnostides, Ioannis and Lenzen, Christoph and Haeupler, Bernhard and Zuzic, Goran and Gouleakis, Themis}, title = {{Almost Universally Optimal Distributed Laplacian Solvers via Low-Congestion Shortcuts}}, booktitle = {36th International Symposium on Distributed Computing (DISC 2022)}, pages = {6:1--6:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-255-6}, ISSN = {1868-8969}, year = {2022}, volume = {246}, editor = {Scheideler, Christian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.6}, URN = {urn:nbn:de:0030-drops-171978}, doi = {10.4230/LIPIcs.DISC.2022.6}, annote = {Keywords: Distributed algorithms, Laplacian solvers, low-congestion shortcuts} }
Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)
John Augustine, Anisur Rahaman Molla, Gopal Pandurangan, and Yadu Vasudev. Byzantine Connectivity Testing in the Congested Clique. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 7:1-7:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{augustine_et_al:LIPIcs.DISC.2022.7, author = {Augustine, John and Molla, Anisur Rahaman and Pandurangan, Gopal and Vasudev, Yadu}, title = {{Byzantine Connectivity Testing in the Congested Clique}}, booktitle = {36th International Symposium on Distributed Computing (DISC 2022)}, pages = {7:1--7:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-255-6}, ISSN = {1868-8969}, year = {2022}, volume = {246}, editor = {Scheideler, Christian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.7}, URN = {urn:nbn:de:0030-drops-171987}, doi = {10.4230/LIPIcs.DISC.2022.7}, annote = {Keywords: Byzantine protocols, distributed graph algorithms, congested clique, graph connectivity, fault-tolerant computation, randomized algorithms} }
Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)
Alkida Balliu, Sebastian Brandt, Yi-Jun Chang, Dennis Olivetti, Jan Studený, and Jukka Suomela. Efficient Classification of Locally Checkable Problems in Regular Trees. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 8:1-8:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{balliu_et_al:LIPIcs.DISC.2022.8, author = {Balliu, Alkida and Brandt, Sebastian and Chang, Yi-Jun and Olivetti, Dennis and Studen\'{y}, Jan and Suomela, Jukka}, title = {{Efficient Classification of Locally Checkable Problems in Regular Trees}}, booktitle = {36th International Symposium on Distributed Computing (DISC 2022)}, pages = {8:1--8:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-255-6}, ISSN = {1868-8969}, year = {2022}, volume = {246}, editor = {Scheideler, Christian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.8}, URN = {urn:nbn:de:0030-drops-171993}, doi = {10.4230/LIPIcs.DISC.2022.8}, annote = {Keywords: locally checkable labeling, locality, distributed computational complexity} }
Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)
Alkida Balliu, Sebastian Brandt, Manuela Fischer, Rustam Latypov, Yannic Maus, Dennis Olivetti, and Jara Uitto. Exponential Speedup over Locality in MPC with Optimal Memory. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 9:1-9:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{balliu_et_al:LIPIcs.DISC.2022.9, author = {Balliu, Alkida and Brandt, Sebastian and Fischer, Manuela and Latypov, Rustam and Maus, Yannic and Olivetti, Dennis and Uitto, Jara}, title = {{Exponential Speedup over Locality in MPC with Optimal Memory}}, booktitle = {36th International Symposium on Distributed Computing (DISC 2022)}, pages = {9:1--9:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-255-6}, ISSN = {1868-8969}, year = {2022}, volume = {246}, editor = {Scheideler, Christian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.9}, URN = {urn:nbn:de:0030-drops-172003}, doi = {10.4230/LIPIcs.DISC.2022.9}, annote = {Keywords: Distributed computing, Locally checkable labeling problems, Trees, Massively Parallel Computation, Sublinear memory} }
Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)
Nathalie Bertrand, Vincent Gramoli, Igor Konnov, Marijana Lazić, Pierre Tholoniat, and Josef Widder. Holistic Verification of Blockchain Consensus. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 10:1-10:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{bertrand_et_al:LIPIcs.DISC.2022.10, author = {Bertrand, Nathalie and Gramoli, Vincent and Konnov, Igor and Lazi\'{c}, Marijana and Tholoniat, Pierre and Widder, Josef}, title = {{Holistic Verification of Blockchain Consensus}}, booktitle = {36th International Symposium on Distributed Computing (DISC 2022)}, pages = {10:1--10:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-255-6}, ISSN = {1868-8969}, year = {2022}, volume = {246}, editor = {Scheideler, Christian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.10}, URN = {urn:nbn:de:0030-drops-172019}, doi = {10.4230/LIPIcs.DISC.2022.10}, annote = {Keywords: Model checking, automata, logic, byzantine failure} }
Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)
Subhash Bhagat and Andrzej Pelc. How to Meet at a Node of Any Connected Graph. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 11:1-11:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{bhagat_et_al:LIPIcs.DISC.2022.11, author = {Bhagat, Subhash and Pelc, Andrzej}, title = {{How to Meet at a Node of Any Connected Graph}}, booktitle = {36th International Symposium on Distributed Computing (DISC 2022)}, pages = {11:1--11:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-255-6}, ISSN = {1868-8969}, year = {2022}, volume = {246}, editor = {Scheideler, Christian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.11}, URN = {urn:nbn:de:0030-drops-172024}, doi = {10.4230/LIPIcs.DISC.2022.11}, annote = {Keywords: Algorithm, graph, rendezvous, mobile agent, terrain} }
Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)
Manuel Bravo, Gregory Chockler, and Alexey Gotsman. Liveness and Latency of Byzantine State-Machine Replication. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 12:1-12:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{bravo_et_al:LIPIcs.DISC.2022.12, author = {Bravo, Manuel and Chockler, Gregory and Gotsman, Alexey}, title = {{Liveness and Latency of Byzantine State-Machine Replication}}, booktitle = {36th International Symposium on Distributed Computing (DISC 2022)}, pages = {12:1--12:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-255-6}, ISSN = {1868-8969}, year = {2022}, volume = {246}, editor = {Scheideler, Christian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.12}, URN = {urn:nbn:de:0030-drops-172037}, doi = {10.4230/LIPIcs.DISC.2022.12}, annote = {Keywords: Replication, blockchain, partial synchrony, liveness} }
Feedback for Dagstuhl Publishing