Structural Information and Communication Complexity: 24th International Colloquium, SIROCCO 2017, Porquerolles, France, June 19-22, 2017, Revised Selected Papers

Description

This book constitutes the thoroughly refereed proceedings of the 24th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2017, held in Porquerolles, France, in June 2017. The 21 full papers presented were carefully reviewed and selected from 41 submissions. They are devoted to the study of the interplay between structural knowledge, communications, and computing in decentralized systems of multiple communicating entities. They are organized around the following topics: wireless networks; identifiers and labeling; mobile agents; probabilistic algorithms; computational complexity; dynamic networks. Front Matter ....Pages I-XXIX Front Matter ....Pages 1-1 Leader Election in SINR Model with Arbitrary Power Control (Magnús M. Halldórsson, Stephan Holzer, Evangelia Anna Markatou)....Pages 3-14 Token Traversal in Ad Hoc Wireless Networks via Implicit Carrier Sensing (Tomasz Jurdzinski, Michal Rozanski, Grzegorz Stachowiak)....Pages 15-33 Front Matter ....Pages 35-35 Short Labeling Schemes for Topology Recognition in Wireless Tree Networks (Barun Gorain, Andrzej Pelc)....Pages 37-52 Space-Time Tradeoffs for Distributed Verification (Rafail Ostrovsky, Mor Perry, Will Rosenbaum)....Pages 53-70 Approximate Proof-Labeling Schemes (Keren Censor-Hillel, Ami Paz, Mor Perry)....Pages 71-89 Global Versus Local Computations: Fast Computing with Identifiers (Mikaël Rabie)....Pages 90-105 On the Smallest Grain of Salt to Get a Unique Identity (Peva Blanchard, Rachid Guerraoui)....Pages 106-121 Front Matter ....Pages 123-123 A General Lower Bound for Collaborative Tree Exploration (Yann Disser, Frank Mousset, Andreas Noever, Nemanja Škorić, Angelika Steger)....Pages 125-139 Wireless Evacuation on m Rays with k Searchers (Sebastian Brandt, Klaus-Tycho Foerster, Benjamin Richner, Roger Wattenhofer)....Pages 140-157 Evacuation from a Disc in the Presence of a Faulty Robot (Jurek Czyzowicz, Konstantinos Georgiou, Maxime Godon, Evangelos Kranakis, Danny Krizanc, Wojciech Rytter et al.)....Pages 158-173 On Location Hiding in Distributed Systems (Karol Gotfryd, Marek Klonowski, Dominik Pająk)....Pages 174-192 Front Matter ....Pages 193-193 Parallel Search with No Coordination (Amos Korman, Yoav Rodeh)....Pages 195-211 Monitoring of Domain-Related Problems in Distributed Data Streams (Pascal Bemmann, Felix Biermeier, Jan Bürmann, Arne Kemper, Till Knollmann, Steffen Knorr et al.)....Pages 212-226 Killing Nodes as a Countermeasure to Virus Expansion (François Bonnet, Quentin Bramas, Xavier Défago, Thanh Dang Nguyen)....Pages 227-243 Front Matter ....Pages 245-245 Improved Distributed Algorithms for Coloring Interval Graphs with Application to Multicoloring Trees (Magnús M. Halldórsson, Christian Konrad)....Pages 247-262 How Long It Takes for an Ordinary Node with an Ordinary ID to Output? (Laurent Feuilloley)....Pages 263-282 How to Choose Friends Strategically (Lata Narayanan, Kangkang Wu)....Pages 283-302 Effective Edge-Fault-Tolerant Single-Source Spanners via Best (or Good) Swap Edges (Davide Bilò, Feliciano Colella, Luciano Gualà, Stefano Leucci, Guido Proietti)....Pages 303-317 Front Matter ....Pages 319-319 A Generic Framework for Computing Parameters of Sequence-Based Dynamic Graphs (Arnaud Casteigts, Ralf Klasing, Yessin M. Neggaz, Joseph G. Peters)....Pages 321-338 Gathering in Dynamic Rings (Giuseppe Antonio Di Luna, Paola Flocchini, Linda Pagli, Giuseppe Prencipe, Nicola Santoro, Giovanni Viglietta)....Pages 339-355 On Liveness of Dynamic Storage (Alexander Spiegelman, Idit Keidar)....Pages 356-376 Back Matter ....Pages 377-377