27. PODC 2008: Toronto, Canada

• Joseph Y. Halpern:
  Beyond nash equilibrium: solution concepts for the 21st century. 1-10
  
• Donald F. Towsley:
  The internet is flat: a brief history of networking in the next ten years. 11-12
  
• Peter Druschel:
  Accountability for distributed systems. 13-14
  

R1

• Fabian Kuhn, Thomas Locher, Stefan Schmid:
  Distributed computation of the mode. 15-24
  
• Leonid Barenboim, Michael Elkin:
  Sublogarithmic distributed MIS algorithm for sparse graphs using nash-williams decomposition. 25-34
  
• Johannes Schneider, Roger Wattenhofer:
  A log-star distributed maximal independent set algorithm for growth-bounded graphs. 35-44
  
• Baruch Awerbuch, Andréa W. Richa, Christian Scheideler:
  A jamming-resistant MAC protocol for single-hop wireless networks. 45-54
  

R2

• Piotr Zielinski:
  Anti-Omega: the weakest failure detector for set agreement. 55-64
  
• Yehuda Afek, Israel Nir:
  Failure detectors in loosely named systems. 65-74
  
• Prasad Jayanti, Sam Toueg:
  Every problem has a weakest failure detector. 75-84
  
• Carole Delporte-Gallet, Hugues Fauconnier, Rachid Guerraoui:
  Sharing is harder than agreeing. 85-94
  

R3

• Alex X. Liu, Fei Chen:
  Collaborative enforcement of firewall policies in virtual private networks. 95-104
  
• Shlomi Dolev, Seth Gilbert, Rachid Guerraoui, Calvin C. Newport:
  Secure communication over radio channels. 105-114
  
• B. V. Ashwinkumar, Arpita Patra, Ashish Choudhary, Kannan Srinathan, C. Pandu Rangan:
  On tradeoff between network connectivity, phase complexity and communication complexity of reliable communication tolerating mixed adversary. 115-124
  
• Shlomi Dolev, Danny Hendler, Adi Suissa:
  CAR-STM: scheduling-based collision avoidance and resolution for software transactional memory. 125-134
  

R4

• Chryssis Georgiou, Seth Gilbert, Rachid Guerraoui, Dariusz R. Kowalski:
  On the complexity of asynchronous gossip. 135-144
  
• Edward Bortnikov, Maxim Gurevich, Idit Keidar, Gabriel Kliot, Alexander Shraer:
  Brahms: byzantine resilient random membership sampling. 145-154
  
• Petra Berenbrink, Robert Elsässer, Tom Friedetzky:
  Efficient randomised broadcasting in random regular networks with applications in peer-to-peer systems. 155-164
  
• Nikolaos Laoutaris, Laura J. Poplawski, Rajmohan Rajaraman, Ravi Sundaram, Shang-Hua Teng:
  Bounded budget connection (BBC) games or how to make friends and influence people, on a budget. 165-174
  

R5

• Xiaojie Gao, Leonard J. Schulman:
  On a capacitated multivehicle routing problem. 175-184
  
• Amos Korman:
  Improved compact routing schemes for dynamic trees. 185-194
  
• Yvonne Anne Oswald, Stefan Schmid, Roger Wattenhofer:
  Tight bounds for delay-sensitive aggregation. 195-202
  
• Tom Hayes, Navin Rustagi, Jared Saia, Amitabh Trehan:
  The forgiving tree: a self-healing distributed data structure. 203-212
  

R6

• Andrea E. F. Clementi, Claudio Macci, Angelo Monti, Francesco Pasquale, Riccardo Silvestri:
  Flooding time in edge-Markovian dynamic graphs. 213-222
  
• Yuval Emek, Erez Kantor, David Peleg:
  On the effect of the deployment setting on broadcasting in Euclidean radio networks. 223-232
  
• Gregory Chockler, Seth Gilbert, Nancy A. Lynch:
  Virtual infrastructure for collision-prone wireless networks. 233-242
  
• Valerie King, Cynthia Phillips, Jared Saia, Maxwell Young:
  Sleeping on the job: energy-efficient and robust broadcast for radio networks. 243-252
  

R7

• Seth Pettie:
  Distributed algorithms for ultrasparse spanners and linear size skeletons. 253-262
  
• Maleq Khan, Fabian Kuhn, Dahlia Malkhi, Gopal Pandurangan, Kunal Talwar:
  Efficient distributed approximation algorithms via probabilistic tree embeddings. 263-272
  
• Bilel Derbel, Cyril Gavoille, David Peleg, Laurent Viennot:
  On the locality of distributed sparse spanner construction. 273-282
  
• Lei Guo, Enhua Tan, Songqing Chen, Zhen Xiao, Xiaodong Zhang:
  The stretched exponential distribution of internet media access patterns. 283-294
  

R8

• Armando Castañeda, Sergio Rajsbaum:
  New combinatorial topology upper and lower bounds for renaming. 295-304
  
• Marcos Kawazoe Aguilera, Sam Toueg:
  Timeliness-based wait-freedom: a gracefully degrading progress condition. 305-314
  
• Hagit Attiya, Keren Censor:
  Lower bounds for randomized consensus under a weak adversary. 315-324
  
• James Aspnes, Hagit Attiya, Keren Censor:
  Randomized consensus in expected O(n log n) individual work. 325-334
  

R9

• Alexander Kesselman, Kirill Kogan, Michael Segal:
  Packet mode and QoS algorithms for buffered crossbar switches with FIFO queuing. 335-344
  
• Marios Mavronicolas, Thomas Sauerwald:
  The impact of randomization in smoothing networks. 345-354
  
• Ming Zhong, Pin Lu, Kai Shen, Joel I. Seiferas:
  Optimizing data popularity conscious bloom filters. 355-364
  
• Thomas Moscibroda, Onur Mutlu:
  Distributed order scheduling and its application to multi-core dram controllers. 365-374
  

R10

• Bogdan S. Chlebus, Dariusz R. Kowalski:
  Asynchronous exclusive selection. 375-384
  
• Michael Ben-Or, Danny Dolev, Ezra N. Hoch:
  Fast self-stabilizing byzantine tolerant digital clock synchronization. 385-394
  
• Danny Dolev, Ezra N. Hoch:
  OCD: obsessive consensus disorder (or repetitive consensus). 395-404
  
• Ittai Abraham, Danny Dolev, Joseph Y. Halpern:
  An almost-surely terminating polynomial protocol forasynchronous byzantine agreement with optimal resilience. 405-414
  

B1-1

• Augustin Chaintreau, Pierre Fraigniaud, Emmanuelle Lebhar:
  Forget him and keep on moving. 415
  
• Michael Dinitz:
  Online and dynamic embeddings of approximate ultrametrics. 416
  
• Goran Konjevod, Andréa W. Richa, Donglin Xia:
  Dynamic routing and location services in metrics of low doubling dimension. 417
  
• Mark Braverman:
  On ad hoc routing with guaranteed delivery. 418
  
• Bruno D. Abrahao, Robert D. Kleinberg:
  On the internet delay space dimensionality. 419
  
• Roman Vitenberg, Ricardo Jiménez-Peris:
  Maximizing quorum availability in multi-clustered systems. 420
  

B1-2

• Chafika Benzaid, Nadjib Badache:
  BMobi_Causal: a causal broadcast protocol in mobile dynamic groups. 421
  
• José Enrique Armendáriz-Iñigo, José Ramón Juárez-Rodríguez, José Ramón González de Mendívil, Francesc D. Muñoz-Escoí:
  Correctness criteria for replicated database systems with snapshot isolation replicas. 422
  
• Peter Robinson, Ulrich Schmid:
  The asynchronous bounded-cycle model. 423
  
• John W. O'Leary, Bratin Saha, Mark R. Tuttle:
  Model checking transactional memory with spin. 424
  
• Chryssis Georgiou, Nicolas C. Nicolaou, Alexander A. Shvartsman:
  On the robustness of (semi) fast quorum-based implementations of atomic shared memory. 425
  
• Christian Cachin, Idit Keidar, Alexander Shraer:
  Principles of untrusted storage: a new look at consistency conditions. 426
  

B2-1

• Vincent Gramoli, Ymir Vigfusson, Ken Birman, Anne-Marie Kermarrec, Robbert van Renesse:
  A fast distributed slicing algorithm. 427
  
• László Toka, Pietro Michiardi:
  A dynamic exchange game. 428
  
• Michael Backes, Marek Hamerlik, Alessandro Linari, Matteo Maffei, Christos Tryfonopoulos, Gerhard Weikum:
  Anonymous and censorship resistant content sharing in unstructured overlays. 429
  
• Alex Brodsky:
  Our brothers' keepers. 430
  
• Vincent Gramoli, Anne-Marie Kermarrec, Erwan Le Merrer:
  Distributed churn measurement in arbitrary networks. 431
  
• Yi Gu, Qishi Wu, Mengxia Zhu, Nageswara S. V. Rao:
  Efficient pipeline configuration in distributed heterogeneous computing environments. 432
  

B2-2

• Song Guo, Minyi Guo, Victor C. M. Leung:
  A tradeoff analysis on message complexity and lifetime optimality for a distributed multicast algorithm in WSNs. 433
  
• Amitabha Bagchi, Sohit Bansal:
  Nearest-neighbor graphs on random point sets and their applications to sensor networks. 434
  
• Anne-Marie Kermarrec, Achour Mostéfaoui, Michel Raynal, Gilles Trédan, Aline Carneiro Viana:
  From anarchy to geometric structuring: the power of virtual coordinates. 435
  
• Haibo Zhang, Hong Shen, Yawen Chen, Zonghua Zhang:
  Balancing energy consumption for uniform data gathering wireless sensor networks. 436
  
• Andreas Klappenecker, Hyunyoung Lee, Jennifer L. Welch:
  Scheduling sensors by tilinglattices. 437
  
• Ajay Gulati:
  Power management of devices: when should i switch off? 438
  

B3-1

• Baruch Awerbuch, Rohit Khandekar:
  Greedy distributed optimization of unsplittable multicommodity flows. 439
  
• Baruch Awerbuch, Rohit Khandekar:
  Stateless distributed algorithms for near optimal maximum multicommodity flows. 440
  
• Hariharan Narayanan:
  Distributed averaging in the presence of a sparse cut. 441
  
• Roberto Di Pietro, Pietro Michiardi:
  Gossip-based aggregate computation: computing faster with non address-oblivious schemes. 442
  
• Sylvie Delaët, Stéphane Devismes, Mikhail Nesterenko, Sébastien Tixeuil:
  Snap-stabilization in message-passing systems. 443
  
• Edward Bortnikov, Israel Cidon, Idit Keidar:
  Dynamic service assignment in mobile networks: the magma approach. 444
  

BA3-2

• Louis K. Helm:
  Quantum distributed consensus. 445
  
• François Bonnet, Michel Raynal:
  Looking for the optimal conditions for solving set agreement. 446
  
• Hagit Attiya, Danny Hendler, Philipp Woelfel:
  Tight RMR lower bounds for mutual exclusion and other problems. 447
  
• Robert Danek, Wojciech M. Golab:
  Closing the complexity gap between mutual exclusion and FCFS mutual exclusion. 448
  
• Colette Johnen, Lisa Higham:
  Fault-tolerant implementations of atomic registers by safe registers in networks. 449
  
• Alberto Lafuente, Mikel Larrea, Iratxe Soraluze Arriola, Roberto Cortiñas:
  Optimal failure detection with low sporadic overhead and communication locality. 450
  

B4-1

• Justin Emile Gottschlich, Daniel A. Connors:
  Optimizing consistency checking for memory-intensive transactions. 451
  
• Phuong Hoai Ha, Philippas Tsigas, Otto J. Anshus:
  Wait-free programming for general purpose computations on graphics processors. 452
  
• Michael F. Spear, Andrew Sveikauskas, Michael L. Scott:
  Transactional memory retry mechanisms. 453
  
• Ioannis Chatzigiannakis, Georgios Giannoulis, Paul G. Spirakis:
  Scheduling tasks with dependencies on asymmetric multiprocessors. 454
  

B4-2

• Ian A. Kash, Eric J. Friedman, Joseph Y. Halpern:
  The lotus-eater attack. 455
  
• David James, Tim Leonard, John W. O'Leary, Murali Talupur, Mark R. Tuttle:
  Extracting models from design documents with mapster. 456
  
• Kannan Srinathan, Ashish Choudhary, Arpita Patra, C. Pandu Rangan:
  Efficient single phase unconditionally secure message transmission with optimum communication complexity. 457
  
• David A. Schultz, Barbara Liskov, Moses Liskov:
  Mobile proactive secret sharing. 458
  

Nancy Lynch celebration

• Michael J. Fischer:
  Evolution of distributed computing theory: from concurrency to networks and beyond. 460
  
• Hagit Attiya, Jennifer L. Welch:
  A world of (Im) possibilities. 461
  
• Roberto Segala:
  The power of simulation relations. 462
  
• Seth Gilbert:
  On fault tolerance and wireless networks. 463
  
• Maurice Herlihy:
  The future of distributed computing: renaissance or reformation? 464