Abstract
Considerable research efforts in the field of Distributed Computing are directed at understanding the nature, the properties, and the limits of systems of autonomous communicating agents.
The 6th Colloquium on Structural Information and Communication Complexity (SIROCCO) was held at Hotel-Golf de l'Ardilouse, Lacanau Océan, France. It focussed on the relationship between computing and communication, and the study of those factors that are significant for the computability and the communication complexity of problems, and on the interplay between structure, knowledge, and complexity in systems of communicating agents. Original papers were solicited on the interplay between structure (for example, topology), knowledge, and complexity in distributed computing, parallel computing, mobile computing, optical computing, interconnection networks, wireless networks, high-speed networks, and so on.
The colloquium consisted of three invited talks, twenty contributed presentations, and a number of open problem sessions. The papers presented in this book are the revised versions of the contributed papers, and form a written record of the colloquium. The revisions have been based on the comments and suggestions received by the authors from referees and participants of the colloquium. Several papers are in the form of preliminary reports on ongoing research. It is expected that more elaborate versions of these papers will appear in the special issue of the conference in the journal of Theoretical Computer Science.
We hope that this volume gives a good impression of activities in the topic of Structural Information and Communication Complexity. Unfortunately, we cannot include, of course, the live discussions that have been a focal point of the colloquium.
We would like to thank the other members of the program committee (Amotz Bar-Noy, Jean-Claude Bermond, Francesc Comellas, Michel Cosnard, Michele Flammini, Satoshi Fujita, Ori Gerstel, Ronald Graham, Marie-Claude Heydemann, Christos Kaklamanis, Francis Lau, Burkhard Monien, David Peleg, Stéphane Perennes, Joseph Peters, Sergio Rajsbaum, Arnold Rosenberg, Peter Ruzicka, Nicola Santoro, Richard Tan, Ugo Vaccaro, Paul Vitanyi, Shmuel Zaks), André Raspaud, and as well as the organizing committee (Olivier Delmas, Guillaume Fertin, Nicolas Hanusse, Olivier Togni).
The colloquium and these proceedings have been supported in part by: Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université Bordeaux I, GdR - CNRS ARP, France Télécom, CNRS, and La Région Aquitaine. Their support is gratefully acknowledged.
Table of Contents
Cyril Gavoille, Jean-Claude Bermond, and André Raspaud
v .... Preface
W. Aiello, S. Bhatt, F. Chung, A. Rosenberg, and R. Sitaraman
1 .... Augmented Ring Networks
L. Barrière
17 .... Triangulations and Chordal Rings
A. Bui, A. K. Datta, F. Petit, V. Villain
32 .... Snap-Stabilizing PIF Algorithm in Trees
C. Busch, N. Demetriou, M. Herlihy, M. Mavronicolas
47 .... Threshold Counters with Increments and Decrements
S. Cicerone, G. Di Stefano, M. Flammini
62 .... Compact-Port Routing Models and Applications to Distance-Hereditary Graphs
Suprakash Datta and Ramesh K. Sitaraman
78 .... Convergence and Concentration Results for Packet Routing Networks
S. Dobrev
93 .... Leader Election using Any Sense of Direction
S. Dobrev, H. Schröder, O. Sykora, I. Vrto
105 .... Evolutionary Graph Colouring
S. Dolev, R. Segala, A. Shvartsman
111 .... Irreversible Dynamos in Tori
A. M. Farley, P. Fragopoulou, D. Krumme, A. Proskurowski, D. Richards
126 .... Multi-Source Spanning Tree Problems
G. Fertin
137 .... Trade-Offs for Odd Gossiping
P. Flocchini, E. Lodi, F. Luccio, L. Pagli, N. Santoro
152 .... Monotone Dynamos in Tori
P. Gvozdjak, J. Peters
166 .... Gossiping in Inclined LEO Satellite Networks
R. Kralovic, P. Ruzicka
181 .... Rank of Graphs: The Size of Acyclic Orientation Cover for Deadlock-Free Packet Routing
E. Kranakis, D. Krizanc
194 .... Searching with Uncertainty
F. Luccio, L. Pagli, H. Sanossian
204 .... Irreversible Dynamos in Butterflies
J. Manuch, L. Stacho
219 .... Fault-tolerant Wavelength Allocations in All-optical Hypercubes
S. Rajsbaum, J. Urrutia
233 .... Some Problems in Distributed Computational Geometry
J. F. Sibeyn
249 .... Power and Limitations of Optical Reconfigurable Arrays
S. S. H. Tse, C. M. Lau
264 .... Some Results on the Space Requirement of Interval Routing