Structural Information and Communication Complexity

1. Front Matter

   PDF

2. Invited Talks

   1. Mobile Entities Computing: Models and Problems

      • Nicola Santoro

      Pages 1-1

   2. Reputation, Trust and Recommendation Systems in Peer-to-Peer Systems

      • Boaz Patt-Shamir

      Pages 2-4

3. Regular Papers

   1. Gathering Problem of Two Asynchronous Mobile Robots with Semi-dynamic Compasses

      • Nobuhiro Inuzuka, Yuichi Tomida, Taisuke Izumi, Yoshiaki Katayama, Koichi Wada

      Pages 5-19

   2. Locating and Repairing Faults in a Network with Mobile Agents

      • Colin Cooper, Ralf Klasing, Tomasz Radzik

      Pages 20-32

   3. Remembering without Memory: Tree Exploration by Asynchronous Oblivious Robots

      • Paola Flocchini, David Ilcinkas, Andrzej Pelc, Nicola Santoro

      Pages 33-47

   4. Average Binary Long-Lived Consensus: Quantifying the Stabilizing Role Played by Memory

      • Florent Becker, Sergio Rajsbaum, Ivan Rapaport, Éric Rémila

      Pages 48-60

   5. Distributed Approximation Algorithm for Resource Clustering

      • Olivier Beaumont, Nicolas Bonichon, Philippe Duchon, Hubert Larchevêque

      Pages 61-73

   6. Sharpness: A Tight Condition for Scalability

      • Augustin Chaintreau

      Pages 74-88

   7. Discovery of Network Properties with All-Shortest-Paths Queries

      • Davide Bilò, Thomas Erlebach, Matúš Mihalák, Peter Widmayer

      Pages 89-103

   8. Recovering the Long-Range Links in Augmented Graphs

      • Pierre Fraigniaud, Emmanuelle Lebhar, Zvi Lotker

      Pages 104-118

   9. Computing Frequent Elements Using Gossip

      • Bibudh Lahiri, Srikanta Tirthapura

      Pages 119-130

   10. Maintaining Consistent Transactional States without a Global Clock

       • Hillel Avni, Nir Shavit

       Pages 131-140

   11. Equal-Area Locus-Based Convex Polygon Decomposition

       • David Adjiashvili, David Peleg

       Pages 141-155

   12. On the Power of Local Orientations

       • Monika Steinová

       Pages 156-169

   13. Best Effort and Priority Queuing Policies for Buffered Crossbar Switches

       • Alex Kesselman, Kirill Kogan, Michael Segal

       Pages 170-184

   14. Word of Mouth: Rumor Dissemination in Social Networks

       • Jan Kostka, Yvonne Anne Oswald, Roger Wattenhofer

       Pages 185-196

   15. Non-preemptive Coordination Mechanisms for Identical Machine Scheduling Games

       • Konstantinos Kollias

       Pages 197-208

   16. Computing Approximate Nash Equilibria in Network Congestion Games

       • Andreas Emil Feldmann, Heiko Röglin, Berthold Vöcking

       Pages 209-220

   17. On the Performance of Beauquier and Debas’ Self-stabilizing Algorithm for Mutual Exclusion

       • Viacheslav Chernoy, Mordechai Shalom, Shmuel Zaks

       Pages 221-233

The Colloquium on Structure, Information, Communication, and Complexity (SIROCCO) is an annual research meeting focused on the relationship between information and e?ciency in decentralized (distributed, parallel, and network) computing.Thisyear,SIROCCOcelebratedits15thanniversary.Overtheyears, the colloquium has become a widely recognized forum bringing together - searchers interested in the fundamental principles underlying the interplay - tween local structural knowledge and global communication and computation complexity. SIROCCO covers topics such as distributed algorithms, compact data structures, information dissemination, informative labeling schemes, c- binatorial optimization, and others, with potential applications to large-scale distributed systems including global computing platforms, peer-to-peer systems andapplications,socialnetworks,wirelessnetworks,andnetworkprotocols(such as routing, broadcasting, localization). SIROCCO 2008 was held in Villars-sur- Ollon, in the Swiss Alps, June 17–20, 2008. There were 52 contributions submitted to SIROCCO 2008. All papers - derwent a thorough refereeing process, where each submission was reviewed by at least 3, and on average 3.4, Program Committee members. After in-depth discussions, the Program Committee selected 22 high-quality contributions for presentation at the colloquium and publication in this volume. We thank the authors of all the submitted papers, the Program Committee members, and the external reviewers. Without their dedication, we could not have prepared a program of such quality. ThereweretwoinvitedspeakersatSIROCCO2008:NicolaSantoro(Carleton University) and Boaz Patt-Shamir (Tel-Aviv University). We express our gratitude to the SIROCCO Steering Committee, and in p-ticulartoPierreFraigniaudforhisenthusiasmandhisinvaluablehelpthroughout the preparation of this event.

• Broadcast
• Peer
• Roadcasting
• algorithm
• algorithms
• combinatorial optimization
• complexity
• data structure
• data structures
• distributed systems
• optimization
• routing
• algorithm analysis and problem complexity

Policies and ethics