Structural Information and Communication Complexity: 26th International Colloquium, SIROCCO 2019, L'Aquila, Italy, July 1–4, 2019, Proceedings

Description

This book constitutes the refereed conference proceedings of the 26th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2019, held in L’Aquila, Italy, in July 2019. The 19 full papers and 9 short papers presented in this book were carefully reviewed and selected from 39 submissions. They are devoted to the study of the interplay between structural knowledge, communication, and computing in decentralized systems of multiple communicating entities. Front Matter ....Pages i-xxi Front Matter ....Pages 1-1 A Topological Perspective on Distributed Network Algorithms (Armando Castañeda, Pierre Fraigniaud, Ami Paz, Sergio Rajsbaum, Matthieu Roy, Corentin Travers)....Pages 3-18 On Sense of Direction and Mobile Agents (Paola Flocchini)....Pages 19-33 Front Matter ....Pages 35-35 Locality of Not-so-Weak Coloring (Alkida Balliu, Juho Hirvonen, Christoph Lenzen, Dennis Olivetti, Jukka Suomela)....Pages 37-51 Near-Gathering of Energy-Constrained Mobile Agents (Andreas Bärtschi, Evangelos Bampas, Jérémie Chalopin, Shantanu Das, Christina Karousatou, Matúš Mihalák)....Pages 52-65 Optimal Multi-broadcast with Beeps Using Group Testing (Joffroy Beauquier, Janna Burman, Peter Davies, Fabien Dufoulon)....Pages 66-80 Tracking Routes in Communication Networks (Davide Bilò, Luciano Gualà, Stefano Leucci, Guido Proietti)....Pages 81-93 Positional Encoding by Robots with Non-rigid Movements (Kaustav Bose, Ranendu Adhikary, Manash Kumar Kundu, Buddhadeb Sau)....Pages 94-108 Arbitrary Pattern Formation by Asynchronous Opaque Robots with Lights (Kaustav Bose, Manash Kumar Kundu, Ranendu Adhikary, Buddhadeb Sau)....Pages 109-123 Breaking the Linear-Memory Barrier in \(\mathsf {MPC}\): Fast \(\mathsf {MIS}\) on Trees with Strongly Sublinear Memory (Sebastian Brandt, Manuela Fischer, Jara Uitto)....Pages 124-138 Collaborative Delivery on a Fixed Path with Homogeneous Energy-Constrained Agents (Jérémie Chalopin, Shantanu Das, Yann Disser, Arnaud Labourel, Matúš Mihalák)....Pages 139-153 Asynchronous Rendezvous with Different Maps (Serafino Cicerone, Gabriele Di Stefano, Leszek Gąsieniec, Alfredo Navarra)....Pages 154-169 Gathering Synchronous Robots in Graphs: From General Properties to Dense and Symmetric Topologies (Serafino Cicerone, Gabriele Di Stefano, Alfredo Navarra)....Pages 170-184 Time-Energy Tradeoffs for Evacuation by Two Robots in the Wireless Model (Jurek Czyzowicz, Konstantinos Georgiou, Ryan Killick, Evangelos Kranakis, Danny Krizanc, Manuel Lafond et al.)....Pages 185-199 Evacuating Two Robots from a Disk: A Second Cut (Yann Disser, Sören Schmitt)....Pages 200-214 Distributed Pattern Formation in a Ring (Anne-Laure Ehresmann, Manuel Lafond, Lata Narayanan, Jaroslav Opatrny)....Pages 215-229 On Distributed Merlin-Arthur Decision Protocols (Pierre Fraigniaud, Pedro Montealegre, Rotem Oshman, Ivan Rapaport, Ioan Todinca)....Pages 230-245 Anonymous Read/Write Memory: Leader Election and De-anonymization (Emmanuel Godard, Damien Imbs, Michel Raynal, Gadi Taubenfeld)....Pages 246-261 Faster Construction of Overlay Networks (Thorsten Götte, Kristian Hinnenthal, Christian Scheideler)....Pages 262-276 Partial Gathering of Mobile Agents Without Identifiers or Global Knowledge in Asynchronous Unidirectional Rings (Masahiro Shibata, Norikazu Kawata, Yuichi Sudo, Fukuhito Ooshita, Hirotsugu Kakugawa, Toshimitsu Masuzawa)....Pages 277-292 Set Agreement Power Is Not a Precise Characterization for Oblivious Deterministic Anonymous Objects (Gadi Taubenfeld)....Pages 293-308 Making Randomized Algorithms Self-stabilizing (Volker Turau)....Pages 309-324 Front Matter ....Pages 325-325 How to Color a French Flag (Bertie Ancona, Ayesha Bajwa, Nancy Lynch, Frederik Mallmann-Trenn)....Pages 327-331 Self-adjusting Linear Networks (Chen Avin, Ingo van Duijn, Stefan Schmid)....Pages 332-335 Mutual Visibility for Asynchronous Robots (Subhash Bhagat, Sruti Gan Chaudhuri, Krishnendu Mukhopadhyaya)....Pages 336-339 Infinite Grid Exploration by Disoriented Robots (Quentin Bramas, Stéphane Devismes, Pascal Lafourcade)....Pages 340-344 A Bounding Box Overlay for Competitive Routing in Hybrid Communication Networks (Jannik Castenow, Christina Kolb, Christian Scheideler)....Pages 345-348 Mobile Robots with Uncertain Visibility Sensors (Adam Heriban, Sébastien Tixeuil)....Pages 349-352 A Strongly-Stabilizing Protocol for Spanning Tree Construction Against a Mobile Byzantine Fault (Koki Inoue, Yuichi Sudo, Hirotsugu Kakugawa, Toshimitsu Masuzawa)....Pages 353-356 Explicit and Tight Bounds of the Convergence Time of Average-Based Population Protocols (Yves Mocquard, Bruno Sericola, Emmanuelle Anceaume)....Pages 357-360 Visiting Infinitely Often the Unit Interval While Minimizing the Idle Time of High Priority Segments (Oscar Morales-Ponce)....Pages 361-365 Back Matter ....Pages 367-368