25. DISC 2011: Rome, Italy

Invited Lecture & Best Student Paper: Rendezvous (Session 1a)

• Andrzej Pelc:
  DISC 2011 Invited Lecture: Deterministic Rendezvous in Networks: Survey of Models and Results. 1-15
  
• Yehuda Afek, Michael Hakimi, Adam Morrison:
  Fast and Scalable Rendezvousing. 16-31
  

Distributed Graph Algorithms (Session 1b)

• Yehuda Afek, Noga Alon, Ziv Bar-Joseph, Alejandro Cornejo, Bernhard Haeupler, Fabian Kuhn:
  Beeping a Maximal Independent Set. 32-50
  
• Johannes Schneider, Roger Wattenhofer:
  Trading Bit, Message, and Time Complexity of Distributed Algorithms. 51-65
  
• Leonid Barenboim, Michael Elkin:
  Combinatorial Algorithms for Distributed Graph Coloring. 66-81
  
• Taisuke Izumi, Maria Gradinariu Potop-Butucaru, Mathieu Valero:
  Physical Expander in Virtual Tree Overlay. 82-96
  

Shared Memory (Session 1c)

• Dan Alistarh, James Aspnes:
  Sub-logarithmic Test-and-Set against a Weak Adversary. 97-109
  
• Gadi Taubenfeld:
  Tight Space Bounds for ℓ-Exclusion. 110-124
  
• Dmitri Perelman, Anton Byshevsky, Oleg Litmanovich, Idit Keidar:
  SMV: Selective Multi-Versioning STM. 125-140
  

Brief Announcements I (Session 1d)

• Leslie Lamport:
  Brief Announcement: Leaderless Byzantine Paxos. 141-142
  
• Keith Marzullo, Hein Meling, Alessandro Mei:
  Brief Announcement: When You Don't Trust Clients: Byzantine Proposer Fast Paxos. 143-144
  
• Carole Delporte-Gallet, Hugues Fauconnier, Eli Gafni, Petr Kuznetsov:
  Brief Announcement: On the Meaning of Solving a Task with a Failure Detector. 145-146
  
• Evgenia Christoforou, Antonio Fernández Anta, Chryssis Georgiou, Miguel A. Mosteiro:
  Brief Announcement: Algorithmic Mechanisms for Internet-Based Computing under Unreliable Communication. 147-149
  

Fault-Tolerance and Security (Session 1e)

• Swan Dubois, Toshimitsu Masuzawa, Sébastien Tixeuil:
  Maximum Metric Spanning Tree Made Byzantine Tolerant. 150-164
  
• Chryssis Georgiou, Dariusz R. Kowalski:
  Performing Dynamically Injected Tasks on Processes Prone to Crashes and Restarts. 165-180
  
• Elette Boyle, Shafi Goldwasser, Yael Tauman Kalai:
  Leakage-Resilient Coin Tossing. 181-196
  

Brief Announcements II (Session 1f)

• Shay Kutten, Ron Lavi, Amitabh Trehan:
  Brief Announcement: Composition Games for Distributed Systems: The EU Grants Games. 197-199
  
• Andrzej Czygrinow, Michal Hanckowiak, Krzysztof Krzywdzinski, Edyta Szymanska, Wojciech Wawrzyniak:
  Brief Announcement: Distributed Approximations for the Semi-matching Problem. 200-201
  
• Martin Farach-Colton, Antonio Fernández Anta, Alessia Milani, Miguel A. Mosteiro, Shmuel Zaks:
  Brief Announcement: Opportunistic Information Dissemination in Mobile Ad-Hoc Networks: - Adaptiveness vs. Obliviousness and Randomization vs. Determinism. 202-204
  
• Siddhartha Sen, Sunghwan Ihm, Kay Ousterhout, Michael J. Freedman:
  Brief Announcement: Bridging the Theory-Practice Gap in Multi-commodity Flow Routing. 205-207
  

Invited Lecture: Paxos Plus (Session 2a)

• Mahesh Balakrishnan, Dahlia Malkhi, Vijayan Prabhakaran, Ted Wobber:
  DISC 2011 Invited Lecture by Dahlia Malkhi: Going beyond Paxos. 208-210
  
• Leslie Lamport:
  Byzantizing Paxos by Refinement. 211-224
  

Wireless (Session 2b)

• Antonio Fernández Anta, Miguel A. Mosteiro, Jorge Ramón Muñoz:
  Unbounded Contention Resolution in Multiple-Access Channels. 225-236
  
• Leonid Barenboim, Shlomi Dolev, Rafail Ostrovsky:
  Deterministic and Energy-Optimal Wireless Synchronization. 237-251
  
• Shlomi Dolev, Seth Gilbert, Majid Khabbazian, Calvin C. Newport:
  Leveraging Channel Diversity to Gain Efficiency and Robustness for Wireless Broadcast. 252-267
  
• Mohsen Ghaffari, Nancy A. Lynch, Srikanth Sastry:
  Leader Election Using Loneliness Detection. 268-282
  

Network algorithms I (Session 2c)

• Srikanta Tirthapura, David P. Woodruff:
  Optimal Random Sampling from Distributed Streams Revisited. 283-297
  
• Andrea E. F. Clementi, Riccardo Silvestri:
  Parsimonious Flooding in Geometric Random-Walks - (Extended Abstract). 298-310
  
• Yvonne Anne Pignolet, Stefan Schmid, Gilles Trédan:
  Misleading Stars: What Cannot Be Measured in the Internet? 311-325
  

Brief Announcements III (Session 2d)

• Meg Walraed-Sullivan, Radhika Niranjan Mysore, Keith Marzullo, Amin Vahdat:
  Brief Announcement: A Randomized Algorithm for Label Assignment in Dynamic Networks. 326-327
  
• Mikel Larrea, Michel Raynal:
  Brief Announcement: ΔΩ: Specifying an Eventual Leader Service for Dynamic Systems. 328-329
  
• Taisuke Izumi, Zohir Bouzid, Sébastien Tixeuil, Koichi Wada:
  Brief Announcement: The BG-Simulation for Byzantine Mobile Robots. 330-331
  

Invited Lecture & Best Paper: Aspects of Locality (Session 3a)

• Peter Widmayer:
  DISC 2011 Invited Lecture: Polygon Reconstruction with Little Information: An Example for the Power of Simple Micro-robots. 332
  
• Pierre Fraigniaud, Sergio Rajsbaum, Corentin Travers:
  Locality and Checkability in Wait-Free Computing. 333-347
  

Consensus (Session 3b)

• Allison B. Lewko:
  The Contest between Simplicity and Efficiency in Asynchronous Byzantine Agreement. 348-362
  
• James Aspnes:
  Randomized Consensus in Expected O(n 2) Total Work Using Single-Writer Registers. 363-373
  
• Hagit Attiya, Fatemeh Borran, Martin Hutle, Zarko Milosevic, André Schiper:
  Structured Derivation of Semi-Synchronous Algorithms. 374-388
  
• Piyush Bansal, Prasant Gopal, Anuj Gupta, Kannan Srinathan, Pranav K. Vasishta:
  Byzantine Agreement Using Partial Authentication. 389-403
  

Network algorithms II (Session 3c)

• Ittai Abraham, Cyril Gavoille:
  On Approximate Distance Labels and Routing Schemes with Affine Stretch. 404-415
  
• Fabian Kuhn, Rotem Oshman:
  The Complexity of Data Aggregation in Directed Networks. 416-431
  
• Jérémie Chalopin, Shantanu Das, Arnaud Labourel, Euripides Markou:
  Black Hole Search with Finite Automata Scattered in a Synchronous Torus. 432-446
  
• Andrew Collins, Jurek Czyzowicz, Leszek Gasieniec, Adrian Kosowski, Russell A. Martin:
  Synchronous Rendezvous for Location-Aware Agents. 447-459
  

Concurrency (Session 3d)

• Li Lu, Michael L. Scott:
  Toward a Formal Semantic Framework for Deterministic Parallel Programming. 460-474
  
• Dmitry Basin, Rui Fan, Idit Keidar, Ofer Kiselov, Dmitri Perelman:
  CAFÉ: Scalable Task Pools with Adjustable Fairness and Contention. 475-488
  
• Yehuda Afek, Yakov Babichenko, Uriel Feige, Eli Gafni, Nati Linial, Benny Sudakov:
  Oblivious Collaboration. 489-504
  

Last update Fri May 25 08:48:13 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page