Structural Information and Communication Complexity

1. Front Matter

   PDF

2. Dynamic Networks Algorithms

   1. Distributed Community Detection in Dynamic Graphs

      • Andrea Clementi, Miriam Di Ianni, Giorgio Gambosi, Emanuele Natale, Riccardo Silvestri

      Pages 1-12

   2. Exploration of the T-Interval-Connected Dynamic Graphs: The Case of the Ring

      • David Ilcinkas, Ahmed Mouhamadou Wade

      Pages 13-23

   3. A Characterization of Dynamic Networks Where Consensus Is Solvable

      • Étienne Coulouma, Emmanuel Godard

      Pages 24-35

3. Algorithms 1

   1. Self-adjusting Grid Networks to Minimize Expected Path Length

      • Chen Avin, Michael Borokhovich, Bernhard Haeupler, Zvi Lotker

      Pages 36-54

   2. On Advice Complexity of the k-server Problem under Sparse Metrics

      • Sushmita Gupta, Shahin Kamali, Alejandro López-Ortiz

      Pages 55-67

   3. Connected Surveillance Game

      • Frédéric Giroire, Dorian Mazauric, Nicolas Nisse, Stéphane Pérennes, Ronan Soares

      Pages 68-79

4. Online Algorithms

   1. Non-Additive Two-Option Ski Rental

      • Amir Levi, Boaz Patt-Shamir

      Pages 80-91

   2. Competitive FIB Aggregation for Independent Prefixes: Online Ski Rental on the Trie

      • Marcin Bienkowski, Stefan Schmid

      Pages 92-103

   3. A Nonmonotone Analysis with the Primal-Dual Approach: Online Routing of Virtual Circuits with Unknown Durations

      • Guy Even, Moti Medina

      Pages 104-115

5. Social Networks Systems

   1. Self-organizing Flows in Social Networks

      • Nidhi Hegde, Laurent Massoulié, Laurent Viennot

      Pages 116-128

   2. Performance/Security Tradeoffs for Content-Based Routing Supported by Bloom Filters

      • Hugues Mercier, Emanuel Onica, Etienne Rivière, Pascal Felber

      Pages 129-140

   3. Influence Diffusion in Social Networks under Time Window Constraints

      • Luisa Gargano, Pavol Hell, Joseph Peters, Ugo Vaccaro

      Pages 141-152

6. Distributed Algorithms

   1. Analysis of Fully Distributed Splitting and Naming Probabilistic Procedures and Applications

      • Yves Métivier, John Michael Robson, Akka Zemmari

      Pages 153-164

   2. A Deterministic Worst-Case Message Complexity Optimal Solution for Resource Discovery

      • Sebastian Kniesburges, Andreas Koutsopoulos, Christian Scheideler

      Pages 165-176

   3. Maintaining Balanced Trees for Structured Distributed Streaming Systems

      • Frédéric Giroire, Remigiusz Modrzejewski, Nicolas Nisse, Stéphane Pérennes

      Pages 177-188

7. Robots

   1. Rendezvous of Two Robots with Constant Memory

      • Paola Flocchini, Nicola Santoro, Giovanni Viglietta, Masafumi Yamashita

      Pages 189-200

   2. Pattern Formation by Mobile Robots with Limited Visibility

      • Yukiko Yamauchi, Masafumi Yamashita

      Pages 201-212

   3. Optimal Gathering of Oblivious Robots in Anonymous Graphs

      • Gabriele Di Stefano, Alfredo Navarra

      Pages 213-224

8. Wireless Networks

   1. Probabilistic Connectivity Threshold for Directional Antenna Widths

      • Hadassa Daltrophe, Shlomi Dolev, Zvi Lotker

      Pages 225-236

This book constitutes the thoroughly refereed post-conference proceedings of the 20th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2013, held in Ischia, Italy, in July 2013. The 28 revised full papers presented were carefully reviewed and selected from 67 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.

• asynchronous system
• distributed algorithms
• graph algorithm
• self-organization
• wireless networks
• algorithm analysis and problem complexity
• data structures

• System Algorithms Research Group, Microsoft Research Asia, Beijing, China

  Thomas Moscibroda

• Dipartimento di Informatica, Università di Salerno, Fisciano, Italy

  Adele A. Rescigno

Policies and ethics