IBM Research


Microsoft Research - Inria Joint Centre

Oracle Labs

University of the Basque Country

PODC 2015 Proceedings

SESSION: Keynote Lecture

Cortical Computation

  • Christos H. Papadimitriou
  • Santosh S. Vempala

SESSION: Session 1

  • Friedhelm Meyer auf der Heide

Near-Optimal Scheduling of Distributed Algorithms

  • Mohsen Ghaffari

Scheduling Loop-free Network Updates: It’s Good to Relax!

  • Arne Ludwig
  • Jan Marcinkowski
  • Stefan Schmid

New Routing Techniques and their Applications

  • Liam Roditty
  • Roei Tov

Brief Announcement: Routing the Internet with Very Few Entries

  • Cyril Gavoille
  • Christian Glacet
  • Nicolas Hanusse
  • David Ilcinkas

SESSION: Session 2

  • Paul G. Spirakis

Terminating Distributed Construction of Shapes and Patterns in a Fair Solution of Automata

  • Othon Michail

Fast and Exact Majority in Population Protocols

  • Dan Alistarh
  • Rati Gelashvili
  • Milan Vojnović

Distributed House-Hunting in Ant Colonies

  • Mohsen Ghaffari
  • Cameron Musco
  • Tsvetomira Radeva
  • Nancy Lynch

Brief Announcement: On the Feasibility of Leader Election and Shape Formation with Self-Organizing Programmable Matter

  • Zahra Derakhshandeh
  • Robert Gmyr
  • Thim Strothmann
  • Rida Bazzi
  • Andrea Richa
  • Christian Scheideler

SESSION: Session 3

  • Antonio Fernández Anta

Construction and Impromptu Repair of an MST in a Distributed Network with o(m) Communication

  • Valerie King
  • Shay Kutten
  • Mikkel Thorup

Near-Optimal Distributed Maximum Flow: Extended Abstract

  • Mohsen Ghaffari
  • Andreas Karrenbauer
  • Fabian Kuhn
  • Christoph Lenzen
  • Boaz Patt-Shamir

Toward Optimal Bounds in the Congested Clique: Graph Connectivity and MST

  • James W. Hegeman
  • Gopal Pandurangan
  • Sriram V. Pemmaraju
  • Vivek B. Sardeshmukh
  • Michele Scquizzato

Fast Distributed Almost Stable Matchings

  • Rafail Ostrovsky
  • Will Rosenbaum

SESSION: Session 4

  • Christian Scheideler

A (Truly) Local Broadcast Layer for Unreliable Radio Networks

  • Nancy Lynch
  • Calvin Newport

Efficient Communication in Cognitive Radio Networks

  • Seth Gilbert
  • Fabian Kuhn
  • Calvin Newport
  • Chaodong Zheng

A Local Broadcast Layer for the SINR Network Model

  • Magnus M. Halldórsson
  • Stephan Holzer
  • Nancy Lynch

Brief Announcement: Fast and Simple Node Coloring in the SINR Model

  • Fabian Fuchs

SESSION: Session 5

  • Thomas Erlebach

Algebraic Methods in the Congested Clique

  • Keren Censor-Hillel
  • Petteri Kaski
  • Janne H. Korhonen
  • Christoph Lenzen
  • Ami Paz
  • Jukka Suomela

Fast Partial Distance Estimation and Applications

  • Christoph Lenzen
  • Boaz Patt-Shamir

Brief Announcement: Distributed Single-Source Reachability

  • Mohsen Ghaffari
  • Rajan Udwani

Brief Announcement: A Hierarchy of Congested Clique Models, from Broadcast to Unicast

  • Florent Becker
  • Antonio Fernandez Anta
  • Ivan Rapaport
  • Eric Reémila

SESSION: Keynote Lecture

The “Mobile Adversary” Paradigm in Distributed Computation and Systems

  • Moti Yung

SESSION: Session 6

  • Nitin Vaidya

Trading Fences with RMRs and Separating Memory Models

  • Hagit Attiya
  • Danny Hendler
  • Philipp Woelfel

The Price of being Adaptive

  • Ohad Ben-Baruch
  • Danny Hendler

On the Time and Space Complexity of ABA Prevention and Detection

  • Zahra Aghazadeh
  • Philipp Woelfel

Brief Announcement: Fault-tolerant Broadcast in Anonymous Distributed Systems with Fair Lossy Communication Channels

  • Jian Tang
  • Mikel Larrea
  • Sergio Arévalo
  • Ernesto Jiménez

SESSION: Session 7

  • Eric Ruppert

Impossibility Results for Distributed Transactional Memory

  • Costas Busch
  • Maurice Herlihy
  • Miroslav Popovic
  • Gokarna Sharma

Disjoint-Access Parallelism: Impossibility, Possibility, and Cost of Transactional Memory Implementations

  • Sebastiano Peluso
  • Roberto Palmieri
  • Paolo Romano
  • Binoy Ravindran
  • Francesco Quaglia

Safety-Liveness Exclusion in Distributed Computing

  • Victor Bushkov
  • Rachid Guerraoui

Brief Announcement: Eventually Consistent Linearizability

  • Maciej Kokociński
  • Tadeusz Kobus
  • Paweł T. Wojciechowski

SESSION: Session 8

  • Alexander A. Shvartsman


  • Keren Censor-Hillel
  • Erez Petrank
  • Shahar Timnat

Lock-Free Algorithms under Stochastic Schedulers

  • Dan Alistarh
  • Thomas Sauerwald
  • Milan Vojnović

Reclaiming Memory for Lock-Free Data Structures: There has to be a Better Way

  • Trevor Alexander Brown

On the Space Complexity of Set Agreement?

  • Carole Delporte-Gallet
  • Hugues Fauconnier
  • Petr Kuznetsov
  • Eric Ruppert

SESSION: Session 9

  • Moti Yung

How Fair is Your Protocol?: A Utility-based Approach to Protocol Optimality

  • Juan Garay
  • Jonathan Katz
  • Björn Tackmann
  • Vassilis Zikas

Adaptively Secure Computation with Partial Erasures

  • Carmit Hazay
  • Yehuda Lindell
  • Arpita Patra

Improved Analysis of Deterministic Load-Balancing Schemes

  • Petra Berenbrink
  • Ralf Klasing
  • Adrian Kosowski
  • Frederik Mallmann-Trenn
  • Przemyslaw Uznanski

Brief Announcement: Robust and Private Distributed Shared Atomic Memory in Message Passing Networks

  • Shlomi Dolev
  • Thomas Petig
  • Elad Michael Schiller

SESSION: Session 10

  • Othon Michail

Randomized Proof-Labeling Schemes

  • Mor Baruch
  • Pierre Fraigniaud
  • Boaz Patt-Shamir

Distributed Convex Thresholding

  • Ran Wolff

Brief Announcement: Average Complexity for the LOCAL Model

  • Laurent Feuilloley

Brief Announcement: Investigating the Cost of Anonymity on Dynamic Networks

  • Giuseppe Antonio Di Luna
  • Roberto Baldoni

SESSION: Keynote Lecture

Online Resource Leasing

  • Christine Markarian
  • Friedhelm Meyer auf der Heide

SESSION: Session 11

  • Elad M. Schiller

Deterministic (Δ + 1)-Coloring in Sublinear (in Δ) Time in Static, Dynamic and Faulty Networks

  • Leonid Barenboim

On Information Complexity in the Broadcast Model

  • Mark Braverman
  • Rotem Oshman

How To Elect a Leader Faster than a Tournament

  • Dan Alistarh
  • Rati Gelashvili
  • Adrian Vladu

SESSION: Session 12

  • Michel Raynal

The Weakest Failure Detector for Eventual Consistency

  • Swan Dubois
  • Rachid Guerraoui
  • Petr Kuznetsov
  • Franck Petit
  • Pierre Sens

Limitations of Highly-Available Eventually-Consistent Data Stores

  • Hagit Attiya
  • Faith Ellen
  • Adam Morrison

Computing Weak Consistency in Polynomial Time: [Extended Abstract]

  • Wojciech Golab
  • Xiaozhou (Steve) Li
  • Alejandro López-Ortiz
  • Naomi Nishimura

SESSION: Session 13

  • Shlomi Dolev

On the Push&Pull Protocol for Rumour Spreading: [Extended Abstract]

  • Huseyin Acan
  • Andrea Collevecchio
  • Abbas Mehrabian
  • Nick Wormald

Distributed Resource Discovery in Sub-Logarithmic Time

  • Bernhard Haeupler
  • Dahlia Malkhi

The Cost of Synchronizing Multiple-Access Channels

  • Tomasz Jurdzinski
  • Grzegorz Stachowiak

Leveraging Multiple Channels in Ad Hoc Networks

  • Magnus M. Halldorsson
  • Yuexuan Wang
  • Dongxiao Yu

SESSION: Session 14

  • Danny Hendler

Towards Optimal Synchronous Counting

  • Christoph Lenzen
  • Joel Rybicki
  • Jukka Suomela

Fault-Tolerant Consensus in Directed Graphs

  • Lewis Tseng
  • Nitin H. Vaidya

Minimal Synchrony for Byzantine Consensus

  • Zohir Bouzid
  • Achour Mostfaoui
  • Michel Raynal

Stabilizing Server-Based Storage in Byzantine Asynchronous Message-Passing Systems: Extended abstract

  • Silvia Bonomi
  • Shlomi Dolev
  • Maria Potop-Butucaru
  • Michel Raynal

Dual Failure Resilient BFS Structure

  • Merav Parter