Structural Information and Communication Complexity

1. Front Matter

   PDF

2. Space Lower Bounds for Low-Stretch Greedy Embeddings

   • Ioannis Caragiannis, Christos Kalaitzis

   Pages 1-12

3. The Fault Tolerant Capacitated k-Center Problem

   • Shiri Chechik, David Peleg

   Pages 13-24

4. Notions of Connectivity in Overlay Networks

   • Yuval Emek, Pierre Fraigniaud, Amos Korman, Shay Kutten, David Peleg

   Pages 25-35

5. Changing of the Guards: Strip Cover with Duty Cycling

   • Amotz Bar-Noy, Ben Baumer, Dror Rawitz

   Pages 36-47

6. Deterministic Local Algorithms, Unique Identifiers, and Fractional Graph Colouring

   • Henning Hasemann, Juho Hirvonen, Joel Rybicki, Jukka Suomela

   Pages 48-60

7. An Algorithm for Online Facility Leasing

   • Peter Kling, Friedhelm Meyer auf der Heide, Peter Pietrzyk

   Pages 61-72

8. Agreement in Directed Dynamic Networks

   • Martin Biely, Peter Robinson, Ulrich Schmid

   Pages 73-84

9. Bounding Interference in Wireless Ad Hoc Networks with Nodes in Random Position

   • Majid Khabbazian, Stephane Durocher, Alireza Haghnegahdar

   Pages 85-98

10. Strong Connectivity of Sensor Networks with Double Antennae

    • Mohsen Eftekhari Hesari, Evangelos Kranakis, Fraser MacQuarie, Oscar Morales-Ponce, Lata Narayanan

    Pages 99-110

11. Distributed Multiple-Message Broadcast in Wireless Ad-Hoc Networks under the SINR Model

    • Dongxiao Yu, Qiang-Sheng Hua, Yuexuan Wang, Haisheng Tan, Francis C. M. Lau

    Pages 111-122

12. Wireless Network Stability in the SINR Model

    • Eyjólfur Ingi Ásgeirsson, Magnús M. Halldórsson, Pradipta Mitra

    Pages 123-134

13. What Can Be Computed without Communications?

    • Heger Arfaoui, Pierre Fraigniaud

    Pages 135-146

14. On Bidimensional Congestion Games

    • Vittorio Bilò, Michele Flammini, Vasco Gallotti

    Pages 147-158

15. Mobile Network Creation Games

    • Michele Flammini, Vasco Gallotti, Giovanna Melideo, Gianpiero Monaco, Luca Moscardelli

    Pages 159-170

16. Homonyms with Forgeable Identifiers

    • Carole Delporte-Gallet, Hugues Fauconnier, Hung Tran-The

    Pages 171-182

17. Asynchrony and Collusion in the N-party BAR Transfer Problem

    • Xavier Vilaça, Oksana Denysyuk, Luís Rodrigues

    Pages 183-194

18. Early Deciding Synchronous Renaming in O( logf ) Rounds or Less

    • Dan Alistarh, Hagit Attiya, Rachid Guerraoui, Corentin Travers

    Pages 195-206

19. On Snapshots and Stable Properties Detection in Anonymous Fully Distributed Systems (Extended Abstract)

    • Jérémie Chalopin, Yves Métivier, Thomas Morsellino

    Pages 207-218

20. Self-stabilizing (k,r)-Clustering in Clock Rate-Limited Systems

    • Andreas Larsson, Philippas Tsigas

    Pages 219-230

This book constitutes the refereed proceedings of the 19th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2012, held in Reykjavik, Iceland for 3 days starting June 30, 2012. The 28 revised full papers presented were carefully reviewed and selected from 54 submissions. SIROCCO is devoted to the study of communication and knowledge in distributed systems. Special emphasis is given to innovative approaches and fundamental understanding, in addition to efforts to optimize current designs. The typical areas include distributed computing, communication networks, game theory, parallel computing, social networks, mobile computing (including autonomous robots), peer to peer systems, communication complexity, fault tolerant graph theories, and randomized/probabilistic issues in networks.

• anonymous networks
• distributed algorithms
• graph theory
• mobile networks
• wireless networks
• algorithm analysis and problem complexity
• data structures

• School of Electrical Engineering,, Tel-Aviv University, Tel Aviv, Israel

  Guy Even

• ICE-TCS School of Computer Science, Reykjavik University, Reykjavik,, Iceland

  Magnús M. Halldórsson

Policies and ethics