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