Ben-Gurion University of the Negev




Laboratoire d'Informatic de Paris 6

Laboratoire de Recherche en Informatique

Laboratory of Information, Networking, and Communication Science

Mairie de Paris

Microsoft Research

Oracle Labs


Telecom ParisTech

University Pierre and Marie Curie

PODC 2014 Proceedings

SESSION: Keynote lecture

Rational and resilient protocols

  • Silvio Micali

SESSION: Session 1

  • Jennifer Welch

Signature-free asynchronous byzantine consensus with t < n/3 and o(n2) messages

  • Achour Mostefaoui
  • Hamouma Moumen
  • Michel Raynal

Asynchronous MPC with a strict honest majority using non-equivocation

  • Michael Backes
  • Fabian Bendun
  • Ashish Choudhury
  • Aniket Kate

Distributing the setup in universally composable multi-party computation

  • Jonathan Katz
  • Aggelos Kiayias
  • Hong-Sheng Zhou
  • Vassilis Zikas

SESSION: Session 2

  • Michel Raynal

The future(s) of shared data structures

  • Alex Kogan
  • Maurice Herlihy

A paradox of eventual linearizability in shared memory

  • Rachid Guerraoui
  • Eric Ruppert

Brief announcement: are lock-free concurrent algorithms practically wait-free?

  • Dan Alistarh
  • Keren Censor-Hillel
  • Nir Shavit

Brief announcement: a generic construction for nonblocking dual containers

  • Joseph Izraelevitz
  • Michael L. Scott

SESSION: Session 3

  • Stefan Schmid

Multi-message broadcast with abstract MAC layers and unreliable links

  • Mohsen Ghaffari
  • Erez Kantor
  • Nancy Lynch
  • Calvin Newport

Consensus with an abstract MAC layer

  • Calvin Newport

Simple and efficient local codes for distributed stable network construction

  • Othon Michail
  • Paul G. Spirakis

Linear-in-delta lower bounds in the LOCAL model

  • Mika Göös
  • Juho Hirvonen
  • Jukka Suomela

SESSION: Session 4

  • Nitin H. Vaidya

Anonymous networks: randomization = 2-hop coloring

  • Yuval Emek
  • Christoph Pfister
  • Jochen Seidel
  • Roger Wattenhofer

Beyond set disjointness: the communication complexity of finding the intersection

  • Joshua Brody
  • Amit Chakrabarti
  • Ranganath Kondapally
  • David P. Woodruff
  • Grigory Yaroslavtsev

Breathe before speaking: efficient information dissemination despite noisy, limited and anonymous communication

  • Ofer Feinerman
  • Bernhard Haeupler
  • Amos Korman

SESSION: Session 5

  • Moti Yung

Estimation for monotone sampling: competitiveness and customization

  • Edith Cohen

Distributed algorithms for the Lovász local lemma and graph coloring

  • Kai-Min Chung
  • Seth Pettie
  • Hsin-Hao Su

Brief announcement: towards security and privacy for outsourced data in the multi-party setting

  • Matteo Maffei
  • Giulio Malavolta
  • Manuel Reinert
  • Dominique Schröder

Brief announcement: game theoretical approach for energy-delay balancing in distributed duty-cycled MAC protocols of wireless networks

  • Messaoud Doudou
  • Jose M. Barcelo
  • Ordinas
  • Djamel Djenouri
  • Jorge Garcia Vidal
  • Nadjib Badache

SESSION: Keynote lecture

Coding theory for scalable media delivery

  • Michael G. Luby

SESSION: Session 6

  • Alexander Schvartsman

Distributed connectivity decomposition

  • Keren Censor-Hillel
  • Mohsen Ghaffari
  • Fabian Kuhn

Can quantum communication speed up distributed computation?

  • Michael Elkin
  • Hartmut Klauck
  • Danupon Nanongkai
  • Gopal Pandurangan

Optimal gossip with direct addressing

  • Bernhard Haeupler
  • Dahlia Malkhi

SESSION: Session 7

  • Panagiota Fatourou

Complexity tradeoffs for read and update operations

  • Danny Hendler
  • Vitaly Khait

Concurrent updates with RCU: search tree as an example

  • Maya Arbel
  • Hagit Attiya

Brief announcement: distributed universality: contention-awareness; wait-freedom; object progress, and other properties

  • Michel Raynal
  • Julien Stainer
  • Gadi Taubenfeld

Brief announcement: concurrency-aware linearizability

  • Nir Hemed
  • Noam Rinetzky

SESSION: Session 8

  • Vassos Hadzilacos

Software-improved hardware lock elision

  • Yehuda Afek
  • Amir Levy
  • Adam Morrison

A generalized asynchronous computability theorem

  • Eli Gafni
  • Petr Kuznetsov
  • Ciprian Manolescu

Balls-into-leaves: sub-logarithmic renaming in synchronous message-passing systems

  • Dan Alistarh
  • Oksana Denysyuk
  • Luís Rodrigues
  • Nir Shavit

Dynamic-sized nonblocking hash tables

  • Yujie Liu
  • Kunlong Zhang
  • Michael Spear

SESSION: Session 9

  • Seth Gilbert

Trade-offs between selection complexity and performance when searching the plane without communication

  • Christoph Lenzen
  • Nancy Lynch
  • Calvin Newport
  • Tsvetomira Radeva

Improved distributed steiner forest construction

  • Christoph Lenzen
  • Boaz Patt-Shamir

Spanners and sparsifiers in dynamic streams

  • Michael Kapralov
  • David Woodruff

Time versus cost tradeoffs for deterministic rendezvous in networks

  • Avery Miller
  • Andrzej Pelc

SESSION: 2013 ACM A.M. turing award lecture

An incomplete history of concurrency chapter 1. 1965–1977

  • Leslie Lamport

SESSION: Keynote lecture

Rigorous system design

  • Joseph Sifakis

SESSION: Session 10

  • Paul Spirakis

How to withstand mobile virus attacks, revisited

  • Joshua Baron
  • Karim El Defrawy
  • Joshua Lampkins
  • Rafail Ostrovsky

Born and raised distributively: fully distributed non-interactive adaptively-secure threshold signatures with short shares

  • Benoît Libert
  • Marc Joye
  • Moti Yung

Fast and unconditionally secure anonymous channel

  • Juan A. Garay
  • Clinton Givens
  • Rafail Ostrovsky
  • Pavel Raykov

SESSION: Session 11

  • Petr Kuznetsov

Efficient lock-free binary search trees

  • Bapi Chatterjee
  • Nhan Nguyen
  • Philippas Tsigas

The amortized complexity of non-blocking binary search trees

  • Faith Ellen
  • Panagiota Fatourou
  • Joanna Helga
  • Eric Ruppert

Brief announcement: gracefully degrading consensus and k-set agreement under dynamic link failures

  • Manfred Schwarz
  • Kyrill Winkler
  • Ulrich Schmid
  • Martin Biely
  • Peter Robinson

Brief announcement: local approximability of minimum dominating set on planar graphs

  • Miikka Hilke
  • Christoph Lenzen
  • Jukka Suomela

SESSION: Session 12

  • Joseph Sifakis

Beyond geometry: towards fully realistic wireless models

  • Marijke H.L. Bodlaender
  • Magnus M. Halldorsson

On the impact of geometry on ad hoc communication in wireless networks

  • Tomasz Jurdzinski
  • Dariusz R. Kowalski
  • Michal Rozanski
  • Grzegorz Stachowiak

On the power of the congested clique model

  • Andrew Drucker
  • Fabian Kuhn
  • Rotem Oshman

Brief announcement: linial’s lower bound made easy

  • Juhana Laurinharju
  • Jukka Suomela

Brief announcement: Super-fast t-ruling sets

  • Tushar Bisht
  • Kishore Kothapalli
  • Sriram Pemmaraju

Brief announcement: almost-tight approximation distributed algorithm for minimum cut

  • Danupon Nanongkai

SESSION: Session 13

  • Luís Rodrigues

Making objects writable

  • Zahra Aghazadeh
  • Wojciech Golab
  • Philipp Woelfel

Asynchronous convex hull consensus in the presence of crash faults

  • Lewis Tseng
  • Nitin H. Vaidya

Distributed computing building blocks for rational agents

  • Yehuda Afek
  • Yehonatan Ginzberg
  • Shir Landau Feibish
  • Moshe Sulamy

Near-optimal communication-time tradeoff in fault-tolerant computation of aggregate functions

  • Yuda Zhao
  • Haifeng Yu
  • Binbin Chen