Stabilization, Safety, and Security of Distributed Systems 20th International Symposium, SSS 2018, Tokyo, Japan, November 4-7, 2018, Proceedings. Theoretical Computer Science and General Issues

This book constitutes the refereed proceedings of the 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems, SSS 2018, held in Tokyo, Japan, in November 2018. The 24 revised full papers presented were carefully reviewed and selected from 55 submissions. The papers are organized into three tracks reflecting major trends related to distributed systems: theoretical and practical aspects of stabilizing systems; distributed networks and concurrency; and safety in malicious environments. Front Matter ....Pages I-XIII A Self-stabilizing Hashed Patricia Trie (Till Knollmann, Christian Scheideler)....Pages 1-15 Self-stabilizing Overlays for High-Dimensional Monotonic Searchability (Michael Feldmann, Christina Kolb, Christian Scheideler)....Pages 16-31 An Adaptive Logging Framework for Persistent Memories (Pavan Poudel, Gokarna Sharma)....Pages 32-49 On Underlay-Aware Self-Stabilizing Overlay Networks (Thorsten Götte, Christian Scheideler, Alexander Setzer)....Pages 50-64 A \(O(\log n)\) Distributed Algorithm to Construct Routing Structures for Pub/Sub Systems (Volker Turau)....Pages 65-79 Self-stabilization and Byzantine Tolerance for Maximal Matching (Stephan Kunne, Johanne Cohen, Laurence Pilard)....Pages 80-95 Exploration of Finite 2D Square Grid by a Metamorphic Robotic System (Keisuke Doi, Yukiko Yamauchi, Shuji Kijima, Masafumi Yamashita)....Pages 96-110 Physical Zero-Knowledge Proof for Makaro (Xavier Bultel, Jannik Dreier, Jean-Guillaume Dumas, Pascal Lafourcade, Daiki Miyahara, Takaaki Mizuki et al.)....Pages 111-125 Searching with Increasing Speeds (Leszek Gąsieniec, Shuji Kijima, Jie Min)....Pages 126-138 Bee’s Strategy Against Byzantines Replacing Byzantine Participants (Amitay Shaer, Shlomi Dolev, Silvia Bonomi, Michel Raynal, Roberto Baldoni)....Pages 139-153 Simple and Fast Approximate Counting and Leader Election in Populations (Othon Michail, Paul G. Spirakis, Michail Theofilatos)....Pages 154-169 Reliable Broadcast in Dynamic Networks with Locally Bounded Byzantine Failures (Silvia Bonomi, Giovanni Farina, Sébastien Tixeuil)....Pages 170-185 Acyclic Strategy for Silent Self-stabilization in Spanning Forests (Karine Altisen, Stéphane Devismes, Anaïs Durand)....Pages 186-202 On Fast Pattern Formation by Autonomous Robots (Ramachandran Vaidyanathan, Gokarna Sharma, Jerry L. Trahan)....Pages 203-220 Load Balanced Distributed Directories (Shishir Rai, Gokarna Sharma, Costas Busch, Maurice Herlihy)....Pages 221-238 Relays: A New Approach for the Finite Departure Problem in Overlay Networks (Christian Scheideler, Alexander Setzer)....Pages 239-253 Clairvoyant State Machine Replications (Rida Bazzi, Maurice Herlihy)....Pages 254-268 Set Agreement and Renaming in the Presence of Contention-Related Crash Failures (Anaïs Durand, Michel Raynal, Gadi Taubenfeld)....Pages 269-283 An Innovative Approach to Achieve Compositionality Efficiently Using Multi-version Object Based Transactional Systems (Chirag Juyal, Sandeep Kulkarni, Sweta Kumari, Sathya Peri, Archit Somani)....Pages 284-300 Ring Exploration with Myopic Luminous Robots (Fukuhito Ooshita, Sébastien Tixeuil)....Pages 301-316 Uniform Circle Formation for Swarms of Opaque Robots with Lights (Caterina Feletti, Carlo Mereghetti, Beatrice Palano)....Pages 317-332 Arbitrary Pattern Formation with Four Robots (Quentin Bramas, Sébastien Tixeuil)....Pages 333-348 Gracefully Degrading Gathering in Dynamic Rings (Marjorie Bournat, Swan Dubois, Franck Petit)....Pages 349-364 Concurrent Lock-Free Unbounded Priority Queue with Mutable Priorities (Ivan Walulya, Bapi Chatterjee, Ajoy K. Datta, Rashmi Niyolia, Philippas Tsigas)....Pages 365-380 Brief Announcement: Deterministic Leader Election in Self-organizing Particle Systems (Rida A. Bazzi, Joseph L. Briones)....Pages 381-386 Brief Announcement: Time Efficient Self-stabilizing Stable Marriage (Joffroy Beauquier, Thibault Bernard, Janna Burman, Shay Kutten, Marie Laveau)....Pages 387-392 Brief Announcement: Feasibility of Weak Gathering in Connected-over-Time Dynamic Rings (Fukuhito Ooshita, Ajoy K. Datta)....Pages 393-397 Brief Announcement: Optimal Self-stabilizing Mobile Byzantine-Tolerant Regular Register with Bounded Timestamps (Silvia Bonomi, Antonella Del Pozzo, Maria Potop-Butucaru, Sébastien Tixeuil)....Pages 398-403 Brief Announcement Continuous vs. Discrete Asynchronous Moves: A Certified Approach for Mobile Robots (Thibaut Balabonski, Pierre Courtieu, Robin Pelle, Lionel Rieg, Sébastien Tixeuil, Xavier Urbain)....Pages 404-408 Back Matter ....Pages 409-410