Structure, Information and Communication Complexity: Proceedings of the 1st Colloquium on Structural Information and Communication Complexity, Carleton University, Ottawa, Canada
The 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.
Lietotāju komentāri - Rakstīt atsauksmi
Ierastajās vietās neesam atraduši nevienu atsauksmi.
P Ferragina A Monti A Roncato Pisa
E Kranakis D Krizanc Carleton
N Norris S Cruz
J van Leeuwen R Tan Utrecht
J Vounckx J Deconinck R Lauwereins J A Peperstraete Leuven
K Diks Hull E Kranakis Carleton A Malinowsky A Pelc Hull
abelian allows arbitrary associated assume automorphism block Boolean functions bound called Carleton University Cayley networks chordal rings communication compact complexity Computer Computer Science connected consider consistent construction contains Contracted corresponding cost cyclic defined Definition denote destination Distributed Algorithms Distributed Computing edge election example execution exists extended fact failure cycle Figure function give given graph Hence hypercubes injured interval interval routing Italy known labeling layout leader Lemma length load mesh messages minimal node Note optimal orientation pair particular permutations possible problem processors Proof properties prove reach References represented requires respect ring routing algorithm routing scheme routing tables satisfies Sense of Direction sequence shortest path shown steps string structure switches symmetry synchronous Theorem topologies tree unique University vertex vertices