ACM Principles of Distributed Computing, PODC, 2016

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: Labeling Schemes for Power-Law Graphs Casper Petersen, Noy Rotbart, Jakob Grue Simonsen, Christian Wulff-Nilsen	Brief Announcement: Labeling Schemes for Power-Law Graphs Details		Discussion Comments: 0 Verification: Authors have not verified information More...
Brief Announcement: Computing in the Presence of Weak Crash Failures Gadi Taubenfeld	Brief Announcement: Computing in the Presence of Weak Crash Failures Details		Discussion Comments: 0 Verification: Author has not verified information More...
Brief Announcement: Oh-RAM! One and a Half Round Read/Write Atomic Memory Theophanis Hadjistasi, Nicolas C. Nicolaou, Alexander A. Schwarzmann	Brief Announcement: Oh-RAM! One and a Half Round Read/Write Atomic Memory Details		Discussion Comments: 0 Verification: Authors have not verified information More...
Noisy Rumor Spreading and Plurality Consensus Pierre Fraigniaud, Emanuele Natale	Noisy Rumor Spreading and Plurality Consensus Details		Discussion Comments: 0 Verification: Authors have not verified information More...
Two-Bit Messages are Sufficient to Implement Atomic Read/Write Registers in Crash-prone Systems Achour Mostéfaoui, Michel Raynal	Two-Bit Messages are Sufficient to Implement Atomic Read/Write Registers in Crash-prone Systems Details		Discussion Comments: 0 Verification: Authors have not verified information More...
A Local Constant Factor MDS Approximation for Bounded Genus Graphs Saeed Akhoondian Amiri, Stefan Schmid, Sebastian Siebertz	A Local Constant Factor MDS Approximation for Bounded Genus Graphs Details		Discussion Comments: 0 Verification: Authors have not verified information More...
On Efficient Distributed Construction of Near Optimal Routing Schemes: Extended Abstract Michael Elkin, Ofer Neiman	On Efficient Distributed Construction of Near Optimal Routing Schemes: Extended Abstract Details		Discussion Comments: 0 Verification: Authors have not verified information More...
A Complexity-Based Hierarchy for Multiprocessor Synchronization: [Extended Abstract] Faith Ellen, Rati Gelashvili, Nir Shavit, Leqi Zhu	A Complexity-Based Hierarchy for Multiprocessor Synchronization: [Extended Abstract] Details		Discussion Comments: 0 Verification: Authors have not verified information More...
Brief Announcement: Active Information Spread in Networks Gennaro Cordasco, Luisa Gargano, Adele A. Rescigno, Ugo Vaccaro	Brief Announcement: Active Information Spread in Networks Details		Discussion Comments: 0 Verification: Authors have not verified information More...
A Faster Distributed Radio Broadcast Primitive: Extended Abstract Bernhard Haeupler, David Wajc	A Faster Distributed Radio Broadcast Primitive: Extended Abstract Details		Discussion Comments: 0 Verification: Authors have not verified information More...
Brief Announcement: Certified Universal Gathering in R² for Oblivious Mobile Robots Pierre Courtieu, Lionel Rieg, Sébastien Tixeuil, Xavier Urbain	Brief Announcement: Certified Universal Gathering in R² for Oblivious Mobile Robots Details	http://pactole.lri.fr	Discussion Comments: 0 Verification: Authors have not verified information More...
A Markov Chain Algorithm for Compression in Self-Organizing Particle Systems Sarah Cannon, Joshua J. Daymude, Dana Randall, Andréa W. Richa	A Markov Chain Algorithm for Compression in Self-Organizing Particle Systems Details		Discussion Comments: 0 Verification: Authors have not verified information More...
How Proofs are Prepared at Camelot: Extended Abstract Andreas Björklund, Petteri Kaski	How Proofs are Prepared at Camelot: Extended Abstract Details		Discussion Comments: 0 Verification: Authors have not verified information More...
Brief Announcement: Using Read-k Inequalities to Analyze a Distributed MIS Algorithm Sriram V. Pemmaraju, Talal Riaz	Brief Announcement: Using Read-k Inequalities to Analyze a Distributed MIS Algorithm Details		Discussion Comments: 0 Verification: Authors have not verified information More...
Ant-Inspired Density Estimation via Random Walks: Extended Abstract Cameron Musco, Hsin-Hao Su, Nancy A. Lynch	Ant-Inspired Density Estimation via Random Walks: Extended Abstract Details		Discussion Comments: 0 Verification: Authors have not verified information More...
Specification and Complexity of Collaborative Text Editing Hagit Attiya, Sebastian Burckhardt, Alexey Gotsman, Adam Morrison, Hongseok Yang, Marek Zawirski	Specification and Complexity of Collaborative Text Editing Details		Discussion Comments: 0 Verification: Authors have not verified information More...
Are Shared Objects Composable under an Oblivious Adversary? Oksana Denysyuk, Philipp Woelfel	Are Shared Objects Composable under an Oblivious Adversary? Details		Discussion Comments: 0 Verification: Authors have not verified information More...
A Distributed (2+ε)-Approximation for Vertex Cover in O(logδ/ε log log δ) Rounds Reuven Bar-Yehuda, Keren Censor-Hillel, Gregory Schwartzman	A Distributed (2+ε)-Approximation for Vertex Cover in O(logδ/ε log log δ) Rounds Details		Discussion Comments: 0 Verification: Authors have not verified information More...
A Randomized Concurrent Algorithm for Disjoint Set Union Siddhartha V. Jayanti, Robert E. Tarjan	A Randomized Concurrent Algorithm for Disjoint Set Union Details		Discussion Comments: 0 Verification: Authors have not verified information More...
Brief Announcement: Multi-Broadcasting under the SINR Model Sai Praneeth Reddy, Shailesh Vaya	Brief Announcement: Multi-Broadcasting under the SINR Model Details		Discussion Comments: 0 Verification: Authors have not verified information More...
Brief Announcement: The Small World of Curious Beings Soroush Alamdari	Brief Announcement: The Small World of Curious Beings Details		Discussion Comments: 0 Verification: Author has not verified information More...
Brief Announcement: Self-stabilizing Clock Synchronization with 3-bit Messages Lucas Boczkowski, Amos Korman, Emanuele Natale	Brief Announcement: Self-stabilizing Clock Synchronization with 3-bit Messages Details		Discussion Comments: 0 Verification: Authors have not verified information More...
How Asynchrony Affects Rumor Spreading Time George Giakkoupis, Yasamin Nazari, Philipp Woelfel	How Asynchrony Affects Rumor Spreading Time Details		Discussion Comments: 0 Verification: Authors have not verified information More...
A Polylogarithmic Gossip Algorithm for Plurality Consensus Mohsen Ghaffari, Merav Parter	A Polylogarithmic Gossip Algorithm for Plurality Consensus Details		Discussion Comments: 0 Verification: Authors have not verified information More...
Fault-Tolerant Multi-Agent Optimization: Optimal Iterative Distributed Algorithms Lili Su, Nitin H. Vaidya	Fault-Tolerant Multi-Agent Optimization: Optimal Iterative Distributed Algorithms Details		Discussion Comments: 0 Verification: Authors have not verified information More...
Brief Announcement: A Family of Leaderless Generalized-Consensus Algorithms Giuliano Losa, Sebastiano Peluso, Binoy Ravindran	Brief Announcement: A Family of Leaderless Generalized-Consensus Algorithms Details	http://losa.fr/research/leaderless giuliano@losa.fr	Author Comments: Discussion Comments: 0 Sharing: Research produced artifacts Verification: Authors have verified information More...
Brief Announcement: Reliable Message Transmission under Partial Knowledge and General Adversaries Aris Pagourtzis, Giorgos Panagiotakos, Dimitris Sakavalas	Brief Announcement: Reliable Message Transmission under Partial Knowledge and General Adversaries Details		Author Comments: Discussion Comments: 0 Sharing: Research produced no artifacts Verification: Authors have verified information More...
Uniform Deployment of Mobile Agents in Asynchronous Rings Masahiro Shibata, Toshiya Mega, Fukuhito Ooshita, Hirotsugu Kakugawa, Toshimitsu Masuzawa	Uniform Deployment of Mobile Agents in Asynchronous Rings Details		Author Comments: Discussion Comments: 0 Sharing: Research produced no artifacts Verification: Authors have verified information More...
Brief Announcement: A Key-Value Map for Massive Real-Time Analytics Dmitry Basin, Edward Bortnikov, Anastasia Braginsky, Guy Golan-Gueta, Eshcar Hillel, Idit Keidar, Moshe Sulamy	Brief Announcement: A Key-Value Map for Massive Real-Time Analytics Details	https://github.com/sdimbsn/KiWi	Author Comments: Discussion Comments: 0 Sharing: Research produced artifacts Verification: Authors have verified information More...
Brief Announcement: Proactive Secret Sharing with a Dishonest Majority Shlomi Dolev, Karim Eldefrawy, Joshua Lampkins, Rafail Ostrovsky, Moti Yung	Brief Announcement: Proactive Secret Sharing with a Dishonest Majority Details		Discussion Comments: 0 Verification: Authors have not verified information More...
Optimal Dynamic Distributed MIS Keren Censor-Hillel, Elad Haramaty, Zohar S. Karnin	Optimal Dynamic Distributed MIS Details		Discussion Comments: 0 Verification: Authors have not verified information More...
Deterministic Objects: Life Beyond Consensus Yehuda Afek, Faith Ellen, Eli Gafni	Deterministic Objects: Life Beyond Consensus Details		Discussion Comments: 0 Verification: Authors have not verified information More...
Optimal Mobile Byzantine Fault Tolerant Distributed Storage: Extended Abstract Silvia Bonomi, Antonella Del Pozzo, Maria Potop-Butucaru, Sébastien Tixeuil	Optimal Mobile Byzantine Fault Tolerant Distributed Storage: Extended Abstract Details		Discussion Comments: 0 Verification: Authors have not verified information More...
Brief Announcement: A Tight Space Bound for Consensus Leqi Zhu	Brief Announcement: A Tight Space Bound for Consensus Details		Discussion Comments: 0 Verification: Author has not verified information More...
Reliable Communication over Highly Connected Noisy Networks Noga Alon, Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler	Reliable Communication over Highly Connected Noisy Networks Details		Discussion Comments: 0 Verification: Authors have not verified information More...
Brief Announcement: Deterministic Graph Connectivity in the Broadcast Congested Clique Pedro Montealegre, Ioan Todinca	Brief Announcement: Deterministic Graph Connectivity in the Broadcast Congested Clique Details		Discussion Comments: 0 Verification: Authors have not verified information More...
Brief Announcement: Probabilistic Asynchronous Arbitrary Pattern Formation Quentin Bramas, Sébastien Tixeuil	Brief Announcement: Probabilistic Asynchronous Arbitrary Pattern Formation Details		Discussion Comments: 0 Verification: Authors have not verified information More...
Concurrent Data Structures Faith Ellen, Trevor Brown	Concurrent Data Structures Details		Discussion Comments: 0 Verification: Authors have not verified information More...
An Algorithm for Replicated Objects with Efficient Reads Tushar Deepak Chandra, Vassos Hadzilacos, Sam Toueg	An Algorithm for Replicated Objects with Efficient Reads Details		Discussion Comments: 0 Verification: Authors have not verified information More...
Brief Announcement: Data Dissemination in Unified Dynamic Wireless Networks Magnús M. Halldórsson, Tigran Tonoyan, Yuexuan Wang, Dongxiao Yu	Brief Announcement: Data Dissemination in Unified Dynamic Wireless Networks Details		Author Comments: Discussion Comments: 0 Sharing: Research produced no artifacts Verification: Authors have verified information More...
MST in Log-Star Rounds of Congested Clique Mohsen Ghaffari, Merav Parter	MST in Log-Star Rounds of Congested Clique Details		Discussion Comments: 0 Verification: Authors have not verified information More...
Search on a Line with Faulty Robots Jurek Czyzowicz, Evangelos Kranakis, Danny Krizanc, Lata Narayanan, Jaroslav Opatrny	Search on a Line with Faulty Robots Details		Discussion Comments: 0 Verification: Authors have not verified information More...
Brief Announcement: Asynchronous Coordination with Constraints and Preferences Armando Castañeda, Pierre Fraigniaud, Eli Gafni, Sergio Rajsbaum, Matthieu Roy	Brief Announcement: Asynchronous Coordination with Constraints and Preferences Details		Discussion Comments: 0 Verification: Authors have not verified information More...
Low-Congestion Shortcuts without Embedding Bernhard Haeupler, Taisuke Izumi, Goran Zuzic	Low-Congestion Shortcuts without Embedding Details		Discussion Comments: 0 Verification: Authors have not verified information More...
Brief Announcement: Pattern Formation Problem for Synchronous Mobile Robots in the Three Dimensional Euclidean Space Yukiko Yamauchi, Taichi Uehara, Masafumi Yamashita	Brief Announcement: Pattern Formation Problem for Synchronous Mobile Robots in the Three Dimensional Euclidean Space Details		Discussion Comments: 0 Verification: Authors have not verified information More...
The Greedy Spanner is Existentially Optimal Arnold Filtser, Shay Solomon	The Greedy Spanner is Existentially Optimal Details		Discussion Comments: 0 Verification: Authors have not verified information More...
Distributed Algorithms for Planar Networks I: Planar Embedding Mohsen Ghaffari, Bernhard Haeupler	Distributed Algorithms for Planar Networks I: Planar Embedding Details		Discussion Comments: 0 Verification: Authors have not verified information More...
Brief Announcement: Space-Time Tradeoffs for Distributed Verification Mor Baruch, Rafail Ostrovsky, Will Rosenbaum	Brief Announcement: Space-Time Tradeoffs for Distributed Verification Details		Discussion Comments: 0 Verification: Authors have not verified information More...
Rational Consensus: Extended Abstract Joseph Y. Halpern, Xavier Vilaça	Rational Consensus: Extended Abstract Details		Discussion Comments: 0 Verification: Authors have not verified information More...
Distributed Strong Diameter Network Decomposition: Extended Abstract Michael Elkin, Ofer Neiman	Distributed Strong Diameter Network Decomposition: Extended Abstract Details		Discussion Comments: 0 Verification: Authors have not verified information More...
Broadcast Extensions with Optimal Communication and Round Complexity Chaya Ganesh, Arpita Patra	Broadcast Extensions with Optimal Communication and Round Complexity Details		Discussion Comments: 0 Verification: Authors have not verified information More...
Self-stabilizing Balls & Bins in Batches: The Power of Leaky Bins [Extended Abstract] Petra Berenbrink, Tom Friedetzky, Peter Kling, Frederik Mallmann-Trenn, Lars Nagel, Christopher Wastell	Self-stabilizing Balls & Bins in Batches: The Power of Leaky Bins [Extended Abstract] Details		Discussion Comments: 0 Verification: Authors have not verified information More...
How Emerging Memory Technologies Will Have You Rethinking Algorithm Design Phillip B. Gibbons	How Emerging Memory Technologies Will Have You Rethinking Algorithm Design Details		Discussion Comments: 0 Verification: Author has not verified information More...
Brief Announcement: Optimal Leader Election in Multi-Hop Radio Networks Artur Czumaj, Peter Davies	Brief Announcement: Optimal Leader Election in Multi-Hop Radio Networks Details		Discussion Comments: 0 Verification: Authors have not verified information More...
Information-Theoretic Lower Bounds on the Storage Cost of Shared Memory Emulation Viveck R. Cadambe, Zhiying Wang, Nancy A. Lynch	Information-Theoretic Lower Bounds on the Storage Cost of Shared Memory Emulation Details		Discussion Comments: 0 Verification: Authors have not verified information More...
Space Bounds for Reliable Storage: Fundamental Limits of Coding Alexander Spiegelman, Yuval Cassuto, Gregory V. Chockler, Idit Keidar	Space Bounds for Reliable Storage: Fundamental Limits of Coding Details		Discussion Comments: 0 Verification: Authors have not verified information More...
Analysing Snapshot Isolation Andrea Cerone, Alexey Gotsman	Analysing Snapshot Isolation Details		Discussion Comments: 0 Verification: Authors have not verified information More...
Brief Announcement: An Exponential Separation Between Randomized and Deterministic Complexity in the LOCAL Model Yi-Jun Chang, Tsvi Kopelowitz, Seth Pettie	Brief Announcement: An Exponential Separation Between Randomized and Deterministic Complexity in the LOCAL Model Details		Discussion Comments: 0 Verification: Authors have not verified information More...
The Coalescing-Branching Random Walk on Expanders and the Dual Epidemic Process Colin Cooper, Tomasz Radzik, Nicolas Rivera	The Coalescing-Branching Random Walk on Expanders and the Dual Epidemic Process Details		Discussion Comments: 0 Verification: Authors have not verified information More...
Brief Announcement: Sublinear-Space Distance Labeling Using Hubs Pawel Gawrychowski, Adrian Kosowski, Przemyslaw Uznanski	Brief Announcement: Sublinear-Space Distance Labeling Using Hubs Details		Discussion Comments: 0 Verification: Authors have not verified information More...
Contention Resolution on a Fading Channel Jeremy T. Fineman, Seth Gilbert, Fabian Kuhn, Calvin C. Newport	Contention Resolution on a Fading Channel Details		Discussion Comments: 0 Verification: Authors have not verified information More...
Brief Announcement: Local Independent Set Approximation Marijke H. L. Bodlaender, Magnús M. Halldórsson, Christian Konrad, Fabian Kuhn	Brief Announcement: Local Independent Set Approximation Details		Discussion Comments: 0 Verification: Authors have not verified information More...
Unbeatable Set Consensus via Topological and Combinatorial Reasoning Armando Castañeda, Yannai A. Gonczarowski, Yoram Moses	Unbeatable Set Consensus via Topological and Combinatorial Reasoning Details		Discussion Comments: 0 Verification: Authors have not verified information More...
Contention Resolution on Multiple Channels with Collision Detection Jeremy T. Fineman, Calvin Newport, Tonghe Wang	Contention Resolution on Multiple Channels with Collision Detection Details		Discussion Comments: 0 Verification: Authors have not verified information More...
New Opportunities for PODC?: Massive, Volatile, but Highly Predictable Resources Andrew A. Chien	New Opportunities for PODC?: Massive, Volatile, but Highly Predictable Resources Details		Discussion Comments: 0 Verification: Author has not verified information More...
On the Complexity of Reader-Writer Locks: Extended Abstract Danny Hendler	On the Complexity of Reader-Writer Locks: Extended Abstract Details		Discussion Comments: 0 Verification: Author has not verified information More...
Recoverable Mutual Exclusion: [Extended Abstract] Wojciech M. Golab, Aditya Ramaraju	Recoverable Mutual Exclusion: [Extended Abstract] Details		Discussion Comments: 0 Verification: Authors have not verified information More...

ACM Principles of Distributed Computing, PODC 2016