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

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. Front Matter....Pages - Random Walks, Interacting Particles, Dynamic Networks: Randomness Can Be Helpful....Pages 1-14 SINR Maps: Properties and Applications....Pages 15-16 A Survey on Some Recent Advances in Shared Memory Models....Pages 17-28 Consensus vs. Broadcast in Communication Networks with Arbitrary Mobile Omission Faults....Pages 29-41 Reconciling Fault-Tolerant Distributed Algorithms and Real-Time Computing....Pages 42-53 Self-stabilizing Hierarchical Construction of Bounded Size Clusters....Pages 54-65 The Universe of Symmetry Breaking Tasks....Pages 66-77 Determining the Conditional Diagnosability of k -Ary n -Cubes Under the MM* Model....Pages 78-88 Medium Access Control for Adversarial Channels with Jamming....Pages 89-100 Full Reversal Routing as a Linear Dynamical System....Pages 101-112 Partial is Full....Pages 113-124 Convergence with Limited Visibility by Asynchronous Mobile Robots....Pages 125-137 Energy-Efficient Strategies for Building Short Chains of Mobile Robots Locally....Pages 138-149 Asynchronous Mobile Robot Gathering from Symmetric Configurations without Global Multiplicity Detection....Pages 150-161 Gathering Asynchronous Oblivious Agents with Local Vision in Regular Bipartite Graphs....Pages 162-173 Gathering of Six Robots on Anonymous Symmetric Rings....Pages 174-185 Tight Bounds for Scattered Black Hole Search in a Ring....Pages 186-197 Improving the Optimal Bounds for Black Hole Search in Rings....Pages 198-209 The Cover Times of Random Walks on Hypergraphs....Pages 210-221 Routing in Carrier-Based Mobile Networks....Pages 222-233 On the Performance of a Retransmission-Based Synchronizer....Pages 234-245 Distributed Coloring Depending on the Chromatic Number or the Neighborhood Growth....Pages 246-257 Multiparty Equality Function Computation in Networks with Point-to-Point Links....Pages 258-269 Network Verification via Routing Table Queries....Pages 270-281 Social Context Congestion Games....Pages 282-293 Network Synchronization and Localization Based on Stolen Signals....Pages 294-305 Optimal Time Data Gathering in Wireless Networks with Omni–Directional Antennas....Pages 306-317 Back Matter....Pages - This book constitutes the refereed proceedings of the 18th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2011, held in Gdansk, Poland, in June 2011.