Structural Information and Communication Complexity

15th International Colloquium, SIROCCO 2008, Villars-sur-Ollon, Switzerland, June 17-20, 2008, Proceedings
2008
ISBN: 978-3-540-69326-0
Verlag: Springer Berlin Heidelberg

Buch, Englisch, Band 5058, 310 Seiten, Format (B × H): 155 mm x 235 mm, Gewicht: 487 g

Reihe: Lecture Notes in Computer Science

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.

Zielgruppe

Research

Autoren/Hrsg.

Felber, Pascal

Fachgebiete

• Mathematik | Informatik EDV | Informatik Technische Informatik Netzwerk-Hardware
• Mathematik | Informatik Mathematik Numerik und Wissenschaftliches Rechnen Numerische Mathematik
• Mathematik | Informatik EDV | Informatik Technische Informatik Externe Speicher & Peripheriegeräte
• Mathematik | Informatik EDV | Informatik Computerkommunikation & -vernetzung
• Mathematik | Informatik EDV | Informatik Informatik Logik, formale Sprachen, Automaten
• Mathematik | Informatik EDV | Informatik Programmierung | Softwareentwicklung Programmierung: Methoden und Allgemeines
• Mathematik | Informatik EDV | Informatik Daten / Datenbanken Zeichen- und Zahlendarstellungen

Inhaltsverzeichnis

Invited Talks.- Mobile Entities Computing: Models and Problems.- Reputation, Trust and Recommendation Systems in Peer-to-Peer Systems.- Regular Papers.- Gathering Problem of Two Asynchronous Mobile Robots with Semi-dynamic Compasses.- Locating and Repairing Faults in a Network with Mobile Agents.- Remembering without Memory: Tree Exploration by Asynchronous Oblivious Robots.- Average Binary Long-Lived Consensus: Quantifying the Stabilizing Role Played by Memory.- Distributed Approximation Algorithm for Resource Clustering.- Sharpness: A Tight Condition for Scalability.- Discovery of Network Properties with All-Shortest-Paths Queries.- Recovering the Long-Range Links in Augmented Graphs.- Computing Frequent Elements Using Gossip.- Maintaining Consistent Transactional States without a Global Clock.- Equal-Area Locus-Based Convex Polygon Decomposition.- On the Power of Local Orientations.- Best Effort and Priority Queuing Policies for Buffered Crossbar Switches.- Word of Mouth: Rumor Dissemination in Social Networks.- Non-preemptive Coordination Mechanisms for Identical Machine Scheduling Games.- Computing Approximate Nash Equilibria in Network Congestion Games.- On the Performance of Beauquier and Debas’ Self-stabilizing Algorithm for Mutual Exclusion.- Self-stabilizing Cuts in Synchronous Networks.- Quiescence of Self-stabilizing Gossiping among Mobile Agents in Graphs.- Gathering with Minimum Delay in Tree Sensor Networks.- Centralized Communication in Radio Networks with Strong Interference.- Fast Radio Broadcasting with Advice.