Structural Information and Communication Complexity : 18th International Colloquium, SIROCCO 2011, Gdańsk, Poland, June 2011, Proceedings

by Kosowski, Adrian; Yamashita, Masafumi

• ISBN13: 9783642222115
• ISBN10: 3642222110
• Format: Paperback
• Copyright: 2011-09-28
• Publisher: Springer-Verlag New York Inc

Summary

This book constitutes the refereed proceedings of the 18th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2011, held in GdaÅ ;sk, Poland, in June 2011. The 24 revised full papers presented together with 1 survey lecture and 2 invited talks were carefully reviewed and selected from 57 submissions. The papers are organized in topical section on fault tolerance, routing, mobile agents, mobile robots, probabilistic methods, distributed algorithms on graphs, and ad-hoc networks.

Table of Contents

Invited Talks
Random Walks, Interacting Particles, Dynamic Networks: Randomness Can Be Helpful	p. 1
SINR Maps: Properties and Applications	p. 15
Survey Talk
A Survey on Some Recent Advances in Shared Memory Models	p. 17
Fault Tolerance
Consensus vs. Broadcast in Communication Networks with Arbitrary Mobile Omission Faults	p. 29
Reconciling Fault-Tolerant Distributed Algorithms and Real-Time Computing (Extended Abstract)	p. 42
Self-stabilizing Hierarchical Construction of Bounded Size Clusters	p. 54
The Universe of Symmetry Breaking Tasks	p. 66
Routing
Determining the Conditional Diagnosability of k-Azy n-Cubes under the MM* Model	p. 78
Medium Access Control for Adversarial Channels with Jamming	p. 89
Full Reversal Routing as a Linear Dynamical System	p. 101
Partial is Full	p. 113
Mobile Agents/Robots (I)
Convergence with Limited Visibility by Asynchronous Mobile Robots	p. 125
Energy-Efficient Strategies for Building Short Chains of Mobile Robots Locally	p. 138
Asynchronous Mobile Robot Gathering from Symmetric Configurations without Global Multiplicity Detection	p. 150
Mobile Agents/Robots (II)
Gathering Asynchronous Oblivious Agents with Local Vision in Regular Bipartite Graphs	p. 162
Gathering of Six Robots on Anonymous Symmetric Rings	p. 174
Tight Bounds for Scattered Black Hole Search in a Ring	p. 186
Improving the Optimal Bounds for Black Hole Search in Rings	p. 198
Probabilistic Methods
The Cover Times of Random Walks on Hypergraphs	p. 210
Routing in Carrier-Based Mobile Networks	p. 222
On the Performance of a Retransmission-Based Synchronizer	p. 234
Distributed Algorithms on Graphs
Distributed Coloring Depending on the Chromatic Number or the Neighborhood Growth	p. 246
Multiparty Equality Function Computation in Networks with Point-to-Point Links	p. 258
Network Verification via Routing Table Queries	p. 270
Social Context Congestion Games	p. 282
Ad-hoc Networks
Network Synchronization and Localization Based on Stolen Signals	p. 294
Optimal Time Data Gathering in Wireless Networks with Omni-Directional Antennas	p. 306
Author Index	p. 319
Table of Contents provided by Ingram. All Rights Reserved.