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 accepted papers

Printable list of accepted papers (pdf)

Regular papers

  • Jonathan Katz, Aggelos Kiayias, Hong-Sheng Zhou and Vassilis Zikas. Distributing the Setup in Universally Composable Secure Multiparty Computation
  • Tomasz Jurdzinski, Dariusz Kowalski, Michal Rozanski and Grzegorz Stachowiak. On the Impact of Geometry on Ad Hoc Communication in Wireless Networks
  • Michael Elkin, Hartmut Klauck, Danupon Nanongkai and Gopal Pandurangan. Can Quantum Communication Speed Up Distributed Computation?
  • Joshua Brody, Amit Chakrabarti, Ranganath Kondapally, David Woodruff and Grigory Yaroslavtsev. Beyond Set Disjointness: The Communication Complexity of Finding the Intersection
  • Yujie Liu, Kunlong Zhang and Michael Spear. Dynamic-Sized Nonblocking Hash Tables
  • Christoph Lenzen and Boaz Patt-Shamir. Improved Distributed Steiner Forest Construction
  • Zahra Aghazadeh,Wojciech Golab and Philipp Woelfel. Making Objects Writable
  • Michael Backes, Fabian Bendun, Ashish Choudhury and Aniket Kate. Asynchronous MPC with t<n/2 Using Non-equivocation
  • Christoph Lenzen, Nancy Lynch, Calvin Newport and Tsvetomira Radeva. Trade-offs between Selection Complexity and Performance when Searching the Plane without Communication
  • Joshua Baron, Karim El Defrawy, Joshua Lampkins and Rafail Ostrovsky. How to Withstand Mobile Virus Attacks, Revisited
  • Calvin Newport. Consensus with an Abstract MAC Layer
  • Faith Ellen, Panagiota Fatourou, Joanna Helga and Eric Ruppert. The Amortized Complexity of Non-blocking Binary Search Trees
  • Juan Garay, Clint Givens, Rafail Ostrovsky and Pavel Raykov. Fast and Unconditionally Secure Anonymous Channel
  • Benoit Libert, Marc Joye and Moti Yung. Born and Raised Distributively: Fully Distributed Non-Interactive Adaptively-Secure Threshold Signatures with Short Shares
  • Danny Hendler and Vitaly Khait. Complexity Tradeoffs for Read and Update Operations
  • Rachid Guerraoui and Eric Ruppert. A Paradox of Eventual Linearizability in Shared Memory
  • Lewis Tseng and Nitin Vaidya. Asynchronous Convex Consensus in the Presence of Crash Faults
  • Mohsen Ghaffari, Erez Kantor, Calvin Newport and Nancy Lynch. Multi-Message Broadcast with Abstract MAC Layers and Unreliable Links
  • Alex Kogan and Maurice Herlihy. The Future(s) of Shared Data Structures
  • Bapi Chatterjee, Nhan Nguyen and Philippas Tsigas. Efficient Lock-free Binary Search Trees
  • Yehuda Afek, Amir Levy and Adam Morrison. Software-Improved Hardware Lock Elision
  • Maya Arbel and Hagit Attiya. Concurrent Updates with RCU: Search Tree as an Example
  • Marijke Bodlaender and Magnus M. Halldorsson. Beyond Geometry : Towards Fully Realistic Wireless Models
  • Edith Cohen. Estimation for Monotone Sampling: Competitiveness and Customization
  • Achour Mostafaoui, Hamouma Moumen and Michel Raynal. Signature-Free Asynchronous Byzantine Consensus with t < n=3 and O(n2) Messages
  • Keren Censor-Hillel, Mohsen Ghaffari and Fabian Kuhn. Distributed Connectivity Decomposition
  • Bernhard Haeupler and Dahlia Malkhi. Optimal Gossip with Direct Addressing
  • Dan Alistarh, Oksana Denysyuk, Luis Rodrigues and Nir Shavit. Balls-into-Leaves: Sub-logarithmic Renaming in Synchronous Message-Passing Systems
  • Ofer Feinerman, Bernhard Haeupler and Amos Korman. Breath before Speaking: Efficient Information Dissemination despite Noisy, Limited and Anonymous Communication
  • Eli Gafni, Petr Kuznetsov and Ciprian Manolescu. A Generalized Asynchronous Computability Theorem
  • Michael Kapralov and David Woodruff. Spanners and Sparsifiers in Dynamic Streams
  • Mika Goos, Juho Hirvonen and Jukka Suomela. Linear-in-Delta Lower Bounds in the LOCAL Model
  • Avery Miller and Andrzej Pelc. Time Versus Cost Tradeoffs for Deterministic Rendezvous in Networks
  • Andrew Drucker, Fabian Kuhn and Rotem Oshman. On the Power of the Congested Clique Model
  • Yuda Zhao, Haifeng Yu and Binbin Chen. Near-Optimal Communication-Time Tradeoff in Fault-Tolerant Computation of Aggregate Functions
  • Yuval Emek, Christoph Pfister, Jochen Seidel and Roger Wattenhofer. Anonymous Networks: Randomization = 2-Hop Coloring
  • Yehuda Afek, Yehonatan Ginzberg, Shir Landau Feibish and Moshe Sulamy. Distributed Computing Building-Blocks for Rational Agents
  • Kai-Min Chung, Seth Pettie and Hsin-Hao Su. Distributed Algorithms for the Lovasz Local Lemma and Graph Coloring
  • Othon Michail and Paul Spirakis. Simple and Efficient Local Codes for Distributed Stable Network Construction

Brief announcements

  • Dan Alistarh, Keren Censor-Hillel and Nir Shavit. Brief Announcement: Are Lock-Free Concurrent Algorithms Practically Wait-Free?
  • Miikka Hilke, Christoph Lenzen and Jukka Suomela. Brief Announcement: Local Approximability of Minimum Dominating Set on Planar Graphs
  • Juhana Laurinharju and Jukka Suomela. Brief Announcement: Linial’s Lower Bound Made Easy
  • Mohsen Ghaffari and Bernhard Haeupler. Brief Announcement: Near-Optimal BFS Computation in Radio Networks
  • Matteo Maffei, Giulio Malavolta, Manuel Reinert and Dominique Schroder. Brief Announcement: GORAM: Privacy, Access Control, and Verifiability in Group Outsourced Storage
  • Tushar Bisht, Kishore Kothapalli and Sriram V. Pemmaraju. Brief Announcement: Super-Fast t-Ruling Sets
  • Danupon Nanongkai. Almost-Tight Approximation Distributed Algorithm for Minimum Cut (Brief Announcement)
  • Nir Hemed and Noam Rinetzky. Brief Announcement: Contention-Aware Linearizability
  • Michel Raynal, Julien Stainer and Gadi Taubenfeld. Distributed Universality: Contention-Awareness, Wait-freedom, Object Progress, and Other Properties
  • Manfred Schwarz, Kyrill Winkler, Ulrich Schmid, Martin Biely and Peter Robinson. Gracefully Degrading Consensus and k-Set Agreement under Dynamic Link Failures
  • Messaoud Doudou, Jose M. Barcelo-Ordinas, Djamel Djenouri, Jorge Garcia-Vidal and Nadjib Badache. Game Theoretical Approach for Energy-Delay Balancing in Distributed Duty-Cycled MAC Protocols of Wireless Networks
  • Joseph Izraelevitz and Michael Scott. A Generic Construction for Nonblocking Dual Containers