ACM Principles of Distributed Computing, PODC 2015


Title/Authors Title Research Artifacts
[?] A research artifact is any by-product of a research project that is not directly included in the published research paper. In Computer Science research this is often source code and data sets, but it could also be media, documentation, inputs to proof assistants, shell-scripts to run experiments, etc.
Details

Brief Announcement: Distributed Single-Source Reachability

Mohsen Ghaffari, Rajan Udwani

Brief Announcement: Distributed Single-Source Reachability

Details
Discussion Comments: 0
Verification: Authors have not verified information

How To Elect a Leader Faster than a Tournament

Dan Alistarh, Rati Gelashvili, Adrian Vladu

How To Elect a Leader Faster than a Tournament

Details
Discussion Comments: 0
Verification: Authors have not verified information

Fast and Exact Majority in Population Protocols

Dan Alistarh, Rati Gelashvili, Milan Vojnovic

Fast and Exact Majority in Population Protocols

Details
Discussion Comments: 0
Verification: Authors have not verified information

Cortical Computation

Christos H. Papadimitriou, Santosh Srinivas Vempala

Cortical Computation

Details
Discussion Comments: 0
Verification: Authors have not verified information

Distributed House-Hunting in Ant Colonies

Mohsen Ghaffari, Cameron Musco, Tsvetomira Radeva, Nancy A. Lynch

Distributed House-Hunting in Ant Colonies

Details
Discussion Comments: 0
Verification: Authors have not verified information

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

Othon Michail

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

Details
Discussion Comments: 0
Verification: Author has not verified information

Randomized Proof-Labeling Schemes

Mor Baruch, Pierre Fraigniaud, Boaz Patt-Shamir

Randomized Proof-Labeling Schemes

Details
Discussion Comments: 0
Verification: Authors have not verified information

Impossibility Results for Distributed Transactional Memory

Costas Busch, Maurice Herlihy, Miroslav Popovic, Gokarna Sharma

Impossibility Results for Distributed Transactional Memory

Details
Discussion Comments: 0
Verification: Authors have not verified information

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

Shlomi Dolev, Thomas Petig, Elad Michael Schiller

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

Details
Discussion Comments: 0
Verification: Authors have not verified information

Adaptively Secure Computation with Partial Erasures

Carmit Hazay, Yehuda Lindell, Arpita Patra

Adaptively Secure Computation with Partial Erasures

Details
Discussion Comments: 0
Verification: Authors have not verified information

Dual Failure Resilient BFS Structure

Merav Parter

Dual Failure Resilient BFS Structure

Details
Discussion Comments: 0
Verification: Author has not verified information

Safety-Liveness Exclusion in Distributed Computing

Victor Bushkov, Rachid Guerraoui

Safety-Liveness Exclusion in Distributed Computing

Details
Discussion Comments: 0
Verification: Authors have not verified information

A Local Broadcast Layer for the SINR Network Model

Magnús M. Halldórsson, Stephan Holzer, Nancy A. Lynch

A Local Broadcast Layer for the SINR Network Model

Details
Discussion Comments: 0
Verification: Authors have not verified information

Brief Announcement: Routing the Internet with Very Few Entries

Cyril Gavoille, Christian Glacet, Nicolas Hanusse, David Ilcinkas

Brief Announcement: Routing the Internet with Very Few Entries

Details
Discussion Comments: 0
Verification: Authors have not verified information

The Price of being Adaptive

Ohad Ben-Baruch, Danny Hendler

The Price of being Adaptive

Details
Discussion Comments: 0
Verification: Authors have not verified information

The Cost of Synchronizing Multiple-Access Channels

Tomasz Jurdzinski, Grzegorz Stachowiak

The Cost of Synchronizing Multiple-Access Channels

Details
Discussion Comments: 0
Verification: Authors have not verified information

Lock-Free Algorithms under Stochastic Schedulers

Dan Alistarh, Thomas Sauerwald, Milan Vojnovic

Lock-Free Algorithms under Stochastic Schedulers

Details
Discussion Comments: 0
Verification: Authors have not verified information

Brief Announcement: Average Complexity for the LOCAL Model

Laurent Feuilloley

Brief Announcement: Average Complexity for the LOCAL Model

Details
Discussion Comments: 0
Verification: Author has not verified information

Efficient Communication in Cognitive Radio Networks

Seth Gilbert, Fabian Kuhn, Calvin Newport, Chaodong Zheng

Efficient Communication in Cognitive Radio Networks

Details
Discussion Comments: 0
Verification: Authors have not verified information

Fast Distributed Almost Stable Matchings

Rafail Ostrovsky, Will Rosenbaum

Fast Distributed Almost Stable Matchings

Details
Discussion Comments: 0
Verification: Authors have not verified information

Brief Announcement: Eventually Consistent Linearizability

Maciej Kokocinski, Tadeusz Kobus, Pawel T. Wojciechowski

Brief Announcement: Eventually Consistent Linearizability

Details
Discussion Comments: 0
Verification: Authors have not verified information

On the Time and Space Complexity of ABA Prevention and Detection

Zahra Aghazadeh, Philipp Woelfel

On the Time and Space Complexity of ABA Prevention and Detection

Details
Discussion Comments: 0
Verification: Authors have not verified information

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

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

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

Details
Discussion Comments: 0
Verification: Authors have not verified information

On the Space Complexity of Set Agreement?

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

On the Space Complexity of Set Agreement?

Details
Discussion Comments: 0
Verification: Authors have not verified information

Fault-Tolerant Consensus in Directed Graphs

Lewis Tseng, Nitin H. Vaidya

Fault-Tolerant Consensus in Directed Graphs

Details
Discussion Comments: 0
Verification: Authors have not verified information

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

Florent Becker, Antonio Fernández Anta, Ivan Rapaport, Eric Rémila

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

Details
Discussion Comments: 0
Verification: Authors have not verified information

Leveraging Multiple Channels in Ad Hoc Networks

Magnús M. Halldórsson, Yuexuan Wang, Dongxiao Yu

Leveraging Multiple Channels in Ad Hoc Networks

Details
Discussion Comments: 0
Verification: Authors have not verified information

Near-Optimal Scheduling of Distributed Algorithms

Mohsen Ghaffari

Near-Optimal Scheduling of Distributed Algorithms

Details
Discussion Comments: 0
Verification: Author has not verified information

The Weakest Failure Detector for Eventual Consistency

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

The Weakest Failure Detector for Eventual Consistency

Details
Discussion Comments: 0
Verification: Authors have not verified information

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

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

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

Details
Discussion Comments: 0
Verification: Authors have not verified information

Trading Fences with RMRs and Separating Memory Models

Hagit Attiya, Danny Hendler, Philipp Woelfel

Trading Fences with RMRs and Separating Memory Models

Details
Author Comments:
Discussion Comments: 0
Sharing: Research produced no artifacts
Verification: Authors have verified information

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

Fabian Fuchs

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

Details
Discussion Comments: 0
Verification: Author has not verified information

A (Truly) Local Broadcast Layer for Unreliable Radio Networks

Nancy A. Lynch, Calvin Newport

A (Truly) Local Broadcast Layer for Unreliable Radio Networks

Details
Discussion Comments: 0
Verification: Authors have not verified information

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

Juan A. Garay, Jonathan Katz, Björn Tackmann, Vassilis Zikas

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

Details
Discussion Comments: 0
Verification: Authors have not verified information

New Routing Techniques and their Applications

Liam Roditty, Roei Tov

New Routing Techniques and their Applications

Details
Discussion Comments: 0
Verification: Authors have not verified information

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

Arne Ludwig, Jan Marcinkowski, Stefan Schmid

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

Details
Discussion Comments: 0
Verification: Authors have not verified information

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

Zahra Derakhshandeh, Robert Gmyr, Thim Strothmann, Rida A. Bazzi, Andréa W. Richa, Christian Scheideler

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

Details
Discussion Comments: 0
Verification: Authors have not verified information

Brief Announcement: Investigating the Cost of Anonymity on Dynamic Networks

Giuseppe Antonio Di Luna, Roberto Baldoni

Brief Announcement: Investigating the Cost of Anonymity on Dynamic Networks

Details
Author Comments:
Discussion Comments: 0
Sharing: Research produced no artifacts
Verification: Authors have verified information

Near-Optimal Distributed Maximum Flow: Extended Abstract

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

Near-Optimal Distributed Maximum Flow: Extended Abstract

Details
Discussion Comments: 0
Verification: Authors have not verified information

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

Trevor Alexander Brown

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

Details
Discussion Comments: 0
Verification: Author has not verified information

Improved Analysis of Deterministic Load-Balancing Schemes

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

Improved Analysis of Deterministic Load-Balancing Schemes

Details
Discussion Comments: 0
Verification: Authors have not verified information

Towards Optimal Synchronous Counting

Christoph Lenzen, Joel Rybicki, Jukka Suomela

Towards Optimal Synchronous Counting

Details
Discussion Comments: 0
Verification: Authors have not verified information

Minimal Synchrony for Byzantine Consensus

Zohir Bouzid, Achour Mostéfaoui, Michel Raynal

Minimal Synchrony for Byzantine Consensus

Details
Author Comments:
Discussion Comments: 0
Sharing: Research produced no artifacts
Verification: Authors have verified information

Algebraic Methods in the Congested Clique

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

Algebraic Methods in the Congested Clique

Details
Discussion Comments: 0
Verification: Authors have not verified information

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

Hüseyin Acan, Andrea Collevecchio, Abbas Mehrabian, Nick Wormald

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

Details
Discussion Comments: 0
Verification: Authors have not verified information

Limitations of Highly-Available Eventually-Consistent Data Stores

Hagit Attiya, Faith Ellen, Adam Morrison

Limitations of Highly-Available Eventually-Consistent Data Stores

Details
Author Comments:
Discussion Comments: 0
Sharing: Research produced no artifacts
Verification: Authors have verified information

Fast Partial Distance Estimation and Applications

Christoph Lenzen, Boaz Patt-Shamir

Fast Partial Distance Estimation and Applications

Details
Discussion Comments: 0
Verification: Authors have not verified information

Distributed Convex Thresholding

Ran Wolff

Distributed Convex Thresholding

Details
Discussion Comments: 0
Verification: Author has not verified information

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

Leonid Barenboim

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

Details
Discussion Comments: 0
Verification: Author has not verified information

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

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

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

Details
Discussion Comments: 0
Verification: Authors have not verified information

Computing Weak Consistency in Polynomial Time: [Extended Abstract]

Wojciech M. Golab, Xiaozhou (Steve) Li, Alejandro López-Ortiz, Naomi Nishimura

Computing Weak Consistency in Polynomial Time: [Extended Abstract]

Details
Discussion Comments: 0
Verification: Authors have not verified information

Distributed Resource Discovery in Sub-Logarithmic Time

Bernhard Haeupler, Dahlia Malkhi

Distributed Resource Discovery in Sub-Logarithmic Time

Details
Discussion Comments: 0
Verification: Authors have not verified information

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

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

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

Details
Discussion Comments: 0
Verification: Authors have not verified information

On Information Complexity in the Broadcast Model

Mark Braverman, Rotem Oshman

On Information Complexity in the Broadcast Model

Details
Discussion Comments: 0
Verification: Authors have not verified information

Online Resource Leasing

Christine Markarian, Friedhelm Meyer auf der Heide

Online Resource Leasing

Details
Discussion Comments: 0
Verification: Authors have not verified information

Help!

Keren Censor-Hillel, Erez Petrank, Shahar Timnat

Help!

Details
Discussion Comments: 0
Verification: Authors have not verified information

The "Mobile Adversary" Paradigm in Distributed Computation and Systems

Moti Yung

The "Mobile Adversary" Paradigm in Distributed Computation and Systems

Details
Discussion Comments: 0
Verification: Author has not verified information

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

Valerie King, Shay Kutten, Mikkel Thorup

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

Details
Discussion Comments: 0
Verification: Authors have not verified information