Nicola Santoro (auth.), Alexander A. Shvartsman, Pascal Felber (eds.)3540693262, 9783540693260
This book constitutes the refereed proceedings of the 15th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2008, held in Villars-sur-Ollon, Switzerland, in June 2008.
The 22 revised full papers presented together with 2 invited talks were carefully reviewed and selected from 52 submissions. The papers cover topics such as distributed algorithms, compact data structures, information dissemination, informative labeling schemes, combinatorial optimization, and others, with potential applications to large scale distributed systems including global computing platforms, peer-to-peer systems and applications, social networks, wireless networks, and network protocols (such as routing, broadcasting, localization).
Table of contents :
Front Matter….Pages –
Mobile Entities Computing: Models and Problems….Pages 1-1
Reputation, Trust and Recommendation Systems in Peer-to-Peer Systems….Pages 2-4
Gathering Problem of Two Asynchronous Mobile Robots with Semi-dynamic Compasses….Pages 5-19
Locating and Repairing Faults in a Network with Mobile Agents….Pages 20-32
Remembering without Memory: Tree Exploration by Asynchronous Oblivious Robots….Pages 33-47
Average Binary Long-Lived Consensus: Quantifying the Stabilizing Role Played by Memory….Pages 48-60
Distributed Approximation Algorithm for Resource Clustering….Pages 61-73
Sharpness: A Tight Condition for Scalability….Pages 74-88
Discovery of Network Properties with All-Shortest-Paths Queries….Pages 89-103
Recovering the Long-Range Links in Augmented Graphs….Pages 104-118
Computing Frequent Elements Using Gossip….Pages 119-130
Maintaining Consistent Transactional States without a Global Clock….Pages 131-140
Equal-Area Locus-Based Convex Polygon Decomposition….Pages 141-155
On the Power of Local Orientations….Pages 156-169
Best Effort and Priority Queuing Policies for Buffered Crossbar Switches….Pages 170-184
Word of Mouth: Rumor Dissemination in Social Networks….Pages 185-196
Non-preemptive Coordination Mechanisms for Identical Machine Scheduling Games….Pages 197-208
Computing Approximate Nash Equilibria in Network Congestion Games….Pages 209-220
On the Performance of Beauquier and Debas’ Self-stabilizing Algorithm for Mutual Exclusion….Pages 221-233
Self-stabilizing Cuts in Synchronous Networks….Pages 234-246
Quiescence of Self-stabilizing Gossiping among Mobile Agents in Graphs….Pages 247-261
Gathering with Minimum Delay in Tree Sensor Networks….Pages 262-276
Centralized Communication in Radio Networks with Strong Interference….Pages 277-290
Fast Radio Broadcasting with Advice….Pages 291-305
Back Matter….Pages –
Reviews
There are no reviews yet.