Volume
LIPIcs, Volume 46
19th International Conference on Principles of Distributed Systems (OPODIS 2015)
Event
OPODIS 2015, December 14-17, 2015, Rennes, FranceEditors
Publication Details
- published at: 2016-10-13
- Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
- ISBN: 978-3-939897-98-9
- DBLP: db/conf/opodis/opodis2015
Access Numbers
- Detailed Access Statistics available here
-
Total Document Accesses (updated on a weekly basis):
0PDF Downloads
Documents
No documents found matching your filter selection.
Document
Complete Volume
LIPIcs, Volume 46, OPODIS'15, Complete Volume
Abstract
LIPIcs, Volume 46, OPODIS'15, Complete Volume
Cite as
19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@Proceedings{anceaume_et_al:LIPIcs.OPODIS.2015,
title = {{LIPIcs, Volume 46, OPODIS'15, Complete Volume}},
booktitle = {19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-98-9},
ISSN = {1868-8969},
year = {2016},
volume = {46},
editor = {Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015},
URN = {urn:nbn:de:0030-drops-67174},
doi = {10.4230/LIPIcs.OPODIS.2015},
annote = {Keywords: Distributed Systems}
}
Document
Front Matter
Front Matter, Table of Contents, Preface, Committees, List of Authors
Abstract
Front Matter, Table of Contents, Preface, Committees, List of Authors
Cite as
19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 0:i-0:xvi, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{anceaume_et_al:LIPIcs.OPODIS.2015.0,
author = {Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
title = {{Front Matter, Table of Contents, Preface, Committees, List of Authors}},
booktitle = {19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
pages = {0:i--0:xvi},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-98-9},
ISSN = {1868-8969},
year = {2016},
volume = {46},
editor = {Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.0},
URN = {urn:nbn:de:0030-drops-66223},
doi = {10.4230/LIPIcs.OPODIS.2015.0},
annote = {Keywords: Front Matter, Table of Contents, Preface, Committees, List of Authors}
}
Document
Tutorial
Signature-Free Communication and Agreement in the Presence of Byzantine Processes (Tutorial)
Abstract
Communication and agreement are fundamental abstractions in any distributed system. (If the computing entities do not need to communicate or agree in one way or another, the system is not a distributed system!) This tutorial was devoted to the design of such abstractions built on top of signature-free asynchronous distributed systems prone to Byzantine process failures. It is made up of three parts, each devoted to an abstraction and algorithms that implement it.
Cite as
Michel Raynal. Signature-Free Communication and Agreement in the Presence of Byzantine Processes (Tutorial). In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 1:1-1:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{raynal:LIPIcs.OPODIS.2015.1,
author = {Raynal, Michel},
title = {{Signature-Free Communication and Agreement in the Presence of Byzantine Processes}},
booktitle = {19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
pages = {1:1--1:10},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-98-9},
ISSN = {1868-8969},
year = {2016},
volume = {46},
editor = {Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.1},
URN = {urn:nbn:de:0030-drops-65929},
doi = {10.4230/LIPIcs.OPODIS.2015.1},
annote = {Keywords: Asynchronous system, Atomic read/write register, Byzantine process Consensus, Distributed algorithm, Distributed computability, Fault-tolerance, No-du}
}
Document
Tutorial
Dynamic Reconfiguration: A Tutorial (Tutorial)
Abstract
A key challenge for distributed systems is the problem of reconfiguration. Clearly, any production storage system that provides data reliability and availability for long periods must be able to reconfigure in order to remove failed or old servers and add healthy or new ones. This is far from trivial since we do not want the reconfiguration management to be centralized or cause a system shutdown.
In this tutorial we look into existing reconfigurable storage algorithms. We propose a common model and failure condition capturing their guarantees. We define a reconfiguration problem around which dynamic object solutions may be designed. To demonstrate its strength, we use it to implement dynamic atomic storage. We present a generic framework for solving the reconfiguration problem, show how to recast existing algorithms in terms of this framework, and compare among them.
Cite as
Alexander Spiegelman, Idit Keidar, and Dahlia Malkhi. Dynamic Reconfiguration: A Tutorial (Tutorial). In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 2:1-2:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{spiegelman_et_al:LIPIcs.OPODIS.2015.2,
author = {Spiegelman, Alexander and Keidar, Idit and Malkhi, Dahlia},
title = {{Dynamic Reconfiguration: A Tutorial}},
booktitle = {19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
pages = {2:1--2:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-98-9},
ISSN = {1868-8969},
year = {2016},
volume = {46},
editor = {Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.2},
URN = {urn:nbn:de:0030-drops-65938},
doi = {10.4230/LIPIcs.OPODIS.2015.2},
annote = {Keywords: Dynamic reconfiguration}
}
Document
Keynote
Time to Change: On Distributed Computing in Dynamic Networks (Keynote)
Abstract
In highly dynamic networks, topological changes are not anomalies but rather integral part of their nature. Such networks are becoming quite ubiquitous. They include systems where the entities are mobile and communicate without infrastructure (e.g. vehicles, satellites, robots, or pedestrian smartphones): the topology changes as the entities move. They also include systems, such as peer-to-peer networks, where the changes are caused by entities entering and leaving the system, They even include systems where there is no physical mobility at all, such as social networks. A vast literature on these dynamic networks has been produced in many different fields, including distributed computing. The several efforts to survey the status of the research and attempts to clarify and classify models and assumptions, have so far brought more valuable bibliographic data than order and clarity. Goal of this note is to ask questions that might bring author and readers to start to clarify some important research aspects and put some order in a sometimes confusing field. The focus here is entirely on distributed computing, specifically on its deterministic aspects.
Cite as
Nicola Santoro. Time to Change: On Distributed Computing in Dynamic Networks (Keynote). In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 3:1-3:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{santoro:LIPIcs.OPODIS.2015.3,
author = {Santoro, Nicola},
title = {{Time to Change: On Distributed Computing in Dynamic Networks}},
booktitle = {19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
pages = {3:1--3:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-98-9},
ISSN = {1868-8969},
year = {2016},
volume = {46},
editor = {Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.3},
URN = {urn:nbn:de:0030-drops-65941},
doi = {10.4230/LIPIcs.OPODIS.2015.3},
annote = {Keywords: distributed computing, dynamic networks, time-varying graphs, mobile agents}
}
Document
Keynote
Space Bounds for Reliable Storage: Fundamental Limits of Coding (Keynote)
Abstract
We present here a synopsis of a keynote presentation given by Idit Keidar at OPODIS 2015, the International Conference on Principles of Distributed Systems, which took place in Rennes, France, on December 14-17 2015.
Cite as
Alexander Spiegelman, Yuval Cassuto, Gregory Chockler, and Idit Keidar. Space Bounds for Reliable Storage: Fundamental Limits of Coding (Keynote). In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 4:1-4:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{spiegelman_et_al:LIPIcs.OPODIS.2015.4,
author = {Spiegelman, Alexander and Cassuto, Yuval and Chockler, Gregory and Keidar, Idit},
title = {{Space Bounds for Reliable Storage: Fundamental Limits of Coding}},
booktitle = {19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
pages = {4:1--4:3},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-98-9},
ISSN = {1868-8969},
year = {2016},
volume = {46},
editor = {Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.4},
URN = {urn:nbn:de:0030-drops-65957},
doi = {10.4230/LIPIcs.OPODIS.2015.4},
annote = {Keywords: distributed storage, impossibility}
}
Document
Keynote
Blockchain-Based Consensus (Keynote)
Abstract
Distributed consensus (aka Byzantine agreement [Pease, Shostak & Lamport, 1980]) is one of the fundamental problems in fault-tolerant distributed computing and cryptographic protocols. It requires correct participants (parties) to reach agreement on initially held values despite the arbitrary behavior of some of them, with the additional requirement (known as Validity) that if all the correct participants start off with the same value, then that must be the decision value. The problem has been studied extensively in both the unconditional setting (where no assumptions are made about the computational power of the adversary) and the cryptographic setting, and efficient (i.e., polynomial-time) solutions exist tolerating the optimal number of misbehaving parties and running in the optimal number of rounds, on networks with pairwise authenticated channels. In many interesting scenarios, however, such as "peer-to-peer" networks, where parties come and go as they please and there are no prior relations among them, such infrastructure (pairwise authenticated channels, public-key infrastructure) is unavailable, thus raising the question whether anything "interesting" can be achieved. In this talk we answer this question in the affirmative, presenting two new probabilistic consensus protocols based on "proofs of work" (POWs, aka "moderately hard functions," "cryptographic puzzles" [Dwork & Naor, 1992]), the technology underlying Bitcoin, the first and most popular decentralized cryptocurrency to date. (In Bitcoin, POWs are implemented using the SHA-256 cryptographic hash function, by finding preimages that produce values in a given smaller domain.) In more detail, we first extract and analyze the core of the Bitcoin protocol, which we term the Bitcoin backbone, and prove two fundamental properties of its "blockchain" approach which we call "common prefix" and "chain quality." The consensus protocols can then be built as applications on top of the backbone protocol, with the Agreement and Validity properties following from common prefix and chain quality, respectively. The first protocol works assuming the adversary's hashing power is bounded by 1/3 of the network's total hashing power. The second consensus protocol is more elaborate, relies on the notion of robust transaction ledgers, which capture the essence of Bitcoin's operation as a cryptocurrency, and works assuming the adversary's hashing power is strictly less than 1/2.
Cite as
Juan A. Garay. Blockchain-Based Consensus (Keynote). In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, p. 5:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{garay:LIPIcs.OPODIS.2015.5,
author = {Garay, Juan A.},
title = {{Blockchain-Based Consensus}},
booktitle = {19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
pages = {5:1--5:1},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-98-9},
ISSN = {1868-8969},
year = {2016},
volume = {46},
editor = {Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.5},
URN = {urn:nbn:de:0030-drops-65968},
doi = {10.4230/LIPIcs.OPODIS.2015.5},
annote = {Keywords: Distributed consensus, cryptocurrencies, cryptographic protocols}
}
Document
Approximation of Distances and Shortest Paths in the Broadcast Congest Clique
Abstract
We study the broadcast version of the CONGEST-CLIQUE model of distributed computing. This model operates in synchronized rounds; in each round, any node in a network of size n can send the same message (i.e. broadcast a message) of limited size to every other node in the network. Nanongkai presented in [STOC'14] a randomized (2+o(1))-approximation algorithm to compute all pairs shortest paths (APSP) in time ~{O}(sqrt{n}) on weighted graphs. We complement this result by proving that any randomized (2-o(1))-approximation of APSP and (2-o(1))-approximation of the diameter of a graph takes ~Omega(n) time in the worst case. This demonstrates that getting a negligible improvement in the approximation factor requires significantly more time. Furthermore this bound implies that already computing a (2-o(1))-approximation of all pairs shortest paths is among the hardest graph-problems in the broadcast-version of the CONGEST-CLIQUE model, as any graph-problem where each node receives a linear amount of input can be solved trivially in linear time in this model. This contrasts a recent (1+o(1))-approximation for APSP that runs in time O(n^{0.15715}) and an exact algorithm for APSP that runs in time ~O(n^{1/3}) in the unicast version of the CONGEST-CLIQUE model, a more powerful variant of the broadcast version.
This lower bound in the broadcast CONGEST-CLIQUE model is derived by first establishing a new lower bound for (2-o(1))-approximating the diameter in weighted graphs in the CONGEST model, which is of independent interest. This lower bound is then transferred to the CONGEST-CLIQUE model.
On the positive side we provide a deterministic version of Nanongkai's (2+o(1))-approximation algorithm for APSP. To do so we present a fast deterministic construction of small hitting sets. We also show how to replace another randomized part within Nanongkai's algorithm with a deterministic source-detection algorithm designed for the CONGEST model.
Cite as
Stephan Holzer and Nathan Pinsker. Approximation of Distances and Shortest Paths in the Broadcast Congest Clique. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 6:1-6:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{holzer_et_al:LIPIcs.OPODIS.2015.6,
author = {Holzer, Stephan and Pinsker, Nathan},
title = {{Approximation of Distances and Shortest Paths in the Broadcast Congest Clique}},
booktitle = {19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
pages = {6:1--6:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-98-9},
ISSN = {1868-8969},
year = {2016},
volume = {46},
editor = {Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.6},
URN = {urn:nbn:de:0030-drops-65971},
doi = {10.4230/LIPIcs.OPODIS.2015.6},
annote = {Keywords: distributed computing, distributed algorithms, approximation algorithms}
}
Document
The Cost of Global Broadcast in Dynamic Radio Networks
Abstract
We study the single-message broadcast problem in dynamic radio networks. We show that the time complexity of the problem depends on the amount of stability and connectivity of the dynamic network topology and on the adaptiveness of the adversary providing the dynamic topology. More formally, we model communication using the standard graph-based radio network model. To model the dynamic network, we use a variant of the synchronous dynamic graph model introduced in [Kuhn et al., STOC 2010]. For integer parameters T >= 1 and k => 1, we call a dynamic graph T-interval k-connected if for every interval of T consecutive rounds, there exists a k-vertex-connected stable subgraph. Further, for an integer parameter tau >= 0, we say that the adversary providing the dynamic network is tau-oblivious if for constructing the graph of some round t, the adversary has access to all the randomness (and states) of the algorithm up to round t-tau.
As our main result, we show that for any T >= 1, any k >= 1, and any tau = 1, for a tau-oblivious adversary, there is a distributed algorithm to broadcast a single message in time O((1+n/(k * min(tau,T)) * n *log^3(n)). We further show that even for large interval k-connectivity, efficient broadcast is not possible for the usual adaptive adversaries. For a 1-oblivious adversary, we show that even for any T <= (n/k)^{1-epsilon} (for any constant epsilon > 0) and for any k >= 1, global broadcast in T-interval k-connected networks requires at least Omega(n^2/k^2*log(n)) time. Further, for a 0-oblivious adversary, broadcast cannot be solved in T-interval k-connected networks as long as T < n-k.
Cite as
Mohamad Ahmadi, Abdolhamid Ghodselahi, Fabian Kuhn, and Anisur Rahaman Molla. The Cost of Global Broadcast in Dynamic Radio Networks. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 7:1-7:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{ahmadi_et_al:LIPIcs.OPODIS.2015.7,
author = {Ahmadi, Mohamad and Ghodselahi, Abdolhamid and Kuhn, Fabian and Molla, Anisur Rahaman},
title = {{The Cost of Global Broadcast in Dynamic Radio Networks}},
booktitle = {19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
pages = {7:1--7:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-98-9},
ISSN = {1868-8969},
year = {2016},
volume = {46},
editor = {Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.7},
URN = {urn:nbn:de:0030-drops-65989},
doi = {10.4230/LIPIcs.OPODIS.2015.7},
annote = {Keywords: radio network, dynamic network, global broadcast, interval connectivity, hitting game}
}
Document
Bounds for Blind Rate Adaptation
Abstract
A core challenge in wireless communication is choosing appropriate transmission rates for packets. This rate selection problem is well understood in the context of unicast communication from a sender to a known receiver that can reply with acknowledgments. The problem is more difficult, however, in the multicast scenario where a sender must communicate with a potentially large and changing group of receivers with varied link qualities. In such settings, it is inefficient to gather feedback, and achieving good performance for every receiver is complicated by the potential diversity of their link conditions. This paper tackles this problem from an algorithmic perspective: identifying near optimal strategies for selecting rates that guarantee every receiver achieves throughput within reasonable factors of the optimal capacity of its link to the sender. Our algorithms have the added benefit that they are blind: they assume the sender has no information about the network and receives no feedback on its transmissions. We then prove new lower bounds on the fundamental difficulty of achieving good performance in the presence of fast fading (rapid and frequent changes to link quality), and conclude by studying strategies for achieving good throughput over multiple hops. We argue that the implementation of our algorithms should be easy because of the feature of being blind (it is independent to the network structure and the quality of links, so it's robust to changes). Our theoretical framework yields many new open problems within this important general topic of distributed transmission rate selection.
Cite as
Seth Gilbert, Calvin Newport, and Tonghe Wang. Bounds for Blind Rate Adaptation. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 8:1-8:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{gilbert_et_al:LIPIcs.OPODIS.2015.8,
author = {Gilbert, Seth and Newport, Calvin and Wang, Tonghe},
title = {{Bounds for Blind Rate Adaptation}},
booktitle = {19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
pages = {8:1--8:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-98-9},
ISSN = {1868-8969},
year = {2016},
volume = {46},
editor = {Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.8},
URN = {urn:nbn:de:0030-drops-65998},
doi = {10.4230/LIPIcs.OPODIS.2015.8},
annote = {Keywords: bitrate, multicast, packet transmission, latency, competitive ratio, lower bound, fading}
}
Document
Overcoming Obstacles with Ants
Abstract
Consider a group of mobile finite automata, referred to as agents, located in the origin of an infinite grid. The grid is occupied by obstacles, i.e., sets of cells that can not be entered by the agents. In every step, an agent can sense the states of the co-located agents and is allowed to move to any neighboring cell of the grid not blocked by an obstacle. We assume that the circumference of each obstacle is finite but allow the number of obstacles to be unbounded. The task of the agents is to cooperatively find a treasure, hidden in the grid by an adversary.
In this work, we show how the agents can utilize their simple means of communication and their constant memory to systematically explore the grid and to locate the treasure in finite time. As integral part of the agents' behavior, we present a method that allows a group of six agents to follow a straight line, even if the line is partially obstructed by obstacles, and to discover all free cells along this line. In total, our search protocol requires nine agents.
Cite as
Tobias Langner, Barbara Keller, Jara Uitto, and Roger Wattenhofer. Overcoming Obstacles with Ants. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 9:1-9:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{langner_et_al:LIPIcs.OPODIS.2015.9,
author = {Langner, Tobias and Keller, Barbara and Uitto, Jara and Wattenhofer, Roger},
title = {{Overcoming Obstacles with Ants}},
booktitle = {19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
pages = {9:1--9:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-98-9},
ISSN = {1868-8969},
year = {2016},
volume = {46},
editor = {Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.9},
URN = {urn:nbn:de:0030-drops-66005},
doi = {10.4230/LIPIcs.OPODIS.2015.9},
annote = {Keywords: Mobile agents, algorithms, treasure search}
}
Document
Distributed Sparse Cut Approximation
Abstract
We study the problem of computing a sparse cut in an undirected network graph G=(V,E). We measure the sparsity of a cut (S,V\S) by its conductance phi(S), i.e., by the ratio of the number of edges crossing the cut and the sum of the degrees on the smaller of the two sides. We present an efficient distributed algorithm to compute a cut of low conductance. Specifically, given two parameters b and phi, if there exists a cut of balance at least b and conductance at most phi, our algorithm outputs a cut of balance at least b/2 and conductance at most ~O(sqrt{phi}), where ~O(.) hides polylogarithmic factors in the number of nodes n. Our distributed algorithm works in the \congest model, i.e., it only requires to send messages of size at most O(log(n)) bits. The time complexity of the algorithm is ~O(D + 1/b*phi), where D is the diameter of G. This is a significant improvement over a result by Das Sarma et al. [ICDCN 2015], where it is shown that a cut of the same quality can be computed in time ~O(n + 1/b*phi). The improved running time is in particular achieved by devising and applying an efficient distributed algorithm for the all-prefix-sums problem in a distributed search tree. This algorithm, which is based on the classic parallel all-prefix-sums algorithm, might be of independent interest.
Cite as
Fabian Kuhn and Anisur Rahaman Molla. Distributed Sparse Cut Approximation. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 10:1-10:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{kuhn_et_al:LIPIcs.OPODIS.2015.10,
author = {Kuhn, Fabian and Molla, Anisur Rahaman},
title = {{Distributed Sparse Cut Approximation}},
booktitle = {19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
pages = {10:1--10:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-98-9},
ISSN = {1868-8969},
year = {2016},
volume = {46},
editor = {Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.10},
URN = {urn:nbn:de:0030-drops-66014},
doi = {10.4230/LIPIcs.OPODIS.2015.10},
annote = {Keywords: sparsest cut, conductance, random walks, all-prefix-sums}
}
Document
Distributed Approximation of k-Service Assignment
Abstract
We consider the k-Service Assignment problem (k-SA), defined as follows. The input consists of a network that contains servers and clients, and an integer k. Each server has a finite capacity, and each client is associated with a demand and a profit. A feasible solution is an assignment of clients to neighboring servers such that (i) the total demand assigned to a server is at most its capacity, and (ii) a client is assigned either to k servers or to none. The profit of an assignment is the total profit of clients that are assigned to k servers, and the goal is to find a maximum profit assignment. In the r-restricted version of k-SA, no client requires more than an r-fraction of the capacity of any adjacent server. The k-SA problem is motivated by backup placement in networks and by resource allocation in 4G cellular networks. It can also be viewed as machine scheduling on related machines with assignment restrictions.
We present a centralized polynomial time greedy (k+1-r)/(1-r)-approximation algorithm for r-restricted k-SA. We then show that a variant of this algorithm achieves an approximation ratio of k+1 using a resource augmentation factor of 1+r. We use the latter to present a (k+1)^2-approximation algorithm for k-SA. In the distributed setting, we present: (i) a (1+epsilon)*(k +1-r)/(1-r)-approximation algorithm for r-restricted k-SA, (ii) a (1+epsilon)(k+1)-approximation algorithm that uses a resource augmentation factor of 1+r for r-restricted k-SA, both for any constant epsilon>0, and (iii) an O{k^2}-approximation algorithm for k-SA (in expectation). The three distributed algorithms compute a solution with high probability and terminate in O(k^2 *log^3(n)) rounds.
Cite as
Magnús M. Halldórsson, Sven Köhler, and Dror Rawitz. Distributed Approximation of k-Service Assignment. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 11:1-11:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{halldorsson_et_al:LIPIcs.OPODIS.2015.11,
author = {Halld\'{o}rsson, Magn\'{u}s M. and K\"{o}hler, Sven and Rawitz, Dror},
title = {{Distributed Approximation of k-Service Assignment}},
booktitle = {19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
pages = {11:1--11:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-98-9},
ISSN = {1868-8969},
year = {2016},
volume = {46},
editor = {Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.11},
URN = {urn:nbn:de:0030-drops-66024},
doi = {10.4230/LIPIcs.OPODIS.2015.11},
annote = {Keywords: approximation algorithms, distributed algorithms, related machines}
}
Document
On the Uncontended Complexity of Anonymous Consensus
Abstract
Consensus is one of the central distributed abstractions. By enabling a collection of processes to agree on one of the values they propose, consensus can be used to implement any generic replicated service in a consistent and fault-tolerant way.
In this paper, we study uncontended complexity of anonymous consensus algorithms, counting the number of memory locations used and the number of memory updates performed in operations that encounter no contention. We assume that contention-free operations on a consensus object perform "fast" reads and writes, and resort to more expensive synchronization primitives, such as CAS, only when contention is detected. We call such concurrent implementations interval-solo-fast and derive one of the first nontrivial tight bounds on space complexity of anonymous interval-solo-fast consensus.
Cite as
Claire Capdevielle, Colette Johnen, Petr Kuznetsov, and Alessia Milani. On the Uncontended Complexity of Anonymous Consensus. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 12:1-12:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{capdevielle_et_al:LIPIcs.OPODIS.2015.12,
author = {Capdevielle, Claire and Johnen, Colette and Kuznetsov, Petr and Milani, Alessia},
title = {{On the Uncontended Complexity of Anonymous Consensus}},
booktitle = {19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
pages = {12:1--12:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-98-9},
ISSN = {1868-8969},
year = {2016},
volume = {46},
editor = {Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.12},
URN = {urn:nbn:de:0030-drops-66034},
doi = {10.4230/LIPIcs.OPODIS.2015.12},
annote = {Keywords: space and time complexity, lower bounds, consensus, interval contention, solo-fast}
}
Document
The Relative Power of Composite Loop Agreement Tasks
Abstract
Loop agreement is a family of distributed tasks that includes set agreement and simplex agreement, and was used to prove the undecidability of wait-free solvability of distributed tasks by read/write memory. Herlihy and Rajsbaum defined the algebraic signature of a loop agreement task, which consists of a group and a distinguished element. They used the algebraic signature to characterize the relative power of loop agreement tasks. In particular, they showed that one task implements another exactly when there is a homomorphism between their respective signatures sending one loop to the other. In this paper, we extend the previous result by defining the composition of multiple loop agreement tasks to create a new one with the same combined power. We generalize the original algebraic characterization for relative power to compositions of tasks. In this way, we can think of loop agreement tasks in terms of their basic building blocks. We also investigate a category-theoretic perspective of loop agreement by defining a category of loops, showing that the algebraic signature is a functor, and proving that our definition of task composition is the "correct" one, in a categorical sense.
Cite as
Vikram Saraph and Maurice Herlihy. The Relative Power of Composite Loop Agreement Tasks. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 13:1-13:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{saraph_et_al:LIPIcs.OPODIS.2015.13,
author = {Saraph, Vikram and Herlihy, Maurice},
title = {{The Relative Power of Composite Loop Agreement Tasks}},
booktitle = {19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
pages = {13:1--13:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-98-9},
ISSN = {1868-8969},
year = {2016},
volume = {46},
editor = {Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.13},
URN = {urn:nbn:de:0030-drops-66044},
doi = {10.4230/LIPIcs.OPODIS.2015.13},
annote = {Keywords: Distributed computing, loop agreement, task composition, topology}
}
Document
Loosely-Stabilizing Leader Election on Arbitrary Graphs in Population Protocols Without Identifiers nor Random Numbers
Abstract
In the population protocol model Angluin et al. proposed in 2004, there exists no self-stabilizing leader election protocol for complete graphs, arbitrary graphs, trees, lines, degree-bounded graphs and so on unless the protocol knows the exact number of nodes. To circumvent the impossibility, we introduced the concept of loose-stabilization in 2009, which relaxes the closure requirement of self-stabilization. A loosely-stabilizing protocol guarantees that starting from any initial configuration a system reaches a safe configuration, and after that, the system keeps its specification (e.g. the unique leader) not forever, but for a sufficiently long time (e.g. exponentially large time with respect to the number of nodes). Our previous works presented two loosely-stabilizing leader election protocols for arbitrary graphs; One uses agent identifiers and the other uses random numbers to elect a unique leader. In this paper, we present a loosely-stabilizing protocol that solves leader election on arbitrary graphs without agent identifiers nor random numbers. By the combination of virus-propagation and token-circulation, the proposed protocol achieves polynomial convergence time and exponential holding time without such external entities. Specifically, given upper bounds N and Delta of the number of nodes n and the maximum degree of nodes delta respectively, it reaches a safe configuration within O(m*n^3*d + m*N*Delta^2*log(N)) expected steps, and keeps the unique leader for Omega(N*e^N) expected steps where m is the number of edges and d is the diameter of the graph. To measure the time complexity of the protocol, we assume the uniformly random scheduler which is widely used in the field of the population protocols.
Cite as
Yuichi Sudo, Fukuhito Ooshita, Hirotsugu Kakugawa, and Toshimitsu Masuzawa. Loosely-Stabilizing Leader Election on Arbitrary Graphs in Population Protocols Without Identifiers nor Random Numbers. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 14:1-14:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{sudo_et_al:LIPIcs.OPODIS.2015.14,
author = {Sudo, Yuichi and Ooshita, Fukuhito and Kakugawa, Hirotsugu and Masuzawa, Toshimitsu},
title = {{Loosely-Stabilizing Leader Election on Arbitrary Graphs in Population Protocols Without Identifiers nor Random Numbers}},
booktitle = {19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
pages = {14:1--14:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-98-9},
ISSN = {1868-8969},
year = {2016},
volume = {46},
editor = {Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.14},
URN = {urn:nbn:de:0030-drops-66054},
doi = {10.4230/LIPIcs.OPODIS.2015.14},
annote = {Keywords: Loose-stabilization, Population protocols, Leader election}
}
Document
A Heap-Based Concurrent Priority Queue with Mutable Priorities for Faster Parallel Algorithms
Abstract
Existing concurrent priority queues do not allow to update the priority of an element after its insertion. As a result, algorithms that need this functionality, such as Dijkstra's single source shortest path algorithm, resort to cumbersome and inefficient workarounds. We report on a heap-based concurrent priority queue which allows to change the priority of an element after its insertion. We show that the enriched interface allows to express Dijkstra's algorithm in a more natural way, and that its implementation, using our concurrent priority queue, outperform existing algorithms.
Cite as
Orr Tamir, Adam Morrison, and Noam Rinetzky. A Heap-Based Concurrent Priority Queue with Mutable Priorities for Faster Parallel Algorithms. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 15:1-15:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{tamir_et_al:LIPIcs.OPODIS.2015.15,
author = {Tamir, Orr and Morrison, Adam and Rinetzky, Noam},
title = {{A Heap-Based Concurrent Priority Queue with Mutable Priorities for Faster Parallel Algorithms}},
booktitle = {19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
pages = {15:1--15:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-98-9},
ISSN = {1868-8969},
year = {2016},
volume = {46},
editor = {Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.15},
URN = {urn:nbn:de:0030-drops-66068},
doi = {10.4230/LIPIcs.OPODIS.2015.15},
annote = {Keywords: priority queues, concurrent data structures, Dijkstra's single-source shortest path algorithm}
}
Document
Maximum Matching for Anonymous Trees with Constant Space per Process
Abstract
We give a silent self-stabilizing protocol for computing a maximum matching in an anonymous network with a tree topology. The round complexity of our protocol is O(diam), where diam is the diameter of the network, and the step complexity is O(n*diam), where n is the number of processes in the network. The working space complexity is O(1) per process, although the output necessarily takes O(log(delta)) space per process, where delta is the degree of that process. To implement parent pointers in constant space, regardless of degree, we use the cyclic Abelian group Z_7.
Cite as
Ajoy K. Datta, Lawrence L. Larmore, and Toshimitsu Masuzawa. Maximum Matching for Anonymous Trees with Constant Space per Process. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 16:1-16:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{datta_et_al:LIPIcs.OPODIS.2015.16,
author = {Datta, Ajoy K. and Larmore, Lawrence L. and Masuzawa, Toshimitsu},
title = {{Maximum Matching for Anonymous Trees with Constant Space per Process}},
booktitle = {19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
pages = {16:1--16:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-98-9},
ISSN = {1868-8969},
year = {2016},
volume = {46},
editor = {Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.16},
URN = {urn:nbn:de:0030-drops-66074},
doi = {10.4230/LIPIcs.OPODIS.2015.16},
annote = {Keywords: anonymous tree, maximum matching, self-stabilization, unfair daemon}
}
Document
Atomic Snapshots from Small Registers
Abstract
Existing n-process implementations of atomic snapshots from registers use large registers. We consider the problem of implementing an m-component snapshot from small, Theta(log(n))-bit registers. A natural solution is to consider simulating the large registers. Doing so straightforwardly can significantly increase the step complexity. We introduce the notion of an interruptible read and show how it can reduce the step complexity of simulating the large registers in the snapshot of Afek et al. In particular, we show how to modify a recent large register simulation to support interruptible reads. Using this modified simulation, the step complexity of UPDATE and SCAN changes from Theta(n*m) to Theta(n*m+m*w), instead of Theta(n*m*w), if each component of the snapshot consists of Theta(w*log(n)) bits. We also show how to modify a limited-use snapshot to use small registers when the number of UPDATE operations is in n^{O(1)}. In this case, we change the step complexity of UPDATE from Theta((log(n))^3) to O(w + (log(n))^2*log(m)) and the step complexity of SCAN from Theta(log(n)) to O(m*w + log(n)).
Cite as
Leqi Zhu and Faith Ellen. Atomic Snapshots from Small Registers. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 17:1-17:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{zhu_et_al:LIPIcs.OPODIS.2015.17,
author = {Zhu, Leqi and Ellen, Faith},
title = {{Atomic Snapshots from Small Registers}},
booktitle = {19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
pages = {17:1--17:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-98-9},
ISSN = {1868-8969},
year = {2016},
volume = {46},
editor = {Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.17},
URN = {urn:nbn:de:0030-drops-66084},
doi = {10.4230/LIPIcs.OPODIS.2015.17},
annote = {Keywords: atomic snapshot, limited-use snapshot, small registers, simulation}
}
Document
Anonymous Obstruction-Free (n,k)-Set Agreement with n-k+1 Atomic Read/Write Registers
Abstract
The k-set agreement problem is a generalization of the consensus problem. Namely, assuming that each process proposes a value, every non-faulty process should decide one of the proposed values, and no more than k different values should be decided. This is a hard problem in the sense that we cannot solve it in an asynchronous system, as soon as k or more processes may crash. One way to sidestep this impossibility result consists in weakening the termination property, requiring that a process must decide a value only if it executes alone during a long enough period of time. This is the well-known obstruction-freedom progress condition.
Consider a system of n anonymous asynchronous processes that communicate through atomic read/write registers, and such that any number of them may crash. In this paper, we address and solve the challenging open problem of designing an obstruction-free k-set agreement algorithm using only (n-k+1) atomic registers. From a shared memory cost point of view, our algorithm is the best algorithm known so far, thereby establishing a new upper bound on the number of registers needed to solve the problem, and in comparison to the previous upper bound, its gain is (n-k) registers. We then extend this algorithm into a space-optimal solution for the repeated version of k-set agreement, and an x-obstruction-free solution that employs 0(n-k+x) atomic registers (with 1 <= x <= k < n).
Cite as
Zohir Bouzid, Michel Raynal, and Pierre Sutra. Anonymous Obstruction-Free (n,k)-Set Agreement with n-k+1 Atomic Read/Write Registers. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 18:1-18:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{bouzid_et_al:LIPIcs.OPODIS.2015.18,
author = {Bouzid, Zohir and Raynal, Michel and Sutra, Pierre},
title = {{Anonymous Obstruction-Free (n,k)-Set Agreement with n-k+1 Atomic Read/Write Registers}},
booktitle = {19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
pages = {18:1--18:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-98-9},
ISSN = {1868-8969},
year = {2016},
volume = {46},
editor = {Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.18},
URN = {urn:nbn:de:0030-drops-66092},
doi = {10.4230/LIPIcs.OPODIS.2015.18},
annote = {Keywords: Anonymous processes, Asynchronous system, Atomic read/write register, Consensus, Fault-tolerance, \$k\$-Set agreement, Obstruction-freedom, Upper bound}
}
Document
Making "Fast" Atomic Operations Computationally Tractable
Abstract
Communication overhead is the most commonly used performance metric for the operation complexity of distributed algorithms in message-passing environments. However, aside with communication, many distributed operations utilize complex computations to reach their desired outcomes. Therefore, a most accurate operation latency measure should account of both computation and communication metrics.
In this paper we focus on the efficiency of read and write operations in an atomic read/write shared memory emulation in the message-passing environment. We examine the operation complexity of the best known atomic register algorithm, that allows all read and write operations to complete in a single communication round-trip. Such operations are called fast. At its heart, the algorithm utilizes a predicate to allow processes to compute their outcome. We show that the predicate used is computationally hard, by devising a computationally equivalent problem and reducing that to Maximum Biclique, a known NP-hard problem. To improve the computational complexity of the algorithm we derive a new predicate that leads to a new algorithm, we call ccFast, and has the following properties: (i) can be computed in polynomial time, rendering each read operation in ccFast tractable compared to the read operations in the original algorithm, (ii) the messages used in ccFast are reduced in size, compared to the original algorithm, by almost a linear factor, (iii) allows all operations in ccFast to be fast, and (iv) allows ccFast to preserve atomicity. A linear time}algorithm for the computation of the new predicate is presented along with an analysis of the message complexity of the new algorithm. We believe that the new algorithm redefines the term fast capturing both the communication and the computation metrics of each operation.
Cite as
Antonio Fernández Anta, Nicolas Nicolaou, and Alexandru Popa. Making "Fast" Atomic Operations Computationally Tractable. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 19:1-19:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{fernandezanta_et_al:LIPIcs.OPODIS.2015.19,
author = {Fern\'{a}ndez Anta, Antonio and Nicolaou, Nicolas and Popa, Alexandru},
title = {{Making "Fast" Atomic Operations Computationally Tractable}},
booktitle = {19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
pages = {19:1--19:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-98-9},
ISSN = {1868-8969},
year = {2016},
volume = {46},
editor = {Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.19},
URN = {urn:nbn:de:0030-drops-66108},
doi = {10.4230/LIPIcs.OPODIS.2015.19},
annote = {Keywords: atomicity, read/write objects, shared memory, computational complexity}
}
Document
Robust Shared Objects for Non-Volatile Main Memory
Abstract
Research in concurrent in-memory data structures has focused almost exclusively on models where processes are either reliable, or may fail by crashing permanently. The case where processes may recover from failures has received little attention because recovery from conventional volatile memory is impossible in the event of a system crash, during which both the state of main memory and the private states of processes are lost. Future hardware architectures are likely to include various forms of non-volatile random access memory (NVRAM), creating new opportunities to design robust main memory data structures that can recover from system crashes. In this paper we advance the theoretical foundations of such data structures in two ways. First, we review several known variations of Herlihy and Wing's linearizability property that were proposed in the context of message passing systems but also apply in our NVRAM-based model, we discuss the limitations of these properties with respect to our specific goals, and we propose an alternative correctness condition called recoverable linearizability. Second, we discuss techniques for implementing shared objects that satisfy such properties with a focus on wait-free implementations. Specifically, we demonstrate how to achieve different variations of linearizability in our model by transforming two classic wait-free constructions.
Cite as
Ryan Berryhill, Wojciech Golab, and Mahesh Tripunitara. Robust Shared Objects for Non-Volatile Main Memory. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 20:1-20:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{berryhill_et_al:LIPIcs.OPODIS.2015.20,
author = {Berryhill, Ryan and Golab, Wojciech and Tripunitara, Mahesh},
title = {{Robust Shared Objects for Non-Volatile Main Memory}},
booktitle = {19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
pages = {20:1--20:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-98-9},
ISSN = {1868-8969},
year = {2016},
volume = {46},
editor = {Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.20},
URN = {urn:nbn:de:0030-drops-66116},
doi = {10.4230/LIPIcs.OPODIS.2015.20},
annote = {Keywords: non-volatile main memory, concurrency, recovery, data structures}
}
Document
The Benefits of Entropy in Population Protocols
Abstract
A distributed computing system can be viewed as the result of the interplay between a distributed algorithm specifying the effects of a local event (e.g. reception of a message), and an adversary choosing the interleaving (schedule) of these events in the execution. In the context of large networks of mobile pairwise interacting agents (population protocols), the adversary models the mobility of the agents by choosing the successive pairs of interacting agents. For some problems, assuming that the adversary selects the schedule according to some probability distribution greatly helps to devise (almost) correct solutions. But how much randomness is really necessary? To what extent does a problem admit implementations that are robust against a "not so random" schedule? This paper takes a first step in addressing this question by borrowing the concept of T-randomness, 0 <= T <= 1, from algorithmic information theory. Roughly speaking, the value T fixes the entropy rate of the considered schedules. For instance, the case T = 1 corresponds, in a specific sense, to schedules in which the pairs of interacting agents are chosen independently and uniformly (perfect randomness). The holy grail question can then be precisely stated as determining the optimal entropy rate to solve a given problem. We first show that perfect randomness is never required. Precisely, if a finite-state algorithm solves a problem with 1-randomness, then this algorithm still solves the same problem with T-randomness for some T < 1. Second, we illustrate how to compute bounds on the optimal entropy rate of a specific problem, namely the leader election problem.
Cite as
Joffroy Beauquier, Peva Blanchard, Janna Burman, and Rachid Guerraoui. The Benefits of Entropy in Population Protocols. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 21:1-21:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{beauquier_et_al:LIPIcs.OPODIS.2015.21,
author = {Beauquier, Joffroy and Blanchard, Peva and Burman, Janna and Guerraoui, Rachid},
title = {{The Benefits of Entropy in Population Protocols}},
booktitle = {19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
pages = {21:1--21:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-98-9},
ISSN = {1868-8969},
year = {2016},
volume = {46},
editor = {Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.21},
URN = {urn:nbn:de:0030-drops-66128},
doi = {10.4230/LIPIcs.OPODIS.2015.21},
annote = {Keywords: algorithmic randomness, entropy, leader election, distributed computing, scheduler, population protocols}
}
Document
Byzantine Agreement with Median Validity
Abstract
We introduce a stronger validity property for the byzantine agreement problem with orderable initial values: The median validity property. In particular, the decision value is required to be close to the median of the initial values of the non-byzantine nodes. The proximity to the median scales with the desired level of fault-tolerance: If no fault-tolerance is required, algorithms have to decide for the true median. If the number of failures is maximal, algorithms must still decide on a value within the range of the input values of the non-byzantine nodes. We present a deterministic algorithm satisfying this property for n >= 3t+1 within t+1 phases, where t is the maximum number of byzantine nodes and n is the total number of nodes.
Cite as
David Stolz and Roger Wattenhofer. Byzantine Agreement with Median Validity. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 22:1-22:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{stolz_et_al:LIPIcs.OPODIS.2015.22,
author = {Stolz, David and Wattenhofer, Roger},
title = {{Byzantine Agreement with Median Validity}},
booktitle = {19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
pages = {22:1--22:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-98-9},
ISSN = {1868-8969},
year = {2016},
volume = {46},
editor = {Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.22},
URN = {urn:nbn:de:0030-drops-65911},
doi = {10.4230/LIPIcs.OPODIS.2015.22},
annote = {Keywords: Reliability, fault-tolerance, median, consensus}
}
Document
Ensuring Average Recovery with Adversarial Scheduler
Abstract
In this paper, we focus on revising a given program so that the average recovery time in the presence of an adversarial scheduler is bounded by a given threshold lambda. Specifically, we consider the scenario where the fault (or other unexpected action) perturbs the program to a state that is outside its set of legitimate states. Starting from this state, the program executes its actions/transitions to recover to legitimate states. However, the adversarial scheduler can force the program to reach one illegitimate state that requires a longer recovery time.
To ensure that the average recovery time is less than lambda, we need to remove certain transitions/behaviors. We show that achieving this average response time while removing minimum transitions is NP-hard. In other words, there is a tradeoff between the time taken to synthesize the program and the transitions preserved to reduce the average convergence time. We present six different heuristics and evaluate this tradeoff with case studies. Finally, we note that the average convergence time considered here requires formalization of hyperproperties. Hence, this work also demonstrates feasibility of adding (certain) hyperproperties to an existing program.
Cite as
Jingshu Chen, Mohammad Roohitavaf, and Sandeep S. Kulkarni. Ensuring Average Recovery with Adversarial Scheduler. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 23:1-23:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{chen_et_al:LIPIcs.OPODIS.2015.23,
author = {Chen, Jingshu and Roohitavaf, Mohammad and Kulkarni, Sandeep S.},
title = {{Ensuring Average Recovery with Adversarial Scheduler}},
booktitle = {19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
pages = {23:1--23:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-98-9},
ISSN = {1868-8969},
year = {2016},
volume = {46},
editor = {Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.23},
URN = {urn:nbn:de:0030-drops-65907},
doi = {10.4230/LIPIcs.OPODIS.2015.23},
annote = {Keywords: Average Recovery Time, Hyper-liveness, Program Repair}
}
Document
Towards Establishing Monotonic Searchability in Self-Stabilizing Data Structures
Abstract
Distributed applications are commonly based on overlay networks interconnecting their sites so that they can exchange information. For these overlay networks to preserve their functionality, they should be able to recover from various problems like membership changes or faults. Various self-stabilizing overlay networks have already been proposed in recent years, which have the advantage of being able to recover from any illegal state, but none of these networks can give any guarantees on its functionality while the recovery process is going on. We initiate research on overlay networks that are not only self-stabilizing but that also ensure that searchability is maintained while the recovery process is going on, as long as there are no corrupted messages in the system. More precisely, once a search message from node u to another node v is successfully delivered, all future search messages from u to v succeed as well. We call this property monotonic searchability. We show that in general it is impossible to provide monotonic searchability if corrupted messages are present in the system, which justifies the restriction to system states without corrupted messages. Furthermore, we provide a self-stabilizing protocol for the line for which we can also show monotonic searchability. It turns out that even for the line it is non-trivial to achieve this property. Additionally, we extend our protocol to deal with node departures in terms of the Finite Departure Problem of Foreback et al. (SSS 2014). This makes our protocol even capable of handling node dynamics.
Cite as
Christian Scheideler, Alexander Setzer, and Thim Strothmann. Towards Establishing Monotonic Searchability in Self-Stabilizing Data Structures. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 24:1-24:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{scheideler_et_al:LIPIcs.OPODIS.2015.24,
author = {Scheideler, Christian and Setzer, Alexander and Strothmann, Thim},
title = {{Towards Establishing Monotonic Searchability in Self-Stabilizing Data Structures}},
booktitle = {19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
pages = {24:1--24:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-98-9},
ISSN = {1868-8969},
year = {2016},
volume = {46},
editor = {Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.24},
URN = {urn:nbn:de:0030-drops-66135},
doi = {10.4230/LIPIcs.OPODIS.2015.24},
annote = {Keywords: Topological Self-Stabilization, Monotonic Searchability, Node Departures}
}
Document
QuickLex: A Fast Algorithm for Consistent Global States Enumeration of Distributed Computations
Abstract
Verifying the correctness of executions of concurrent and distributed programs is difficult because they show nondeterministic behavior due to different process scheduling order. Predicate detection can alleviate this problem by predicting whether the user-specified condition (predicate) could have become true in any global state of the given concurrent or distributed computation. The method is predictive because it generates inferred global states from the observed execution path and then checks if those global states satisfy the predicate. An important part of the predicate detection method is global states enumeration, which generates the consistent global states, including the inferred ones, of the given computation. Cooper and Marzullo gave the first enumeration algorithm based on a breadth first strategy (BFS). Later, many algorithms have been proposed to improve the space and time complexity. Among the existing algorithms, the Tree algorithm due to Jegou et al. has the smallest time complexity and requires O(|P|) space, which is linear to the size of the computation P. In this paper, we present a fast algorithm, QuickLex, to enumerate global states in the lexical order. QuickLex requires much smaller space than O(|P|). From our experiments, the Tree algorithm requires 2-10 times more memory space than QuickLex. Moreover, QuickLex is 4 times faster than Tree even though the asymptotic time complexity of QuickLex is higher than that of Tree. The reason is that the worst case time complexity of QuickLex happens only in computations that are not common in practice. Moreover, Tree is built on linked-lists and QuickLex can be implemented using integer arrays. In comparison with the existing lexical algorithm (Lex), QuickLex is 7 times faster and uses almost the same amount of memory as Lex. Finally, we implement a parallel-and-online predicate detector for concurrent programs using QuickLex, which can detect data races and violation of invariants in the programs.
Cite as
Yen-Jung Chang and Vijay K. Garg. QuickLex: A Fast Algorithm for Consistent Global States Enumeration of Distributed Computations. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 25:1-25:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{chang_et_al:LIPIcs.OPODIS.2015.25,
author = {Chang, Yen-Jung and Garg, Vijay K.},
title = {{QuickLex: A Fast Algorithm for Consistent Global States Enumeration of Distributed Computations}},
booktitle = {19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
pages = {25:1--25:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-98-9},
ISSN = {1868-8969},
year = {2016},
volume = {46},
editor = {Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.25},
URN = {urn:nbn:de:0030-drops-66142},
doi = {10.4230/LIPIcs.OPODIS.2015.25},
annote = {Keywords: consistent global state, algorithm, computation}
}
Document
The Synchronization Power of Atomic Bitwise Operations
Abstract
In a distributed system, processes must reach a certain level of synchronization to solve a common problem. The strongest form of synchronization can be reached through consensus: all the processes must agree on a common value that has been proposed by one of them. Consensus is universal in shared memory systems: any type of shared object can be implemented using it. Unfortunately, consensus is impossible to solve using only shared registers when processes can crash.
To circumvent this impossibility, one can use stronger objects, for example Test&Set or Compare&Swap. The synchronization power of these objects can be measured using the concept of Consensus Number: the maximum number of processes for which they can solve consensus in a crash-prone system. Bitwise AND, OR and XOR operations are very widely used, but have received little attention in the distributed setting. Because bitwise operations are available in most modern processors, they can constitute a valuable tool for synchronization in distributed systems. It is then natural to consider the level of synchronization that these operations can achieve.
This paper introduces shared AND/OR and AND/OR/XOR registers. A shared AND/OR register consists of an array of x bits and offers three atomic operations: AND and OR operations, which take an array of x bits as parameter and change the state of the register by applying the corresponding bitwise operation, and a read operation which returns the content of the array. A shared AND/OR/XOR register additionally offers a XOR operation.
We show that shared AND/OR registers of x bits have consensus number lfloor (x+1)/2 rfloor, by presenting an algorithm that solves consensus using these registers, and by proving that consensus cannot be solved for n processes using AND/OR registers that have strictly less than 2n-1 bits. We then show that shared AND/OR/XOR registers of x bits have consensus number x using a similar technique.
Cite as
Damien Imbs. The Synchronization Power of Atomic Bitwise Operations. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 26:1-26:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{imbs:LIPIcs.OPODIS.2015.26,
author = {Imbs, Damien},
title = {{The Synchronization Power of Atomic Bitwise Operations}},
booktitle = {19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
pages = {26:1--26:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-98-9},
ISSN = {1868-8969},
year = {2016},
volume = {46},
editor = {Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.26},
URN = {urn:nbn:de:0030-drops-66151},
doi = {10.4230/LIPIcs.OPODIS.2015.26},
annote = {Keywords: Asynchronous systems, Binary operations, Consensus, Consensus number, Read/write shared memory, Shared objects, Synchronization, Wait-freedom}
}
Document
Wait-Free Concurrent Graph Objects with Dynamic Traversals
Abstract
Graphs are versatile data structures that allow the implementation of a variety of applications, such as computer-aided design and manufacturing, video gaming, or scientific simulations. However, although data structures such as queues, stacks, and trees have been widely studied and implemented in the concurrent context, multi-process applications that rely on graphs still largely use a sequential implementation where accesses are synchronized through the use of global locks or partitioning, thus imposing serious performance bottlenecks. In this paper we introduce an innovative concurrent graph model that provides addition and removal of any edge of the graph, as well as atomic traversals of a part (or the entirety) of the graph. We further present Dense, a concurrent graph implementation that aims at mitigating the two aforementioned implementation drawbacks. Dense achieves wait-freedom by relying on helping and provides the inbuilt capability of performing a partial snapshot on a dynamically determined subset of the graph.
Cite as
Nikolaos D. Kallimanis and Eleni Kanellou. Wait-Free Concurrent Graph Objects with Dynamic Traversals. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 27:1-27:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{kallimanis_et_al:LIPIcs.OPODIS.2015.27,
author = {Kallimanis, Nikolaos D. and Kanellou, Eleni},
title = {{Wait-Free Concurrent Graph Objects with Dynamic Traversals}},
booktitle = {19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
pages = {27:1--27:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-98-9},
ISSN = {1868-8969},
year = {2016},
volume = {46},
editor = {Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.27},
URN = {urn:nbn:de:0030-drops-66164},
doi = {10.4230/LIPIcs.OPODIS.2015.27},
annote = {Keywords: graph, shared memory, concurrent data structure, snapshot}
}
Document
A Faster Counting Protocol for Anonymous Dynamic Networks
Abstract
We study the problem of counting the number of nodes in a slotted-time communication network, under the challenging assumption that nodes do not have identifiers and the network topology changes frequently. That is, for each time slot links among nodes can change arbitrarily provided that the network is always connected.
This network model has been motivated by the ongoing development of new communication technologies that enable the deployment of a massive number of devices with highly dynamic connectivity patterns. Tolerating dynamic topologies is clearly crucial in face of mobility and unreliable communication. Current communication networks do have node identifiers though. Nevertheless, in future massive networks, it might be suitable to avoid nodes IDs to facilitate mass production. Consequently, knowing what is the cost of anonymity is of paramount importance to understand what is feasible or not for future generations of Dynamic Networks.
Counting is a fundamental task in distributed computing since knowing the size of the system often facilitates the desing of solutions for more complex problems. Also, the size of the system is usually used to decide termination in distributed algorithms. Currently, the best upper bound proved on the running time to compute the exact network size is double-exponential. However, only linear complexity lower bounds are known, leaving open the question of whether efficient Counting protocols for Anonymous Dynamic Networks exist or not.
In this paper we make a significant step towards answering this question by presenting a distributed Counting protocol for Anonymous Dynamic Networks which has exponential time complexity. This algorithm, which we call Incremental Counting, ensures that eventually every node knows the exact size of the system and stops executing the protocol. Previous Counting protocols have either double-exponential time complexity, or they are exponential but do not terminate, or terminate but do not provide running-time guarantees, or guarantee only an exponential upper bound on the network size. Other protocols are heuristic and do not guarantee the correct count.
Cite as
Alessia Milani and Miguel A. Mosteiro. A Faster Counting Protocol for Anonymous Dynamic Networks. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 28:1-28:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{milani_et_al:LIPIcs.OPODIS.2015.28,
author = {Milani, Alessia and Mosteiro, Miguel A.},
title = {{A Faster Counting Protocol for Anonymous Dynamic Networks}},
booktitle = {19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
pages = {28:1--28:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-98-9},
ISSN = {1868-8969},
year = {2016},
volume = {46},
editor = {Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.28},
URN = {urn:nbn:de:0030-drops-66179},
doi = {10.4230/LIPIcs.OPODIS.2015.28},
annote = {Keywords: Anonymous Dynamic Networks, Counting, Time-varying Graphs}
}
Document
ActiveMonitor: Asynchronous Monitor Framework for Scalability and Multi-Object Synchronization
Abstract
Monitor objects are used extensively for thread-safety and synchronization in shared memory parallel programs. They provide ease of use, and enable straightforward correctness analysis. However, they inhibit parallelism by enforcing serial executions of critical sections, and thus the performance of parallel programs with monitors scales poorly with number of processes. Their current design and implementation is also ill-suited for thread synchronization across multiple thread-safe objects. We present ActiveMonitor - a framework that allows multi-object synchronization without global locks, and improves parallelism by exploiting asynchronous execution of critical sections. We evaluate the performance of Java based implementation of ActiveMonitor on micro-benchmarks involving light and heavy critical sections, as well as on single-source-shortest-path problem in directed graphs. Our results show that on most of these problems, ActiveMonitor based programs outperform programs implemented using Java's reentrant-lock and condition constructs.
Cite as
Wei-Lun Hung, Himanshu Chauhan, and Vijay K. Garg. ActiveMonitor: Asynchronous Monitor Framework for Scalability and Multi-Object Synchronization. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 29:1-29:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{hung_et_al:LIPIcs.OPODIS.2015.29,
author = {Hung, Wei-Lun and Chauhan, Himanshu and Garg, Vijay K.},
title = {{ActiveMonitor: Asynchronous Monitor Framework for Scalability and Multi-Object Synchronization}},
booktitle = {19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
pages = {29:1--29:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-98-9},
ISSN = {1868-8969},
year = {2016},
volume = {46},
editor = {Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.29},
URN = {urn:nbn:de:0030-drops-66188},
doi = {10.4230/LIPIcs.OPODIS.2015.29},
annote = {Keywords: concurrent/parallel programming, monitors, concurrency}
}
Document
Communicating with Beeps
Abstract
The beep model is a very weak communications model in which devices in a network can communicate only via beeps and silence. As a result of its weak assumptions, it has broad applicability to many different implementations of communications networks. This comes at the cost of a restrictive environment for algorithm design.
Despite being only recently introduced, the beep model has received considerable attention, in part due to its relationship with other communication models such as that of ad-hoc radio networks. However, there has been no definitive published result for several fundamental tasks in the model. We aim to rectify this with our paper.
We present algorithms for the tasks of broadcast, gossiping, and multi-broadcast, and also, as intermediary results, means of depth-first search and diameter estimation. Our O(D+log(M)-time algorithm for broadcasting is a simple formalization of a concept known as beep waves, and is asymptotically optimal. We give an O(n*log(L))-time depth-first search procedure, and show how this can be used as the basis for an O(n*log(L*M))-time gossiping algorithm. Finally, we approach the more general problem of multi-broadcast. We differentiate between two variants of this problem: one where nodes must know the origin of all source messages, and another where this information is not required. In the first instance we achieve an algorithm running in time O(k*log((L*M)/k)+D*log(L)), and in the second an O(k*log(M/k)+D*log(L))-time algorithm (or O(M+D*log(L)) when M <= k). We then give corresponding lower bounds: Omega(k*log((L*M)/k)+D) in the case where nodes must know message origins, and Omega(k*log(M/k)+D) and Omega(M+D) in the other case, for M > k and M <= k respectively. These lower bounds demonstrate that our algorithms are optimal except for the D*log(L) additive term. In these running-time expressions, n represents network size, D network diameter, L range of node labels, M range of source messages, and k number of sources.
Our algorithms are all explicit, deterministic, and practical, and give efficient means of communication while making arguably the minimum possible assumptions about the network.
Cite as
Artur Czumaj and Peter Davies. Communicating with Beeps. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 30:1-30:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{czumaj_et_al:LIPIcs.OPODIS.2015.30,
author = {Czumaj, Artur and Davies, Peter},
title = {{Communicating with Beeps}},
booktitle = {19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
pages = {30:1--30:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-98-9},
ISSN = {1868-8969},
year = {2016},
volume = {46},
editor = {Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.30},
URN = {urn:nbn:de:0030-drops-66195},
doi = {10.4230/LIPIcs.OPODIS.2015.30},
annote = {Keywords: Beep model, Communication networks, Broadcasting, Gossiping, Leader election}
}
Document
Nontrivial and Universal Helping for Wait-Free Queues and Stacks
Abstract
This paper studies two approaches to formalize helping in wait-free implementations of shared objects. The first approach is based on operation valency, and it allows us to make the important distinction between trivial and nontrivial helping. We show that a wait-free implementation of a queue from common2 objects (e.g., Test&Set) requires nontrivial helping. In contrast, there is a wait-free implementation of a stack from Common2 objects with only trivial helping. This separation might shed light on the difficulty of implementing a queue from Common2 objects.
The other approach formalizes the helping mechanism employed by Herlihy's universal wait-free construction and is based on having an operation by one process restrict the possible linearizations of operations by other processes. We show that objects possessing such universal helping can be used to solve consensus.
Cite as
Hagit Attiya, Armando Castaneda, and Danny Hendler. Nontrivial and Universal Helping for Wait-Free Queues and Stacks. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 31:1-31:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{attiya_et_al:LIPIcs.OPODIS.2015.31,
author = {Attiya, Hagit and Castaneda, Armando and Hendler, Danny},
title = {{Nontrivial and Universal Helping for Wait-Free Queues and Stacks}},
booktitle = {19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
pages = {31:1--31:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-98-9},
ISSN = {1868-8969},
year = {2016},
volume = {46},
editor = {Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.31},
URN = {urn:nbn:de:0030-drops-66201},
doi = {10.4230/LIPIcs.OPODIS.2015.31},
annote = {Keywords: helping, wait-free, nonblocking, queues, stacks, common2}
}
Document
Generic Proofs of Consensus Numbers for Abstract Data Types
Abstract
The power of shared data types to solve consensus in asynchronous wait-free systems is a fundamental question in distributed computing, but is largely considered only for specific data types. We consider general classes of abstract shared data types, and classify types of operations on those data types by the knowledge about past operations that processes can extract from the state of the shared object. We prove upper and lower bounds on the number of processes which can use data types in these classes to solve consensus. Our results generalize the consensus numbers known for a wide variety of specific shared data types, such as compare-and-swap, augmented queues and stacks, registers, and cyclic queues. Further, since the classification is based directly on the semantics of operations, one can use the bounds we present to determine the consensus number of a new data type from its specification.
We show that, using sets of operations which can detect the first change to the shared object state, or even one at a fixed distance from the beginning of the execution, any number of processes can solve consensus. However, if instead of one of the first changes, operations can only detect one of the most recent changes, then fewer processes can solve consensus. In general, if each operation can either change shared state or read it, but not both, then the number of processes which can solve consensus is limited by the number of consecutive recent operations which can be viewed by a single operation. Allowing operations that both change and read the shared state can allow consensus algorithms with more processes, but if the operations can only see one change a fixed number of operations in the past, we upper bound the number of processes which can solve consensus with a small constant.
Cite as
Edward Talmage and Jennifer Welch. Generic Proofs of Consensus Numbers for Abstract Data Types. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 32:1-32:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{talmage_et_al:LIPIcs.OPODIS.2015.32,
author = {Talmage, Edward and Welch, Jennifer},
title = {{Generic Proofs of Consensus Numbers for Abstract Data Types}},
booktitle = {19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
pages = {32:1--32:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-98-9},
ISSN = {1868-8969},
year = {2016},
volume = {46},
editor = {Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.32},
URN = {urn:nbn:de:0030-drops-66217},
doi = {10.4230/LIPIcs.OPODIS.2015.32},
annote = {Keywords: Distributed Data Structures, Abstract Data Types, Consensus Numbers, Distributed Computing, Crash Failures}
}
Document
Non Trivial Computations in Anonymous Dynamic Networks
Abstract
In this paper we consider a static set of anonymous processes, i.e., they do not have distinguished IDs, that communicate with neighbors using a local broadcast primitive. The communication graph changes at each computational round with the restriction of being always connected, i.e., the network topology guarantees 1-interval connectivity. In such setting non trivial computations, i.e., answering to a predicate like "there exists at least one process with initial input a?", are impossible. In a recent work, it has been conjectured that the impossibility holds even if a distinguished leader process is available within the computation. In this paper we prove that the conjecture is false. We show this result by implementing a deterministic leader-based terminating counting algorithm. In order to build our counting algorithm we first develop a counting technique that is time optimal on a family of dynamic graphs where each process has a fixed distance h from the leader and such distance does not change along rounds. Using this technique we build an algorithm that counts in anonymous 1-interval connected networks.
Cite as
Giuseppe Di Luna and Roberto Baldoni. Non Trivial Computations in Anonymous Dynamic Networks. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 33:1-33:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{diluna_et_al:LIPIcs.OPODIS.2015.33,
author = {Di Luna, Giuseppe and Baldoni, Roberto},
title = {{Non Trivial Computations in Anonymous Dynamic Networks}},
booktitle = {19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
pages = {33:1--33:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-98-9},
ISSN = {1868-8969},
year = {2016},
volume = {46},
editor = {Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.33},
URN = {urn:nbn:de:0030-drops-66761},
doi = {10.4230/LIPIcs.OPODIS.2015.33},
annote = {Keywords: Distributed System, Anonymous Networks, Dynamic Networks}
}
Document
Analysis of Bounds on Hybrid Vector Clocks
Abstract
Hybrid vector clocks (HVC) implement vector clocks (VC) in a space-efficient manner by exploiting the availability of loosely-synchronized physical clocks at each node. In this paper, we develop a model for determining the bounds on the size of HVC. Our model uses four parameters, epsilon: uncertainty window, delta: minimum message delay, alpha: communication frequency and n: number of nodes in the system. We derive the size of HVC in terms of a differential equation, and show that the size predicted by our model is almost identical to the results obtained by simulation. We also identify closed form solutions that provide tight lower and upper bounds for useful special cases.
Our model and simulations show the HVC size is a sigmoid function with respect to increasing epsilon; it has a slow start but it grows exponentially after a phase transition. We present equations to identify the phase transition point and show that for many practical applications and deployment environments, the size of HVC remains only as a couple entries and substantially less than n. We also find that, in a model with random unicast message transmissions, increasing n actually helps for reducing HVC size.
Cite as
Sorrachai Yingchareonthawornchai, Sandeep S. Kulkarni, and Murat Demirbas. Analysis of Bounds on Hybrid Vector Clocks. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 34:1-34:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{yingchareonthawornchai_et_al:LIPIcs.OPODIS.2015.34,
author = {Yingchareonthawornchai, Sorrachai and Kulkarni, Sandeep S. and Demirbas, Murat},
title = {{Analysis of Bounds on Hybrid Vector Clocks}},
booktitle = {19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
pages = {34:1--34:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-98-9},
ISSN = {1868-8969},
year = {2016},
volume = {46},
editor = {Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.34},
URN = {urn:nbn:de:0030-drops-66771},
doi = {10.4230/LIPIcs.OPODIS.2015.34},
annote = {Keywords: Vector Clocks, Physical Clocks, Large Scale Systems}
}
Document
Non-Blocking Doubly-Linked Lists with Good Amortized Complexity
Abstract
We present a new non-blocking doubly-linked list implementation for an asynchronous shared-memory system. It is the first such implementation for which an upper bound on amortized time complexity has been proved. In our implementation, operations access the list via cursors. Each cursor is located at an item in the list and is local to a process. In our implementation, cursors can be used to traverse and update the list, even as concurrent operations modify the list. The implementation supports two update operations, insertBefore and delete, and two move operations, moveRight and moveLeft. An insertBefore(c, x) operation inserts an item x into the list immediately before the cursor c's location. A delete(c) operation removes the item at the cursor c's location and sets the cursor to the next item in the list. The move operations move the cursor one position to the right or left. Update operations use single-word Compare&Swap instructions. Move operations only read shared memory and never change the state of the data structure. If all update operations modify different parts of the list, they run completely concurrently. A cursor is active if it is initialized, but not yet removed from the process's set of cursors. Let c.(op) be the maximum number of active cursors at any one time during the operation op. The amortized step complexity is O(c.(op)) for each update op and O(1) for each move. We provide a detailed correctness proof and amortized analysis of our implementation.
Cite as
Niloufar Shafiei. Non-Blocking Doubly-Linked Lists with Good Amortized Complexity. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 35:1-35:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{shafiei:LIPIcs.OPODIS.2015.35,
author = {Shafiei, Niloufar},
title = {{Non-Blocking Doubly-Linked Lists with Good Amortized Complexity}},
booktitle = {19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
pages = {35:1--35:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-98-9},
ISSN = {1868-8969},
year = {2016},
volume = {46},
editor = {Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.35},
URN = {urn:nbn:de:0030-drops-66787},
doi = {10.4230/LIPIcs.OPODIS.2015.35},
annote = {Keywords: non-blocking data structure, doubly-linked list, shared memory, amortized complexity, cursor}
}
Document
Poly-Logarithmic Adaptive Algorithms Require Unconditional Primitives
Abstract
This paper studies the step complexity of adaptive algorithms using primitives stronger than reads and writes. We first consider unconditional primitives, like fetch&inc, which modify the value of the register to which they are applied, regardless of its current value. Unconditional primitives admit snapshot algorithms with O(log(k)) step complexity, where k is the total or the point contention. These algorithms combine a renaming algorithm with a mechanism for propagating values so they can be quickly collected.
When only conditional primitives, e.g., compare&swap or LL/SC, are used (in addition to reads and writes), we show that any collect algorithm must perform Omega(k) steps, in an execution with total contention k in O(log(log(n))). The lower bound applies for snapshot and renaming, both one-shot and long-lived. Note that there are snapshot algorithms whose step complexity is polylogarithmic in n using only reads and writes, but there are no adaptive algorithms whose step complexity is polylogarithmic in the contention, even when compare&swap and LL/SC are used.
Cite as
Hagit Attiya and Arie Fouren. Poly-Logarithmic Adaptive Algorithms Require Unconditional Primitives. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 36:1-36:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{attiya_et_al:LIPIcs.OPODIS.2015.36,
author = {Attiya, Hagit and Fouren, Arie},
title = {{Poly-Logarithmic Adaptive Algorithms Require Unconditional Primitives}},
booktitle = {19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
pages = {36:1--36:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-98-9},
ISSN = {1868-8969},
year = {2016},
volume = {46},
editor = {Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.36},
URN = {urn:nbn:de:0030-drops-66793},
doi = {10.4230/LIPIcs.OPODIS.2015.36},
annote = {Keywords: collect, atomic snapshot, renaming, fetch\&inc, compare\&swap}
}