Full Description
th These are the proceedings of SIROCCO 2009: the 16 annual Colloquium on Structure, Information, Communication, and Complexity. SIROCCO is devoted tothestudyoftheinterplayandtrade-o?sbetweenthee?ciencyofdecentralized algorithms and systems and the availability of information. Over the years,the colloquium has become a widely recognizedforum, bri- ing together researchers interested in the fundamental principles underlying the interplay between local knowledge and global complexity. It has a tradition of interesting and productive scienti?c meetings in a relaxed and pleasant at- sphere, attracting leading researchers in a variety of ?elds which exhibit such interplay. This means that SIROCCO addresses topics in areas such as distributed computing, parallel computing, game theory, social networks, networking, - bile computing, peer to peer systems, communication complexity, combinatorial optimization, etc. Some of the topics in these areasarecompact data structures, informationdissemination,informative labeling schemes,distributed scheduling, wireless networks and scheduling of transmissions, routing, broadcasting, loc- ization, and others.
SIROCCO 2009 was held in Piran, Slovenia, on the Adriatic. There were 53 contributions submitted to SIROCCO 2009.The submissions underwent a th- ough refereeing process, where each submission was reviewed by four members of the Program Committee. After in-depth discussions, the Program Comm- tee selected 23 high-quality contributions for presentationat the colloquium and publicationinthisvolume.Separately,fourposterswerealsopresented(butthey arenotincludedintheseproceedings).Wethanktheauthorsofallthesubmitted papers, the Program Committee members, and the external reviewers. Without their dedication, we could not have prepared a program of such quality. There were two invited speakers: Israel Cidon (the Technion) and Leszek A. Gasieniec (University of Liverpool).
Contents
Invited Talks.- Zooming in on Network-on-Chip Architectures.- On Efficient Gossiping in Radio Networks.- Regular Papers.- Regular Register: An Implementation in a Churn Prone Environment.- Ordered Coloring Grids and Related Graphs.- Sub-linear Universal Spatial Gossip Protocols.- Designing Hypergraph Layouts to GMPLS Routing Strategies.- On Gossip and Populations.- Reconstructing Visibility Graphs with Simple Robots.- Stability of Networks in Stretchable Graphs.- Space Complexity of Self-stabilizing Leader Election in Passively-Mobile Anonymous Agents.- Characterizing Topological Assumptions of Distributed Algorithms in Dynamic Networks.- A New Polynomial Silent Stabilizing Spanning-Tree Construction Algorithm.- Spatial Node Distribution of Manhattan Path Based Random Waypoint Mobility Models with Applications.- More Efficient Periodic Traversal in Anonymous Undirected Graphs.- Black Hole Search in Directed Graphs.- Optimal Probabilistic Ring Exploration by Semi-synchronous Oblivious Robots.- Revisiting Randomized Parallel Load Balancing Algorithms.- An Improved Strategy for Exploring a Grid Polygon.- An Efficient Self-stabilizing Distance-2 Coloring Algorithm.- Distributed Computing of Efficient Routing Schemes in Generalized Chordal Graphs.- A Versatile STM Protocol with Invisible Read Operations That Satisfies the Virtual World Consistency Condition.- On-Line Maximum Matching in Complete Multipartite Graphs with Implications to the Minimum ADM Problem on a Star Topology.- Loosely-Stabilizing Leader Election in Population Protocol Model.- Convergence of Mobile Robots with Uniformly-Inaccurate Sensors.- An Optimal Bit Complexity Randomized Distributed MIS Algorithm (Extended Abstract).
