28. PODC 2009: Calgary, Alberta, Canada

• Robbert van Renesse:
  Refining the way to consensus. 1
  
• Sarita V. Adve:
  Memory models: a case for rethinking parallel languages and hardware. 2
  
• Bruce Hendrickson:
  Emerging challenges and opportunities in parallel computing: the cretaceous redux? 3
  

Invited session on industrial applications of algorithms

• Flavio Paiva Junqueira, Benjamin Reed:
  The life and times of a zookeeper. 4
  
• Avinash Lakshman, Prashant Malik:
  Cassandra: structured storage system on a P2P network. 5
  
• Grzegorz Malewicz, Matthew H. Austern, Aart J. C. Bik, James C. Dehnert, Ilan Horn, Naty Leiser, Grzegorz Czajkowski:
  Pregel: a system for large-scale graph processing. 6
  

R1

• Aleksandar Dragojevic, Rachid Guerraoui, Anmol V. Singh, Vasu Singh:
  Preventing versus curing: avoiding conflicts in transactional memories. 7-16
  
• Marcos Kawazoe Aguilera, Idit Keidar, Dahlia Malkhi, Alexander Shraer:
  Dynamic atomic storage without consensus. 17-25
  
• Danny Hendler, Philipp Woelfel:
  Randomized mutual exclusion in O(log N / log log N) RMRs. 26-35
  
• James Aspnes, Hagit Attiya, Keren Censor:
  Max registers, counters, and monotone circuits. 36-45
  

R2

• Christoph Lenzen, Thomas Locher, Roger Wattenhofer:
  Tight bounds for clock synchronization. 46-55
  
• Robert D. Kleinberg, Georgios Piliouras, Éva Tardos:
  Load balancing without regret in the bulletin board model. 56-62
  
• Heiner Ackermann, Petra Berenbrink, Simon Fischer, Martin Hoefer:
  Concurrent imitation dynamics in congestion games. 63-72
  
• Vibhor Bhatt, Nicholas Christman, Prasad Jayanti:
  Extracting quorum failure detectors. 73-82
  

R3

• Eli Gafni, Petr Kuznetsov:
  The weakest failure detector for solving k-set agreement. 83-91
  
• Arpita Patra, Ashish Choudhary, C. Pandu Rangan:
  Simple and efficient asynchronous byzantine agreement with optimal resilience. 92-101
  
• Marcos Kawazoe Aguilera, Carole Delporte-Gallet, Hugues Fauconnier, Sam Toueg:
  Partial synchrony based on set timeliness. 102-110
  
• Bogdan S. Chlebus, Dariusz R. Kowalski, Michal Strojnowski:
  Fast scalable deterministic consensus for crash failures. 111-120
  

R4

• Thomas P. Hayes, Jared Saia, Amitabh Trehan:
  The forgiving graph: a distributed data structure for low stretch under adversarial attack. 121-130
  
• Riko Jacob, Andréa W. Richa, Christian Scheideler, Stefan Schmid, Hanjo Täubig:
  A distributed polylogarithmic time algorithm for self-stabilizing skip graphs. 131-140
  
• Colin Cooper, Martin E. Dyer, Andrew J. Handley:
  The flip markov chain and a randomising P2P protocol. 141-150
  
• Maxim Gurevich, Idit Keidar:
  Correctness of gossip-based membership under message loss. 151-160
  

R5

• Atish Das Sarma, Danupon Nanongkai, Gopal Pandurangan:
  Fast distributed random walks. 161-170
  
• Christos Koufogiannakis, Neal E. Young:
  Distributed and parallel algorithms for weighted vertex cover and other covering problems. 171-179
  
• Saurav Pandit, Sriram V. Pemmaraju:
  Return of the primal-dual: distributed metric facilitylocation. 180-189
  

R6

• Shlomi Dolev, Seth Gilbert, Rachid Guerraoui, Fabian Kuhn, Calvin C. Newport:
  The wireless synchronization problem. 190-199
  
• Chen Avin, Yuval Emek, Erez Kantor, Zvi Lotker, David Peleg, Liam Roditty:
  SINR diagrams: towards algorithmically usable SINR models of wireless networks. 200-209
  
• Johannes Schneider, Roger Wattenhofer:
  Coloring unstructured wireless multi-hop networks. 210-219
  
• Alexander Fanghänel, Thomas Keßelheim, Harald Räcke, Berthold Vöcking:
  Oblivious interference scheduling. 220-229
  

R7

• Frantisek Galcík, Leszek Gasieniec, Andrzej Lingas:
  Efficient broadcasting in known topology radio networks with long-range interference. 230-239
  
• Pierre Fraigniaud, George Giakkoupis:
  The effect of power-law degrees on the navigability of small worlds: [extended abstract]. 240-249
  
• Prosenjit Bose, Paz Carmi, Stephane Durocher:
  Bounding the locality of distributed routing algorithms. 250-259
  
• Hervé Baumann, Pierluigi Crescenzi, Pierre Fraigniaud:
  Parsimonious flooding in dynamic graphs. 260-269
  

B1-1

• Baruch Awerbuch, Zhenghua Fu, Rohit Khandekar:
  Brief announcement: Stateless distributed algorithms for generalized packing linear programs. 270-271
  
• Eric Koskinen, Maurice Herlihy:
  Brief announcement: concurrent non-commutative boosted transactions. 272-273
  
• R. K. Shyamasundar, Shivali Agarwal:
  Brief announcement: distributed phase synchronization of dynamic set of processes. 274-275
  
• Andreas Dielacher, Matthias Függer, Ulrich Schmid:
  Brief announcement: how to speed-up fault-tolerant clock generation in VLSI systems-on-chip via pipelining. 276-277
  
• Arpita Patra, Ashish Choudhary, C. Pandu Rangan:
  Brief announcement: perfectly secure message transmission in directed networks re-visited. 278-279
  
• Damien Imbs, José Ramón González de Mendívil, Michel Raynal:
  Brief announcement: virtual world consistency: a new condition for STM systems. 280-281
  

B1-2

• Alex Kipnis, Boaz Patt-Shamir:
  Brief announcement: a note on distributed stable matching. 282-283
  
• Pietro Michiardi, Carla-Fabiana Chiasserini, Claudio Casetti, Chi-Anh La, Marco Fiore:
  On a selfish caching game. 284-285
  
• Joffroy Beauquier, Janna Burman, Julien Clement, Shay Kutten:
  Brief announcement: non-self-stabilizing and self-stabilizing gathering in networks of mobile agents--the notion of speed. 286-287
  
• Carole Delporte-Gallet, Hugues Fauconnier, Rachid Guerraoui, Andreas Tielmann:
  The disagreement power of an adversary: extended abstract. 288-289
  
• Antonio Fernández Anta, Sergio Rajsbaum, Corentin Travers:
  Brief announcement: weakest failure detectors via an egg-laying simulation. 290-291
  
• Jinyao Yan, Martin May, Bernhard Plattner:
  Brief announcement: optimization based rate allocation for application layer multicast. 292-293
  

B2-1

• François Bonnet, Michel Raynal:
  Brief announcement: the price of anonymity: optimal consensus despite asynchrony, crash and anonymity. 294-295
  
• Alejandro Cornejo, Nancy A. Lynch:
  Brief announcement: minimum spanning trees and cone-based topology control. 296-297
  
• Jen-Yeu Chen, Gopal Pandurangan, Jianghai Hu:
  Brief announcement: locality-based aggregate computation in wireless sensor networks. 298-299
  
• Martin Dietzfelbinger, Philipp Woelfel:
  Brief announcement: tight lower bounds for greedy routing in uniform small world rings. 300-301
  
• Andrew Berns, Anurag Dasgupta, Sukumar Ghosh:
  Brief announcement: optimal self-stabilizing multi-token ring: a randomized solution. 302-303
  
• Valerie King, Jared Saia:
  Brief announcement: fast scalable Byzantine agreement in the full information model with a nonadaptive adversary. 304-305
  

B2-2

• Noah Paul Evans, Eric Van Hensbergen:
  Brief announcement: PUSH, a DISC shell. 306-307
  
• Yoann Dieudonné, Shlomi Dolev, Franck Petit, Michael Segal:
  Brief announcement: deaf, dumb, and chatting robots. 308-309
  
• Prasant Gopal, Anuj Gupta, Pranav K. Vasishta, Piyush Bansal, Kannan Srinathan:
  Brief announcement: global consistency can be easier than point-to-point communication. 310-311
  
• Leslie Lamport, Dahlia Malkhi, Lidong Zhou:
  Vertical paxos and primary-backup replication. 312-313
  
• Pranav K. Vasishta, Prasant Gopal, Anuj Gupta, Piyush Bansal, K. Srinathan:
  Brief announcement: topology knowledge affects probabilistic reliable communication. 314-315
  
• Matthieu Roy, Marc-Olivier Killijian:
  Brief announcement: a platform for experimenting with mobile algorithms in a laboratory. 316-317
  

B3-1

• Hrishikesh B. Acharya, Mohamed G. Gouda:
  Brief announcement: the theory of network tracing. 318-319
  
• Enoch Peserico:
  Brief announcement: (more) efficient pruning of ad-hoc wireless networks. 320-321
  
• Aaron Sterling:
  Brief announcement: self-assembly as graph grammar as distributed system. 322-323
  
• Zvika Brakerski, Boaz Patt-Shamir:
  Distributed discovery of large near-cliques. 324-325
  
• Oscar García Morchon, Tobias Heer, Klaus Wehrle:
  Brief announcement: lightweight key agreement and digital certificates for wireless sensor networks. 326-327
  
• Michael Dinitz:
  Brief announcement: distributed algorithms for approximating wireless network capacity. 328-329
  

B3-2

• Fabian Kuhn, Nancy A. Lynch, Calvin C. Newport:
  Brief announcement: hardness of broadcasting in wireless networks with unreliable communication. 330-331
  
• Yi Gu, Qishi Wu, Anne Benoit, Yves Robert:
  Brief announcement: complexity analysis and algorithm design for pipeline configuration in distributed networks. 332-333
  
• Hirotada Kobayashi, Keiji Matsumoto, Seiichiro Tani:
  Brief announcement: exactly electing a unique leader is not harder than computing symmetric functions on anonymous quantum networks. 334-335
  
• Alptekin Küpçü, Anna Lysyanskaya:
  Brief announcement: impossibility results for optimistic fair exchange with multiple autonomous arbiters. 336-337
  
• John R. Douceur, James W. Mickens, Thomas Moscibroda, Debmalya Panigrahi:
  Brief announcement: collaborative measurement of upload speeds in P2P systems. 338-339
  
• Yuval Emek, Amos Korman:
  Brief announcement: new bounds for the controller problem. 340-341