Proceedings of the 6th International Colloquium on Structural Information & Communication Complexity

SIROCCO 6, Carleton Scientific, 1-3 July 1999

Cyril Gavoille, Jean-Claude Bermond, and André Raspaud


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