Structural Information and Communication Complexity: 26th International Colloquium, SIROCCO 2019, L'Aquila, Italy, July 1–4, 2019, Proceedings (Lecture Notes in Computer Science Book 11639)

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 This book constitutes the refereed proceedings of the 43rd International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2017, held in Limerick, Ireland, in January 2017. The 34 papers presented in this volume were carefully reviewed and selected from 41 submissions. They were organized in topical sections named: foundations in computer science; semantics, specification and compositionality; theory of mobile and distributed systems; verification and automated system analysis; petri nets, games and relaxed data structures; graph theory and scheduling algorithms; quantum and matrix algorithms; planar and molecular graphs; coloring and vertex covers; algorithms for strings and formal languages; data, information and knowledge engineering; and software engineering: methods, tools, applications. This book constitutes the refereed proceedings of the 23rd International Symposium on Algorithms and Computation, ISAAC 2012, held in Taipei, Taiwan, in December 2012. The 68 revised full papers presented together with three invited talks were carefully reviewed and selected from 174 submissions for inclusion in the book. This volume contains topics such as graph algorithms; online and streaming algorithms; combinatorial optimization; computational complexity; computational geometry; string algorithms; approximation algorithms; graph drawing; data structures; randomized algorithms; and algorithmic game theory. This book constitutes the thoroughly refereed post-conference proceedings of the 9th International Symposium on Foundations and Practice of Security, FPS 2016, held in Québec City, QC, Canada, in October 2016. The 18 revised regular papers presented together with 5 short papers and 3 invited talks were carefully reviewed and selected from 34 submissions. The accepted papers cover diverse research themes, ranging from classic topics, such as malware, anomaly detection, and privacy, to emerging issues, such as security and privacy in mobile computing and cloud.