Principles of Distributed Systems

1. Front Matter

   PDF

2. Robots

   1. Pattern Formation through Optimum Matching by Oblivious CORDA Robots

      • Nao Fujinaga, Hirotaka Ono, Shuji Kijima, Masafumi Yamashita

      Pages 1-15

   2. RoboCast: Asynchronous Communication in Robot Networks

      • Zohir Bouzid, Shlomi Dolev, Maria Potop-Butucaru, Sébastien Tixeuil

      Pages 16-31

3. Randomization in Distributed Algorithms

   1. Biased Selection for Building Small-World Networks

      • Andrés Sevilla, Alberto Mozo, M. Araceli Lorenzo, Jose Luis López-Presa, Pilar Manzano, Antonio Fernández Anta

      Pages 32-47

   2. Application of Random Walks to Decentralized Recommender Systems

      • Anne-Marie Kermarrec, Vincent Leroy, Afshin Moin, Christopher Thraves

      Pages 48-63

   3. Uniform and Ergodic Sampling in Unstructured Peer-to-Peer Systems with Malicious Nodes

      • Emmanuelle Anceaume, Yann Busnel, Sébastien Gambs

      Pages 64-78

4. Brief Announcements I

   1. Self-stabilizing (k,r)-Clustering in Wireless Ad-hoc Networks with Multiple Paths

      • Andreas Larsson, Philippas Tsigas

      Pages 79-82

   2. Self-stabilizing Byzantine Asynchronous Unison,

      • Swan Dubois, Maria Gradinariu Potop-Butucaru, Mikhail Nesterenko, Sébastien Tixeuil

      Pages 83-86

5. Graph Algorithms

   1. Reliably Detecting Connectivity Using Local Graph Traits

      • Alejandro Cornejo, Nancy Lynch

      Pages 87-102

   2. Distributed Game-Theoretic Vertex Coloring

      • Ioannis Chatzigiannakis, Christos Koninis, Panagiota N. Panagopoulou, Paul G. Spirakis

      Pages 103-118

   3. Constructing a Map of an Anonymous Graph: Applications of Universal Sequences

      • Jérémie Chalopin, Shantanu Das, Adrian Kosowski

      Pages 119-134

6. Brief Announcements II

   1. Effect of Fairness in Model Checking of Self-stabilizing Programs

      • Jingshu Chen, Fuad Abujarad, Sandeep Kulkarni

      Pages 135-138

   2. A Formal Framework for Conformance Testing of Distributed Real-Time Systems

      • Moez Krichen

      Pages 139-142

7. Fault-Tolerance

   1. Signature-Free Broadcast-Based Intrusion Tolerance: Never Decide a Byzantine Value

      • Achour Mostéfaoui, Michel Raynal

      Pages 143-158

   2. A Fault Avoidance Strategy Improving the Reliability of the EGI Production Grid Infrastructure

      • Francesco Palmieri, Silvio Pardi, Paolo Veronesi

      Pages 159-172

   3. Failure Detectors Encapsulate Fairness

      • Scott M. Pike, Srikanth Sastry, Jennifer L. Welch

      Pages 173-188

   4. \((\mathrm{anti-}\Omega^{x} \times \Sigma_{z})\)-Based k-Set Agreement Algorithms

      • Zohir Bouzid, Corentin Travers

      Pages 189-204

8. Distributed Programming

   1. Distributed Programming with Tasks

      • Eli Gafni, Sergio Rajsbaum

      Pages 205-218

   2. SkewCCC+: A Heterogeneous Distributed Hash Table

      • Marcin Bienkowski, André Brinkmann, Marek Klonowski, Miroslaw Korzeniowski

      Pages 219-234

   3. On the Automated Implementation of Time-Based Paxos Using the IOA Compiler

      • Chryssis Georgiou, Procopis Hadjiprocopiou, Peter M. Musial

      Pages 235-252

The 14th International Conference on Principles of Distributed Systems (OPODIS 2010) took place during December 14–17, 2010 in Tozeur, Tunisia. It continued a tradition of successful conferences; Chantilly (1997), Amiens (1998), Hanoi (1999), Paris (2000), Mexico (2001), Reims (2002), La Martinique (2003), Gre- ble (2004), Pisa (2005), Bordeaux (2006), Guadeloupe (2007), Luxor (2008) and Nˆ?mes (2009). The OPODIS conference constitutes an open forum for the exchange of sta- of-the-art knowledge on distributed computing and systems among researchers from around the world. Following the tradition of the previous events, the p- gram was composed of high-quality contributed papers. The program call for papers looked for original and signi?cant research contributions to the theory, speci?cation, design and implementation of distributed systems, including: – Communication and synchronization protocols – Distributed algorithms, multiprocessor algorithms – Distributed cooperative computing – Embedded systems – Fault-tolerance, reliability, availability – Grid and cluster computing – Location- and context-aware systems – Mobile agents and autonomous robots – Mobile computing and networks – Peer-to-peer systems, overlay networks – Complexity and lower bounds – Performance analysis of distributed systems – Real-time systems – Security issues in distributed computing and systems – Sensor networks: theory and practice – Speci?cation and veri?cation of distributed systems – Testing and experimentation with distributed systems In response to this call for papers, 122 papers were submitted. Each paper was reviewed by at least three reviewers, and judged according to scienti?c and p- sentation quality, originality and relevance to theconference topics.

• Broadcast
• Partition
• calculus
• complexity
• concurrency
• distributed algorithms
• distributed systems
• fault-tolerance
• graph algorithm
• memory
• programming
• proving
• robot
• shared memory
• wireless sensor networks
• algorithm analysis and problem complexity

• Department of Computer Science and Engineering, Washington University, St. Louis, USA

  Chenyang Lu

• Osaka University, Japan

  Toshimitsu Masuzawa

• LaBRI, University of Bordeaux, Talence, France

  Mohamed Mosbah

Policies and ethics