Stabilization, safety, and security of distributed systems : 11th international symposium, SSS 2009, Lyon, France, November 3-6, 2009 : proceedings

Table of Contents Invited Talks Challenges in Personalizing and Decentralizing the Web: An Overview of GOSSPLE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 Anne-Marie Kermarrec Local Algorithms: Self-stabilization on Speed . . . . . . . . . . . . . . . . . . . . . . . . 17 Christoph Lenzen, Jukka Suomela, and Roger Wattenhofer As Good as It Gets: Competitive Fault Tolerance in Network Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 David Peleg Regular Papers Multicore Constraint-Based Automated Stabilization . . . . . . . . . . . . . . . . . 47 Fuad Abujarad and Sandeep S. Kulkarni A Theory of Network Tracing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 Hrishikesh B. Acharya and Mohamed G. Gouda Developing Autonomic and Secure Virtual Organisations with Chemical Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 Alvaro E. Arenas, Jean-Pierre Banˆatre, and Thierry Priol Making Population Protocols Self-stabilizing . . . . . . . . . . . . . . . . . . . . . . . . 90 Joffroy Beauquier, Janna Burman, and Shay Kutten Analysis of Wireless Sensor Network Protocols in Dynamic Scenarios . . . 105 Cinzia Bernardeschi, Paolo Masci, and Holger Pfeifer Consensus When All Processes May Be Byzantine for Some Time . . . . . . 120 Martin Biely and Martin Hutle A Superstabilizing log(n)-Approximation Algorithm for Dynamic Steiner Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 L´elia Blin, Maria Gradinariu Potop-Butucaru, and Stephane Rovedakis Looking for the Weakest Failure Detector for k-Set Agreement in Message-Passing Systems: Is Πk the End of the Road? . . . . . . . . . . . . . . . . 149 Fran¸cois Bonnet and Michel Raynal XIV Table of Contents Optimal Byzantine Resilient Convergence in Asynchronous Robot Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165 Zohir Bouzid, Maria Gradinariu Potop-Butucaru, and S´ebastien Tixeuil FoG: Fighting the Achilles’ Heel of Gossip Protocols with Fountain Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180 Mary-Luc Champel, Anne-Marie Kermarrec, and Nicolas Le Scouarnec How to Improve Snap-Stabilizing Point-to-Point Communication Space Complexity? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195 Alain Cournier, Swan Dubois, and Vincent Villain Fault-Containment in Weakly-Stabilizing Systems . . . . . . . . . . . . . . . . . . . . 209 Anurag Dasgupta, Sukumar Ghosh, and Xin Xiao Stability of Distributed Algorithms in the Face of Incessant Faults . . . . . 224 Robert E. Lee DeVille and Sayan Mitra Dependability Engineering of Silent Self-stabilizing Systems . . . . . . . . . . . 238 Abhishek Dhama, Oliver Theel, Pepijn Crouzen, Holger Hermanns, Ralf Wimmer, and Bernd Becker Robustness and Dependability of Self-Organizing Systems - A Safety Engineering Perspective. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254 Giovanna Di Marzo Serugendo Efficient Robust Storage Using Secret Tokens . . . . . . . . . . . . . . . . . . . . . . . . 269 Dan Dobre, Matthias Majuntke, Marco Serafini, and Neeraj Suri An Optimal Self-stabilizing Firing Squad . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284 Danny Dolev, Ezra N. Hoch, and Yoram Moses Anonymous Transactions in Computer Networks (Extended Abstract) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297 Shlomi Dolev and Marina Kopeetsky Nash Equilibria in Stabilizing Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311 Mohamed G. Gouda and Hrishikesh B. Acharya ACCADA: A Framework for Continuous Context-Aware Deployment and Adaptation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325 Ning Gui, Vincenzo De Florio, Hong Sun, and Chris Blondia A Self-stabilizing Approximation Algorithm for Vertex Cover in Anonymous Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 341 Volker Turau and Bernd Hauck Table of Contents XV Separation of Circulating Tokens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354 Kajari Ghosh Dastidar and Ted Herman Visiting Gafni’s Reduction Land: From the BG Simulation to the Extended BG Simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 369 Damien Imbs and Michel Raynal Randomized Gathering of Mobile Robots with Local-Multiplicity Detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 384 Taisuke Izumi, Tomoko Izumi, Sayaka Kamei, and Fukuhito Ooshita Scalable P2P Overlays of Very Small Constant Degree: An Emerging Security Threat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 399 M´ark Jelasity and Vilmos Bilicki CFlood: A Constrained Flooding Protocol for Real-time Data Delivery in Wireless Sensor Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 413 Bo Jiang, Binoy Ravindran, and Hyeonjoong Cho Cached Sensornet Transformation of Non-silent Self-stabilizing Algorithms with Unreliable Links . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 428 Hirotsugu Kakugawa, Yukiko Yamauchi, Sayaka Kamei, and Toshimitsu Masuzawa Analysis of an Intentional Fault Which Is Undetectable by Local Checks under an Unfair Scheduler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 443 Jun Kiniwa and Kensaku Kikuta Exploring Polygonal Environments by Simple Robots with Faulty Combinatorial Vision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 458 Anvesh Komuravelli and Mat´uˇs Mihal´ak Finding Good Partners in Availability-Aware P2P Networks . . . . . . . . . . . 472 Stevens Le Blond, Fabrice Le Fessant, and Erwan Le Merrer Churn-Resilient Replication Strategy for Peer-to-Peer Distributed Hash-Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 485 Sergey Legtchenko, S´ebastien Monnet, Pierre Sens, and Gilles Muller Distributed Power Control with Multiple Agents in a Distributed Base Station Scheme Using Macrodiversity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 500 Philippe Leroux and S´ebastien Roy Redundancy Maintenance and Garbage Collection Strategies in Peer-to-Peer Storage Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 515 Xin Liu and Anwitaman Datta XVI Table of Contents Model Checking Coalition Nash Equilibria in MAD Distributed Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 531 Federico Mari, Igor Melatti, Ivano Salvo, Enrico Tronci, Lorenzo Alvisi, Allen Clement, and Harry Li OpenMP Support for NBTI-Induced Aging Tolerance in MPSoCs . . . . . . 547 Andrea Marongiu, Andrea Acquaviva, and Luca Benini A Self-stabilizing Algorithm for Graph Searching in Trees . . . . . . . . . . . . . 563 Rodica Mihai and Morten Mjelde A Metastability-Free Multi-synchronous Communication Scheme for SoCs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 578 Thomas Polzer, Thomas Handl, and Andreas Steininger From Local Impact Functions to Global Adaptation of Service Compositions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 593 Liliana Rosa, Lu´ıs Rodrigues, Ant´onia Lopes, Matti Hiltunen, and Richard Schlichting A Wireless Security Framework without Shared Secrets . . . . . . . . . . . . . . . 609 Lifeng Sang and Anish Arora Read-Write-Codes: An Erasure Resilient Encoding System for Flexible Reading and Writing in Storage Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . 624 Mario Mense and Christian Schindelhauer Distributed Sleep Scheduling in Wireless Sensor Networks via Fractional Domatic Partitioning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 640 Andr´e Schumacher and Harri Haanp¨a¨a Network-Friendly Gossiping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 655 Sabina Serbu, ´Etienne Rivi`ere, and Pascal Felber Black Hole Search with Tokens in Interconnected Networks . . . . . . . . . . . . 670 Wei Shi Oracle-Based Flocking of Mobile Robots in Crash-Recovery Model . . . . . 683 Samia Souissi, Taisuke Izumi, and Koichi Wada Speculation for Parallelizing Runtime Checks . . . . . . . . . . . . . . . . . . . . . . . . 698 Martin S¨ußkraut, Stefan Weigert, Ute Schiffel, Thomas Knauth, Martin Nowack, Diogo Becker de Brum, and Christof Fetzer Optimistic Fair Exchange Using Trusted Devices . . . . . . . . . . . . . . . . . . . . . 711 Mohammad Torabi Dashti Application Data Consistency Checking for Anomaly Based Intrusion Detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 726 Olivier Sarrouy, Eric Totel, and Bernard Jouga Table of Contents XVII Self Adaptive High Interaction Honeypots Driven by Game Theory . . . . . 741 G´erard Wagener, Radu State, Alexandre Dulaunoy, and Thomas Engel Cooperative Autonomic Management in Dynamic Distributed Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 756 Jing Xu, Ming Zhao, and Jos´e A.B. Fortes Brief Announcements Consistent Fixed Points and Negative Gain. . . . . . . . . . . . . . . . . . . . . . . . . . 771 Hrishikesh B. Acharya, Ehab S. Elmallah, and Mohamed G. Gouda Induced Churn to Face Adversarial Behavior in Peer-to-Peer Systems . . . 773 Emmanuelle Anceaume, Francisco Brasileiro, Romaric Ludinard, Bruno Sericola, and Frederic Tronel Safer Than Safe: On the Initial State of Self-stabilizing Systems . . . . . . . . 775 Sylvie Dela¨et, Shlomi Dolev, and Olivier Peres Unique Permutation Hashing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 777 Shlomi Dolev, Limor Lahiani, and Yinnon Haviv Randomization Adaptive Self-stabilization . . . . . . . . . . . . . . . . . . . . . . . . . . 779 Shlomi Dolev and Nir Tzachar On the Time Complexity of Distributed Topological Self-stabilization . . . 781 Dominik Gall, Riko Jacob, Andrea Richa, Christian Scheideler, Stefan Schmid, and Hanjo T¨aubig An OS Architecture for Device Self-protection . . . . . . . . . . . . . . . . . . . . . . . 783 Ruan He, Marc Lacoste, and Jean Leneutre Towards Secure Cloud Computing. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 785 Christian Henrich, Matthias Huber, Carmen Kempka, J¨orn M¨uller-Quade, and Mario Strefler Robust Self-stabilizing Construction of Bounded Size Weight-Based Clusters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 787 Colette Johnen and Fouzi Mekhaldi A Stabilizing Algorithm for Finding Two Disjoint Paths in Arbitrary Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 789 Mehmet Hakan Karaata and Rachid Hadid Relocation Analysis of Stabilizing MAC Algorithms for Large-Scale Mobile Ad Hoc Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 791 Pierre Leone, Marina Papatriantafilou, and Elad M. Schiller XVIII Table of Contents A Simple and Quiescent Omega Algorithm in the Crash-Recovery Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 793 Cristian Mart´ın and Mikel Larrea How to Overcome the Limits of Bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 795 Olivier Peres The Design and Evaluation of a Distributed Reliable File System . . . . . . 797 Dalibor Peric, Thomas Bocek, Fabio Hecht, David Hausheer, and Burkhard Stiller Author Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 799