PODC '16- Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing

Full Citation in the ACM Digital Library

SESSION: Keynote Lecture 1

New Opportunities for PODC?: Massive, Volatile, but Highly Predictable Resources

SESSION: Session 1

A Distributed (2+ε)-Approximation for Vertex Cover in O(logδ/ε log log δ) Rounds

The Greedy Spanner is Existentially Optimal

MST in Log-Star Rounds of Congested Clique

Distributed Algorithms for Planar Networks I: Planar Embedding

Brief Announcement: Labeling Schemes for Power-Law Graphs

Brief Announcement: Sublinear-Space Distance Labeling Using Hubs

Brief Announcement: Optimal Leader Election in Multi-Hop Radio Networks

Brief Announcement: The Small World of Curious Beings

SESSION: Session 2

Analysing Snapshot Isolation

Recoverable Mutual Exclusion: [Extended Abstract]

A Randomized Concurrent Algorithm for Disjoint Set Union

Self-stabilizing Balls & Bins in Batches: The Power of Leaky Bins [Extended Abstract]

Brief Announcement: Local Independent Set Approximation

SESSION: Session 3

Deterministic Objects: Life Beyond Consensus

Unbeatable Set Consensus via Topological and Combinatorial Reasoning

A Polylogarithmic Gossip Algorithm for Plurality Consensus

Noisy Rumor Spreading and Plurality Consensus

Rational Consensus: Extended Abstract

Brief Announcement: A Tight Space Bound for Consensus

SESSION: Keynote Lecture 2

Concurrent Data Structures

SESSION: Session 4

Contention Resolution on a Fading Channel

Reliable Communication over Highly Connected Noisy Networks

Contention Resolution on Multiple Channels with Collision Detection

How Asynchrony Affects Rumor Spreading Time

Brief Announcement: An Exponential Separation Between Randomized and Deterministic Complexity in the LOCAL Model

Brief Announcement: Data Dissemination in Unified Dynamic Wireless Networks

Brief Announcement: Reliable Message Transmission under Partial Knowledge and General Adversaries

Brief Announcement: Self-stabilizing Clock Synchronization with 3-bit Messages

SESSION: Session 5

Distributed Strong Diameter Network Decomposition: Extended Abstract

Optimal Dynamic Distributed MIS

A Local Constant Factor MDS Approximation for Bounded Genus Graphs

On Efficient Distributed Construction of Near Optimal Routing Schemes: Extended Abstract

Brief Announcement: Deterministic Graph Connectivity in the Broadcast Congested Clique

SESSION: Session 6

Space Bounds for Reliable Storage: Fundamental Limits of Coding

Specification and Complexity of Collaborative Text Editing

Optimal Mobile Byzantine Fault Tolerant Distributed Storage: Extended Abstract

A Markov Chain Algorithm for Compression in Self-Organizing Particle Systems

A Complexity-Based Hierarchy for Multiprocessor Synchronization: [Extended Abstract]

Brief Announcement: Asynchronous Coordination with Constraints and Preferences

SESSION: Keynote Lecture 3

How Emerging Memory Technologies Will Have You Rethinking Algorithm Design

SESSION: Session 7

Information-Theoretic Lower Bounds on the Storage Cost of Shared Memory Emulation

On the Complexity of Reader-Writer Locks: Extended Abstract

An Algorithm for Replicated Objects with Efficient Reads

Are Shared Objects Composable under an Oblivious Adversary?

Brief Announcement: A Family of Leaderless Generalized-Consensus Algorithms

Brief Announcement: Computing in the Presence of Weak Crash Failures

Brief Announcement: Oh-RAM! One and a Half Round Read/Write Atomic Memory

Brief Announcement: Space-Time Tradeoffs for Distributed Verification

SESSION: Session 8

A Faster Distributed Radio Broadcast Primitive: Extended Abstract

Broadcast Extensions with Optimal Communication and Round Complexity

Two-Bit Messages are Sufficient to Implement Atomic Read/Write Registers in Crash-prone Systems

How Proofs are Prepared at Camelot: Extended Abstract

Brief Announcement: Proactive Secret Sharing with a Dishonest Majority

SESSION: Session 9

Search on a Line with Faulty Robots

Uniform Deployment of Mobile Agents in Asynchronous Rings

Fault-Tolerant Multi-Agent Optimization: Optimal Iterative Distributed Algorithms

Brief Announcement: Active Information Spread in Networks

Brief Announcement: Certified Universal Gathering in R2 for Oblivious Mobile Robots

Brief Announcement: Probabilistic Asynchronous Arbitrary Pattern Formation

Brief Announcement: Pattern Formation Problem for Synchronous Mobile Robots in the Three Dimensional Euclidean Space

SESSION: Session 10

Low-Congestion Shortcuts without Embedding

The Coalescing-Branching Random Walk on Expanders and the Dual Epidemic Process

Ant-Inspired Density Estimation via Random Walks: Extended Abstract

Brief Announcement: Multi-Broadcasting under the SINR Model

Brief Announcement: Using Read-k Inequalities to Analyze a Distributed MIS Algorithm

Brief Announcement: A Key-Value Map for Massive Real-Time Analytics