Microsoft Research
Oracle Labs

PODC 2013 Proceedings

SESSION: Keynote addresses

Plenary talk

  • Michael Merritt

Athena lecture: distributed computing theory for wireless networks and mobile systems

  • Nancy A. Lynch

Programming models for extreme-scale computing

  • Marc Snir

SESSION: Concurrent data structures and objects

  • Michel Raynal

On deterministic abortable objects

  • Vassos Hadzilacos
  • Sam Toueg

Pragmatic primitives for non-blocking data structures

  • Trevor Brown
  • Faith Ellen
  • Eric Ruppert

The SkipTrie: low-depth concurrent search without rebalancing

  • Rotem Oshman
  • Nir Shavit

SESSION: Routing and distributed algorithms

  • James Aspnes

Compact routing schemes with improved stretch

  • Shiri Chechik

Optimal deterministic routing and sorting on the congested clique

  • Christoph Lenzen

Brief announcement: fair maximal independent sets in trees

  • Jeremy Fineman
  • Calvin Newport
  • Tonghe Wang

Brief announcement: threshold load balancing in networks

  • Martin Hoefer
  • Thomas Sauerwald

SESSION: Byzantine agreement

  • Keren Censor-Hillel

Fast byzantine agreement

  • Nicolas Braud-Santoni
  • Rachid Guerraoui
  • Florian Huc

Byzantine vector consensus in complete graphs

  • Nitin H. Vaidya
  • Vijay K. Garg

Fast byzantine agreement in dynamic networks

  • John Augustine
  • Gopal Pandurangan
  • Peter Robinson

Synchronous byzantine agreement with nearly a cubic number of communication bits

  • Dariusz R. Kowalski
  • Achour Mostéfaoui

SESSION: Distributed algorithms and their complexity

  • Philipp Woelfel

How to meet asynchronously at polynomial cost

  • Yoann Dieudonné
  • Andrzej Pelc
  • Vincent Villain

On the complexity of universal leader election

  • Shay Kutten
  • Gopal Pandurangan
  • David Peleg
  • Peter Robinson
  • Amitabh Trehan

Brief announcement: a simple stretch 2 distance oracle

  • Rachit Agarwal
  • Philip Brighten Godfrey

Brief announcement: pareto optimal solutions to consensus and set consensus

  • Armando Castañeda
  • Yannai A. Gonczarowski
  • Yoram Moses

SESSION: Brief announcements

  • Phillip Gibbons

Brief announcement: self-stabilizing resource discovery algorithm

  • Seda Davtyan
  • Kishori M. Konwar
  • Alexander A. Shvartsman

Brief announcement: parameterized model checking of fault-tolerant distributed algorithms by abstraction

  • Annu John
  • Igor Konnov
  • Ulrich Schmid
  • Helmut Veith
  • Josef Widder

Brief announcement: on minimum interaction time for continuous distributed interactive computing

  • Lu Zhang
  • Xueyan Tang
  • Bingsheng He

Brief announcement: deterministic self-stabilizing leader election with O(log log n)-bits

  • Lélia Blin
  • Sébastien Tixeuil

Brief announcement: scalable anonymous communication with byzantine adversary

  • Josh Karlin
  • Joud Khoury
  • Jared Saia
  • Mahdi Zamani

Brief announcement: brokerage and closure in a strategic model of social capital

  • Samuel D. Johnson
  • Raissa M. D’Souza

Brief announcement: techniques for programmatically troubleshooting distributed systems

  • Sam Whitlock
  • Colin Scott
  • Scott Shenker

SESSION: Distributed algorithms and their complexity

  • Fabian Kuhn

Stone age distributed computing

  • Yuval Emek
  • Roger Wattenhofer

Feedback from nature: an optimal distributed algorithm for maximal independent set selection

  • Alex Scott
  • Peter Jeavons
  • Lei Xu

What can be decided locally without identifiers?

  • Pierre Fraigniaud
  • Mika Göös
  • Amos Korman
  • Jukka Suomela

SESSION: Fault tolerance in distributed systems

  • Chryssis Georgiou

Synchrony weakened by message adversaries vs asynchrony restricted by failure detectors

  • Michel Raynal
  • Julien Stainer

Highly dynamic distributed computing with byzantine failures

  • Rachid Guerraoui
  • Florian Huc
  • Anne-Marie Kermarrec

Brief announcement: constructing fault-tolerant overlay networks for topic-based publish/subscribe

  • Chen Chen
  • Roman Vitenberg
  • Hans-Arno Jacobsen

Brief announcement: byzantine agreement with a strong adversary in polynomial expected time

  • Valerie King
  • Jared Saia

SESSION: Renaming and mutual exclusion

  • Eric Ruppert

Upper bound on the complexity of solving hard renaming

  • Hagit Attiya
  • Armando Castañeda
  • Maurice Herlihy
  • Ami Paz

Randomized loose renaming in o(log log n) time

  • Dan Alistarh
  • James Aspnes
  • George Giakkoupis
  • Philipp Woelfel

Byzantine renaming in synchronous systems with t < N

  • Oksana Denysyuk
  • Luís Rodrigues

An O(1)-barriers optimal RMRs mutual exclusion algorithm: extended abstract

  • Hagit Attiya
  • Danny Hendler
  • Smadar Levy

SESSION: Social and peer to peer networks and mobile robots

  • Darek Kowalski

Fair and resilient incentive tree mechanisms

  • Yuezhou Lv
  • Thomas Moscibroda

What’s a little collusion between friends?

  • Edmund L. Wong
  • Lorenzo Alvisi

A distributed algorithm for gathering many fat mobile robots in the plane

  • Chrysovalandis Agathangelou
  • Chryssis Georgiou
  • Marios Mavronicolas

Stable and scalable universal swarms

  • Ji Zhu
  • Stratis Ioannidis
  • Nidhi Hegde
  • Laurent Massoulie

SESSION: Byzantine agreement and self-stabilization

  • Danny Hendler

Early-deciding consensus is expensive

  • Danny Dolev
  • Christoph Lenzen

On the complexity of asynchronous agreement against powerful adversaries

  • Allison Lewko
  • Mark Lewko

Introducing speculation in self-stabilization: an application to mutual exclusion

  • Swan Dubois
  • Rachid Guerraoui

SESSION: Shared and transactional memory

  • Panagiota Fatourou

Leaplist: lessons learned in designing tm-supported range queries

  • Hillel Avni
  • Nir Shavit
  • Adi Suissa

A programming language perspective on transactional memory consistency

  • Hagit Attiya
  • Alexey Gotsman
  • Sandeep Hans
  • Noam Rinetzky

Brief announcement: an asymmetric flat-combining based queue algorithm

  • Michael Gorelik
  • Danny Hendler

Brief announcement: resettable objects and efficient memory reclamation for concurrent algorithms

  • Zahra Aghazadeh
  • Wojciech Golab
  • Philipp Woelfel

SESSION: Radio and wireless networks

  • Luis Rodrigues

Randomized broadcast in radio networks with collision detection

  • Mohsen Ghaffari
  • Bernhard Haeupler
  • Majid Khabbazian

Maximal independent sets in multichannel radio networks

  • Sebastian Daum
  • Mohsen Ghaffari
  • Seth Gilbert
  • Fabian Kuhn
  • Calvin Newport

The cost of radio network broadcast for different models of unreliable links

  • Mohsen Ghaffari
  • Nancy Lynch
  • Calvin Newport

Connectivity and aggregation in multihop wireless networks

  • Marijke H.L. Bodlaender
  • Magnús M. Halldórsson
  • Pradipta Mitra

SESSION: Sensor network, graph algorithms and system security

  • Seth Gilbert

The multi-agent rotor-router on the ring: a deterministic alternative to parallel random walks

  • Ralf Klasing
  • Adrian Kosowski
  • Dominik Pająk
  • Thomas Sauerwald

Efficient distributed source detection with limited bandwidth

  • Christoph Lenzen
  • David Peleg

Distributed algorithms for barrier coverage using relocatable sensors

  • Mohsen Eftekhari
  • Evangelos Kranakis
  • Danny Krizanc
  • Oscar Morales-Ponce
  • Lata Narayanan
  • Jaroslav Opatrny
  • Sunil Shende

Delegation of computation with verification outsourcing: curious verifiers

  • Gang Xu
  • George Amariucai
  • Yong Guan

Brief announcement: a shorter and stronger proof of an Ω(d log(n/d)) lower bound for broadcast in radio networks

  • Calvin Newport

Brief announcement: a local approximation algorithm for MDS problem in anonymous planar networks

  • Wojciech Wawrzyniak