## Structure, Information and Communication Complexity: Proceedings of the 1st Colloquium on Structural Information and Communication Complexity, Carleton University, Ottawa, CanadaThe ultimate goal of research in Distributed Computing is to understand the nature, properties and limits of computing in a system of autonomous communicating agents. To this end, it is crucial to identify those factors which are significant for the computability and the communication complexity of problems. A crucial role is played by those factors which can be termed Structural Information: its identification, characterization, analysis, and its impact on communication complexity is an important theoretical task which has immediate practical importance. The purpose of the Colloquia on Structural Information and Communication Complexity (SIROCCO) is to focus explicitly on the interaction between structural information and communication complexity. The Colloquia comprise position papers, presentations of current research, and group discussions. Series 1 contains papers presented at the 1st Colloquium on Structural Information and Communication Complexity, held in Ottawa, Canada. Series 2 contains papers presented at the 2nd Colloquium held in Olympia, Greece. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

Preface | 7 |

P Ferragina A Monti A Roncato Pisa | 35 |

Lavault ParisNord | 49 |

E Kranakis D Krizanc Carleton | 68 |

N Norris S Cruz | 83 |

J van Leeuwen R Tan Utrecht | 99 |

J Vounckx J Deconinck R Lauwereins J A Peperstraete Leuven | 125 |

K Diks Hull E Kranakis Carleton A Malinowsky A Pelc Hull | 149 |

### Common terms and phrases

abelian groups anonymous networks anonymous ring assume automorphism Boolean functions Bruijn and Kautz canonical set Carleton University Cayley graph chordal rings coding function communication complexity compact routing complete networks Computer Science consider construction coset coset representative covering map cyclic permutations decoding function defined Definition denote diameter Distributed Algorithms Distributed Computing dynamic cost links edge symmetry edge-label example failure rectangle fault-tolerant Figure functions computable given graph G group Q Hamiltonian cycle Hence hypercubes idempotent injured area input configuration interval routing schemes interval tables invariant under cyclic isomorphism Kautz networks Kranakis Krizanc layout leader election Leeuwen Lemma mesh message complexity minimal symmetries n-Hypercube network topologies node optimum orientation outgoing link pair path representation Proof protocol routing algorithm routing tables Santoro Sense of Direction sequence shortest path stretch factor structural information switches synchronous Theorem tree vertex vertices