Volume
LIPIcs, Volume 91
31st International Symposium on Distributed Computing (DISC 2017)
-
Part of:
Series:
Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Distributed Computing (DISC)
Event
DISC 2017, October 16-20, 2017, Vienna, AustriaEditor
Publication Details
- published at: 2017-10-12
- Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
- ISBN: 978-3-95977-053-8
- DBLP: db/conf/wdag/disc2017
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 91, DISC'17, Complete Volume
Abstract
LIPIcs, Volume 91, DISC'17, Complete Volume
Cite as
31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@Proceedings{richa:LIPIcs.DISC.2017,
title = {{LIPIcs, Volume 91, DISC'17, Complete Volume}},
booktitle = {31st International Symposium on Distributed Computing (DISC 2017)},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-053-8},
ISSN = {1868-8969},
year = {2017},
volume = {91},
editor = {Richa, Andr\'{e}a},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017},
URN = {urn:nbn:de:0030-drops-80247},
doi = {10.4230/LIPIcs.DISC.2017},
annote = {Keywords: Computer-Communication Networks, Distributed Systems, Concurrent Programming, Data Structures, Theory of Computation, Models of Computation, Modes of Computation}
}
Document
Front Matter
Front Matter, Table of Contents, Preface, Symposium Organization, Awards
Abstract
Front Matter, Table of Contents, Preface, Symposium Organization, 2017 Edsger W. Dijkstra Prize in Distributed Computing, and 2017 Principles of Distributed Computing Doctoral Dissertation Award.
Cite as
31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 0:i-0:xviii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{richa:LIPIcs.DISC.2017.0,
author = {Richa, Andr\'{e}a},
title = {{Front Matter, Table of Contents, Preface, Symposium Organization, Awards}},
booktitle = {31st International Symposium on Distributed Computing (DISC 2017)},
pages = {0:i--0:xviii},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-053-8},
ISSN = {1868-8969},
year = {2017},
volume = {91},
editor = {Richa, Andr\'{e}a},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.0},
URN = {urn:nbn:de:0030-drops-79629},
doi = {10.4230/LIPIcs.DISC.2017.0},
annote = {Keywords: Front Matter, Table of Contents, Preface, Symposium Organization, Edsger W. Dijkstra Prize in Distributed Computing, Principles of Distributed Computi}
}
Document
Keynote Talk
Blockchain Consensus Protocols in the Wild (Keynote Talk)
Abstract
A blockchain is a distributed ledger for recording transactions, maintained by many nodes without central authority through a distributed cryptographic protocol. All nodes validate the information to be appended to the blockchain, and a consensus protocol ensures that the nodes agree on a unique order in which entries are appended. Consensus protocols for tolerating Byzantine faults have received renewed attention because they also address blockchain systems. This work discusses the process of assessing and gaining confidence in the resilience of a consensus protocols exposed to faults and adversarial nodes. We advocate to follow the established practice in cryptography and computer security, relying on public reviews, detailed models, and formal proofs; the designers of several practical systems appear to be unaware of this. Moreover, we review the consensus protocols in some prominent permissioned blockchain platforms with respect to their fault models and resilience against attacks.
Cite as
Christian Cachin and Marko Vukolic. Blockchain Consensus Protocols in the Wild (Keynote Talk). In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 1:1-1:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{cachin_et_al:LIPIcs.DISC.2017.1,
author = {Cachin, Christian and Vukolic, Marko},
title = {{Blockchain Consensus Protocols in the Wild}},
booktitle = {31st International Symposium on Distributed Computing (DISC 2017)},
pages = {1:1--1:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-053-8},
ISSN = {1868-8969},
year = {2017},
volume = {91},
editor = {Richa, Andr\'{e}a},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.1},
URN = {urn:nbn:de:0030-drops-80160},
doi = {10.4230/LIPIcs.DISC.2017.1},
annote = {Keywords: Permissioned blockchains, consensus, Byzantine fault-tolerance, snake oil, protocol analysis}
}
Document
Keynote Talk
Recommenders: from the Lab to the Wild (Keynote Talk)
Abstract
Recommenders are ubiquitous on the Internet today: they tell you which book to read, which movie you should watch, predict your next holiday destination, give you advices on restaurants and hotels, they are even responsible for the posts that you see on your favorite social media and potentially greatly influence your friendship on social networks.
While many approaches exist, collaborative filtering is one of the most popular approaches to build online recommenders that provide users with content that matches their interest. Interestingly, the very notion of users can be general and span actual humans or software applications. Recommenders come with many challenges beyond the quality of the recommendations. One of the most prominent ones is their ability to scale to a large number of users and a growing volume of data to provide real-time recommendations introducing many system challenges. Another challenge is related to privacy awareness: while recommenders rely on the very fact that users give away information about themselves, this potentially raises some privacy concerns.
In this talk, I will focus on the challenges associated to building efficient, scalable and privacy-aware recommenders.
Cite as
Anne-Marie Kermarrec. Recommenders: from the Lab to the Wild (Keynote Talk). In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{kermarrec:LIPIcs.DISC.2017.2,
author = {Kermarrec, Anne-Marie},
title = {{Recommenders: from the Lab to the Wild}},
booktitle = {31st International Symposium on Distributed Computing (DISC 2017)},
pages = {2:1--2:1},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-053-8},
ISSN = {1868-8969},
year = {2017},
volume = {91},
editor = {Richa, Andr\'{e}a},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.2},
URN = {urn:nbn:de:0030-drops-79652},
doi = {10.4230/LIPIcs.DISC.2017.2},
annote = {Keywords: Recommenders, Collaborative filtering, Distributed systems}
}
Document
Keynote Talk
Phase Transitions and Emergent Phenomena in Random Structures and Algorithms (Keynote Talk)
Abstract
Markov chain Monte Carlo methods have become ubiquitous across science and engineering to model dynamics and explore large sets of configurations. The idea is to perform a random walk among the configurations so that even though only a very small part of the space is visited, samples will be drawn from a desirable distribution. Over the last 20 years there have been tremendous advances in the design and analysis of efficient sampling algorithms for this purpose, building on insights from statistical physics. One of the striking discoveries has been the realization that many natural Markov chains undergo phase transitions, whereby they change from being efficient to inefficient as some parameter of the system is modified, also revealing interesting properties of the underlying random structures.
We will explore how phase transitions can provide valuable insights in three settings. First, they allow us to understand the limitations of certain classes of sampling algorithms, potentially leading to faster alternative approaches. Second, they reveal statistical properties of stationary distributions, giving insight into various interacting models. Example include colloids, or binary mixtures of molecules, segregation models, where individuals are more likely move when they are unhappy with their local demographics, and interacting particle systems from statistical physics. Last, they predict emergent phenomena that can be harnessed for the design of distributed algorithms for certain asynchronous models of programmable active matter. We will see how these three research threads are closely interrelated and inform one another.
The talk will take a random walk through some of the results included in the references.
Cite as
Dana Randall. Phase Transitions and Emergent Phenomena in Random Structures and Algorithms (Keynote Talk). In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 3:1-3:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{randall:LIPIcs.DISC.2017.3,
author = {Randall, Dana},
title = {{Phase Transitions and Emergent Phenomena in Random Structures and Algorithms}},
booktitle = {31st International Symposium on Distributed Computing (DISC 2017)},
pages = {3:1--3:2},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-053-8},
ISSN = {1868-8969},
year = {2017},
volume = {91},
editor = {Richa, Andr\'{e}a},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.3},
URN = {urn:nbn:de:0030-drops-80212},
doi = {10.4230/LIPIcs.DISC.2017.3},
annote = {Keywords: Markov chains, phase transitions, sampling, emergent phenomena, programmable matter}
}
Document
Reuse, Don't Recycle: Transforming Lock-Free Algorithms That Throw Away Descriptors
Abstract
In many lock-free algorithms, threads help one another, and each operation creates a descriptor that describes how other threads should help it. Allocating and reclaiming descriptors introduces significant space and time overhead. We introduce the first descriptor abstract data type (ADT), which captures the usage of descriptors by lock-free algorithms. We then develop a weak descriptor ADT which has weaker semantics, but can be implemented significantly more efficiently. We show how a large class of lock-free algorithms can be transformed to use weak descriptors, and demonstrate our technique by transforming several algorithms, including the leading k-compare-and-swap (k-CAS) algorithm. The original k-CAS algorithm allocates at least k+1 new descriptors per k-CAS. In contrast, our implementation allocates two descriptors per process, and each process simply reuses its two descriptors. Experiments on a variety of workloads show significant performance improvements over implementations that reclaim descriptors, and reductions of up to three orders of magnitude in peak memory usage.
Cite as
Maya Arbel-Raviv and Trevor Brown. Reuse, Don't Recycle: Transforming Lock-Free Algorithms That Throw Away Descriptors. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 4:1-4:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{arbelraviv_et_al:LIPIcs.DISC.2017.4,
author = {Arbel-Raviv, Maya and Brown, Trevor},
title = {{Reuse, Don't Recycle: Transforming Lock-Free Algorithms That Throw Away Descriptors}},
booktitle = {31st International Symposium on Distributed Computing (DISC 2017)},
pages = {4:1--4:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-053-8},
ISSN = {1868-8969},
year = {2017},
volume = {91},
editor = {Richa, Andr\'{e}a},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.4},
URN = {urn:nbn:de:0030-drops-80092},
doi = {10.4230/LIPIcs.DISC.2017.4},
annote = {Keywords: Concurrency, data structures, lock-free, synchronization, descriptors}
}
Document
Demand-Aware Network Designs of Bounded Degree
Abstract
Traditionally, networks such as datacenter interconnects are designed to optimize worst-case performance under arbitrary traffic patterns. Such network designs can however be far from optimal when considering the actual workloads and traffic patterns which they serve. This insight led to the development of demand-aware datacenter interconnects which can be reconfigured depending on the workload.
Motivated by these trends, this paper initiates the algorithmic study of demand-aware networks (DANs), and in particular the design of bounded-degree networks. The inputs to the network design problem are a discrete communication request distribution, D, defined over communicating pairs from the node set V, and a bound, d, on the maximum degree. In turn, our objective is to design an (undirected) demand-aware network N = (V,E) of bounded-degree d, which provides short routing paths between frequently communicating nodes distributed across N. In particular, the designed network should minimize the expected path length on N (with respect to D), which is a basic measure of the efficiency of the network.
We show that this fundamental network design problem exhibits interesting connections to several classic combinatorial problems and to information theory. We derive a general lower bound based on the entropy of the communication pattern D, and present asymptotically optimal network-aware design algorithms for important distribution families, such as sparse distributions and distributions of locally bounded doubling dimensions.
Cite as
Chen Avin, Kaushik Mondal, and Stefan Schmid. Demand-Aware Network Designs of Bounded Degree. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 5:1-5:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{avin_et_al:LIPIcs.DISC.2017.5,
author = {Avin, Chen and Mondal, Kaushik and Schmid, Stefan},
title = {{Demand-Aware Network Designs of Bounded Degree}},
booktitle = {31st International Symposium on Distributed Computing (DISC 2017)},
pages = {5:1--5:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-053-8},
ISSN = {1868-8969},
year = {2017},
volume = {91},
editor = {Richa, Andr\'{e}a},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.5},
URN = {urn:nbn:de:0030-drops-80153},
doi = {10.4230/LIPIcs.DISC.2017.5},
annote = {Keywords: Network design, reconfigurable networks, datacenter topology, peer-topeer computing, entropy, sparse spanners}
}
Document
Certification of Compact Low-Stretch Routing Schemes
Abstract
On the one hand, the correctness of routing protocols in networks is an issue of utmost importance for guaranteeing the delivery of messages from any source to any target. On the other hand, a large collection of routing schemes have been proposed during the last two decades, with the objective of transmitting messages along short routes, while keeping the routing tables small. Regrettably, all these schemes share the property that an adversary may modify the content of the routing tables with the objective of, e.g., blocking the delivery of messages between some pairs of nodes, without being detected by any node.
In this paper, we present a simple certification mechanism which enables the nodes to locally detect any alteration of their routing tables. In particular, we show how to locally verify the stretch 3 routing scheme by Thorup and Zwick [SPAA 2001] by adding certificates of ~O(sqrt(n)) bits at each node in n-node networks, that is, by keeping the memory size of the same order of magnitude as the original routing tables. We also propose a new name-independent routing scheme using routing tables of size ~O(sqrt(n)) bits. This new routing scheme can be locally verified using certificates on ~O(sqrt(n)) bits. Its stretch is 3 if using handshaking, and 5 otherwise.
Cite as
Alkida Balliu and Pierre Fraigniaud. Certification of Compact Low-Stretch Routing Schemes. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 6:1-6:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{balliu_et_al:LIPIcs.DISC.2017.6,
author = {Balliu, Alkida and Fraigniaud, Pierre},
title = {{Certification of Compact Low-Stretch Routing Schemes}},
booktitle = {31st International Symposium on Distributed Computing (DISC 2017)},
pages = {6:1--6:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-053-8},
ISSN = {1868-8969},
year = {2017},
volume = {91},
editor = {Richa, Andr\'{e}a},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.6},
URN = {urn:nbn:de:0030-drops-79807},
doi = {10.4230/LIPIcs.DISC.2017.6},
annote = {Keywords: Distributed verification, compact routing, local computing}
}
Document
Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models
Abstract
We present a method for solving the shortest transshipment problem - also known as uncapacitated minimum cost flow - up to a multiplicative error of (1 + epsilon) in undirected graphs with non-negative integer edge weights using a tailored gradient descent algorithm. Our gradient descent algorithm takes epsilon^(-3) polylog(n) iterations, and in each iteration it needs to solve an instance of the transshipment problem up to a multiplicative error of polylog(n), where n is the number of nodes. In particular, this allows us to perform a single iteration by computing a solution on a sparse spanner of logarithmic stretch. Using a careful white-box analysis, we can further extend the method to finding approximate solutions for the single-source shortest paths (SSSP) problem. As a consequence, we improve prior work by obtaining the following results:
(1) Broadcast CONGEST model: (1 + epsilon)-approximate SSSP using ~O((sqrt(n) + D) epsilon^(-O(1))) rounds, where D is the (hop) diameter of the network.
(2) Broadcast congested clique model: (1 + epsilon)-approximate shortest transshipment and SSSP using ~O(epsilon^(-O(1))) rounds.
(3) Multipass streaming model: (1 + epsilon)-approximate shortest transshipment and SSSP using ~O(n) space and ~O(epsilon^(-O(1))) passes.
The previously fastest SSSP algorithms for these models leverage sparse hop sets. We bypass the hop set construction; computing a spanner is sufficient with our method. The above bounds assume non-negative integer edge weights that are polynomially bounded in n; for general non-negative weights, running times scale with the logarithm of the maximum ratio between non-zero weights. In case of asymmetric costs for traversing an edge in opposite directions, running times scale with the maximum ratio between the costs of both directions over all edges.
Cite as
Ruben Becker, Andreas Karrenbauer, Sebastian Krinninger, and Christoph Lenzen. Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 7:1-7:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{becker_et_al:LIPIcs.DISC.2017.7,
author = {Becker, Ruben and Karrenbauer, Andreas and Krinninger, Sebastian and Lenzen, Christoph},
title = {{Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models}},
booktitle = {31st International Symposium on Distributed Computing (DISC 2017)},
pages = {7:1--7:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-053-8},
ISSN = {1868-8969},
year = {2017},
volume = {91},
editor = {Richa, Andr\'{e}a},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.7},
URN = {urn:nbn:de:0030-drops-80031},
doi = {10.4230/LIPIcs.DISC.2017.7},
annote = {Keywords: Shortest Paths, Shortest Transshipment, Undirected Min-cost Flow, Gradient Descent, Spanner}
}
Document
Asynchronous Approach in the Plane: A Deterministic Polynomial Algorithm
Abstract
In this paper we study the task of approach of two mobile agents having the same limited range of vision and moving asynchronously in the plane. This task consists in getting them in finite time within each other's range of vision. The agents execute the same deterministic algorithm and are assumed to have a compass showing the cardinal directions as well as a unit measure. On the other hand, they do not share any global coordinates system (like GPS), cannot communicate and have distinct labels. Each agent knows its label but does not know the label of the other agent or the initial position of the other agent relative to its own. The route of an agent is a sequence of segments that are subsequently traversed in order to achieve approach. For each agent, the computation of its route depends only on its algorithm and its label. An adversary chooses the initial positions of both agents in the plane and controls the way each of them moves along every segment of the routes, in particular by arbitrarily varying the speeds of the agents. Roughly speaking, the goal of the adversary is to prevent the agents from solving the task, or at least to ensure that the agents have covered as much distance as possible before seeing each other. A deterministic approach algorithm is a deterministic algorithm that always allows two agents with any distinct labels to solve the task of approach regardless of the choices and the behavior of the adversary. The cost of a complete execution of an approach algorithm is the length of both parts of route travelled by the agents until approach is completed.
Let Delta and l be the initial distance separating the agents and the length of (the binary representation of) the shortest label, respectively. Assuming that Delta and l are unknown to both agents, does there exist a deterministic approach algorithm whose cost is polynomial in Delta and l?
Actually the problem of approach in the plane reduces to the network problem of rendezvous in an infinite oriented grid, which consists in ensuring that both agents end up meeting at the same time at a node or on an edge of the grid. By designing such a rendezvous algorithm with appropriate properties, as we do in this paper, we provide a positive answer to the above question.
Our result turns out to be an important step forward from a computational point of view, as the other algorithms allowing to solve the same problem either have an exponential cost in the initial separating distance and in the labels of the agents, or require each agent to know its starting position in a global system of coordinates, or only work under a much less powerful adversary.
Cite as
Sébastien Bouchard, Marjorie Bournat, Yoann Dieudonné, Swan Dubois, and Franck Petit. Asynchronous Approach in the Plane: A Deterministic Polynomial Algorithm. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 8:1-8:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{bouchard_et_al:LIPIcs.DISC.2017.8,
author = {Bouchard, S\'{e}bastien and Bournat, Marjorie and Dieudonn\'{e}, Yoann and Dubois, Swan and Petit, Franck},
title = {{Asynchronous Approach in the Plane: A Deterministic Polynomial Algorithm}},
booktitle = {31st International Symposium on Distributed Computing (DISC 2017)},
pages = {8:1--8:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-053-8},
ISSN = {1868-8969},
year = {2017},
volume = {91},
editor = {Richa, Andr\'{e}a},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.8},
URN = {urn:nbn:de:0030-drops-79631},
doi = {10.4230/LIPIcs.DISC.2017.8},
annote = {Keywords: mobile agents, asynchronous rendezvous, plane, infinite grid, deterministic algorithm, polynomial cost}
}
Document
Cost of Concurrency in Hybrid Transactional Memory
Abstract
State-of-the-art software transactional memory (STM) implementations achieve good performance by carefully avoiding the overhead of incremental validation (i.e., re-reading previously read data items to avoid inconsistency) while still providing progressiveness (allowing transactional aborts only due to data conflicts). Hardware transactional memory (HTM) implementations promise even better performance, but offer no progress guarantees. Thus, they must be combined with STMs, leading to hybrid TMs (HyTMs) in which hardware transactions must be instrumented (i.e., access metadata) to detect contention with software transactions.
We show that, unlike in progressive STMs, software transactions in progressive HyTMs cannot avoid incremental validation. In fact, this result holds even if hardware transactions can read metadata non-speculatively. We then present opaque HyTM algorithms providing progressiveness for a subset of transactions that are optimal in terms of hardware instrumentation. We explore the concurrency vs. hardware instrumentation vs. software validation trade-offs for these algorithms. Our experiments with Intel and IBM POWER8 HTMs seem to suggest that (i) the cost of concurrency also exists in practice, (ii) it is important to implement HyTMs that provide progressiveness for a maximal set of transactions without incurring high hardware instrumentation overhead or using global contending bottlenecks and (iii) there is no easy way to derive more efficient HyTMs by taking advantage of non-speculative accesses within hardware.
Cite as
Trevor Brown and Srivatsan Ravi. Cost of Concurrency in Hybrid Transactional Memory. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 9:1-9:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{brown_et_al:LIPIcs.DISC.2017.9,
author = {Brown, Trevor and Ravi, Srivatsan},
title = {{Cost of Concurrency in Hybrid Transactional Memory}},
booktitle = {31st International Symposium on Distributed Computing (DISC 2017)},
pages = {9:1--9:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-053-8},
ISSN = {1868-8969},
year = {2017},
volume = {91},
editor = {Richa, Andr\'{e}a},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.9},
URN = {urn:nbn:de:0030-drops-79958},
doi = {10.4230/LIPIcs.DISC.2017.9},
annote = {Keywords: Transactional memory, Lower bounds, Opacity}
}
Document
Quadratic and Near-Quadratic Lower Bounds for the CONGEST Model
Abstract
We present the first super-linear lower bounds for natural graph problems in the CONGEST model, answering a long-standing open question.
Specifically, we show that any exact computation of a minimum vertex cover or a maximum independent set requires a near-quadratic number of rounds in the CONGEST model, as well as any algorithm for computing the chromatic number of the graph. We further show that such strong lower bounds are not limited to NP-hard problems, by showing two simple graph problems in P which require a quadratic and near-quadratic number of rounds.
Finally, we address the problem of computing an exact solution to weighted all-pairs-shortest-paths (APSP), which arguably may be considered as a candidate for having a super-linear lower bound. We show a simple linear lower bound for this problem, which implies a separation between the weighted and unweighted cases, since the latter is known to have a sub-linear complexity. We also formally prove that the standard Alice-Bob framework is incapable of providing a super-linear lower bound for exact weighted APSP, whose complexity remains an intriguing open question.
Cite as
Keren Censor-Hillel, Seri Khoury, and Ami Paz. Quadratic and Near-Quadratic Lower Bounds for the CONGEST Model. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{censorhillel_et_al:LIPIcs.DISC.2017.10,
author = {Censor-Hillel, Keren and Khoury, Seri and Paz, Ami},
title = {{Quadratic and Near-Quadratic Lower Bounds for the CONGEST Model}},
booktitle = {31st International Symposium on Distributed Computing (DISC 2017)},
pages = {10:1--10:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-053-8},
ISSN = {1868-8969},
year = {2017},
volume = {91},
editor = {Richa, Andr\'{e}a},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.10},
URN = {urn:nbn:de:0030-drops-79969},
doi = {10.4230/LIPIcs.DISC.2017.10},
annote = {Keywords: CONGEST, Lower Bounds, Minimum Vertex Cover, Chromatic Number, Weighted APSP}
}
Document
Derandomizing Local Distributed Algorithms under Bandwidth Restrictions
Abstract
This paper addresses the cornerstone family of local problems in distributed computing, and investigates the curious gap between randomized and deterministic solutions under bandwidth restrictions.
Our main contribution is in providing tools for derandomizing solutions to local problems, when the n nodes can only send O(log n)-bit messages in each round of communication. We combine bounded independence, which we show to be sufficient for some algorithms, with the method of conditional expectations and with additional machinery, to obtain the following results.
First, we show that in the Congested Clique model, which allows all-to-all communication, there is a deterministic maximal independent set (MIS) algorithm that runs in O(log^2 Delta) rounds, where Delta is the maximum degree. When Delta=O(n^(1/3)), the bound improves to O(log Delta).
Adapting the above to the CONGEST model gives an O(D log^2 n)-round deterministic MIS algorithm, where D is the diameter of the graph. Apart from a previous unproven claim of a O(D log^3 n)-round algorithm, the only known deterministic solutions for the CONGEST model are a coloring-based O(Delta + log^* n)-round algorithm, where Delta is the maximal degree in the graph, and a 2^O(sqrt(log n log log n))-round algorithm, which is super-polylogarithmic in n.
In addition, we deterministically construct a (2k-1)-spanner with O(kn^(1+1/k) log n) edges in O(k log n) rounds in the Congested Clique model. For comparison, in the more stringent CONGEST model, where the communication graph is identical to the input graph, the best deterministic algorithm for constructing a (2k-1)-spanner with O(kn^(1+1/k)) edges runs in O(n^(1-1/k)) rounds.
Cite as
Keren Censor-Hillel, Merav Parter, and Gregory Schwartzman. Derandomizing Local Distributed Algorithms under Bandwidth Restrictions. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 11:1-11:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{censorhillel_et_al:LIPIcs.DISC.2017.11,
author = {Censor-Hillel, Keren and Parter, Merav and Schwartzman, Gregory},
title = {{Derandomizing Local Distributed Algorithms under Bandwidth Restrictions}},
booktitle = {31st International Symposium on Distributed Computing (DISC 2017)},
pages = {11:1--11:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-053-8},
ISSN = {1868-8969},
year = {2017},
volume = {91},
editor = {Richa, Andr\'{e}a},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.11},
URN = {urn:nbn:de:0030-drops-79759},
doi = {10.4230/LIPIcs.DISC.2017.11},
annote = {Keywords: Local problems, congested clique, derandomization}
}
Document
On the Number of Objects with Distinct Power and the Linearizability of Set Agreement Objects
Abstract
We first prove that there are uncountably many objects with distinct computational powers. More precisely, we show that there is an uncountable set of objects such that for any two of them, at least one cannot be implemented from the other (and registers) in a wait-free manner. We then strengthen this result by showing that there are uncountably many linearizable objects with distinct computational powers. To do so, we prove that for all positive integers n and k, there is a linearizable object that is computationally equivalent to the k-set agreement task among n processes. To the best of our knowledge, these are the first linearizable objects proven to be computationally equivalent to set agreement tasks.
Cite as
David Yu Cheng Chan, Vassos Hadzilacos, and Sam Toueg. On the Number of Objects with Distinct Power and the Linearizability of Set Agreement Objects. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 12:1-12:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{chan_et_al:LIPIcs.DISC.2017.12,
author = {Chan, David Yu Cheng and Hadzilacos, Vassos and Toueg, Sam},
title = {{On the Number of Objects with Distinct Power and the Linearizability of Set Agreement Objects}},
booktitle = {31st International Symposium on Distributed Computing (DISC 2017)},
pages = {12:1--12:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-053-8},
ISSN = {1868-8969},
year = {2017},
volume = {91},
editor = {Richa, Andr\'{e}a},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.12},
URN = {urn:nbn:de:0030-drops-79973},
doi = {10.4230/LIPIcs.DISC.2017.12},
annote = {Keywords: Set Agreement, Asynchronous System, Shared Memory}
}
Document
Fast Plurality Consensus in Regular Expanders
Abstract
In a voting process on a graph vertices revise their opinions in a distributed way based on the opinions of nearby vertices. The voting completes when the vertices reach consensus, that is, they all have the same opinion. The classic example is synchronous pull voting where at each step, each vertex adopts the opinion of a random neighbour. This very simple process, however, can be slow and the final opinion is not necessarily the one with the initial largest support. It was shown earlier that if there are initially only two opposing opinions, then both these drawbacks can be overcome by a synchronous two-sample voting, in which at each step each vertex considers its own opinion and the opinions of two random neighbours.
If there are initially three or more opinions, a problem arises when there is no clear majority. One class of opinions may be largest (the plurality opinion), although its total size is less than that of two other opinions put together. We analyse the performance of the two-sample voting on d-regular graphs for this case. We show that, if the difference between the initial sizes A_1 and A_2 of the largest and second largest opinions is at least C n max{sqrt((log n)/A_1), lambda}, then the largest opinion wins in O((n log n)/A_1) steps with high probability. Here C is a suitable constant and lambda is the absolute second eigenvalue of transition matrix P=Adj(G)/d of a simple random walk on the graph G. Our bound generalizes the results of Becchetti et al. [SPAA 2014] for the related three-sample voting process on complete graphs. Our bound implies that if lambda = o(1), then the two-sample voting can consistently converge to the largest opinion, even if A_1 - A_2 = o(n). If lambda is constant, we show that the case A_1 - A_2 = o(n) can be dealt with by sampling using short random walks. Finally, we give a simple and efficient push voting algorithm for the case when there are a number of large opinions and any of them is acceptable as the final winning opinion.
Cite as
Colin Cooper, Tomasz Radzik, Nicolás Rivera, and Takeharu Shiraga. Fast Plurality Consensus in Regular Expanders. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 13:1-13:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{cooper_et_al:LIPIcs.DISC.2017.13,
author = {Cooper, Colin and Radzik, Tomasz and Rivera, Nicol\'{a}s and Shiraga, Takeharu},
title = {{Fast Plurality Consensus in Regular Expanders}},
booktitle = {31st International Symposium on Distributed Computing (DISC 2017)},
pages = {13:1--13:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-053-8},
ISSN = {1868-8969},
year = {2017},
volume = {91},
editor = {Richa, Andr\'{e}a},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.13},
URN = {urn:nbn:de:0030-drops-79778},
doi = {10.4230/LIPIcs.DISC.2017.13},
annote = {Keywords: Plurality consensus, Regular expanders}
}
Document
Meeting in a Polygon by Anonymous Oblivious Robots
Abstract
The Meeting problem for k>=2 searchers in a polygon P (possibly with holes) consists in making the searchers move within P, according to a distributed algorithm, in such a way that at least two of them eventually come to see each other, regardless of their initial positions. The polygon is initially unknown to the searchers, and its edges obstruct both movement and vision. Depending on the shape of P, we minimize the number of searchers k for which the Meeting problem is solvable. Specifically, if P has a rotational symmetry of order sigma (where sigma=1 corresponds to no rotational symmetry), we prove that k=sigma+1 searchers are sufficient, and the bound is tight. Furthermore, we give an improved algorithm that optimally solves the Meeting problem with k=2 searchers in all polygons whose barycenter is not in a hole (which includes the polygons with no holes). Our algorithms can be implemented in a variety of standard models of mobile robots operating in Look-Compute-Move cycles. For instance, if the searchers have memory but are anonymous, asynchronous, and have no agreement on a coordinate system or a notion of clockwise direction, then our algorithms work even if the initial memory contents of the searchers are arbitrary and possibly misleading. Moreover, oblivious searchers can execute our algorithms as well, encoding information by carefully positioning themselves within the polygon. This code is computable with basic arithmetic operations (provided that the coordinates of the polygon's vertices are algebraic real numbers in some global coordinate system), and each searcher can geometrically construct its own destination point at each cycle using only a compass. We stress that such memoryless searchers may be located anywhere in the polygon when the execution begins, and hence the information they initially encode is arbitrary. Our algorithms use a self-stabilizing map construction subroutine which is of independent interest.
Cite as
Giuseppe A. Di Luna, Paola Flocchini, Nicola Santoro, Giovanni Viglietta, and Masafumi Yamashita. Meeting in a Polygon by Anonymous Oblivious Robots. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 14:1-14:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{diluna_et_al:LIPIcs.DISC.2017.14,
author = {Di Luna, Giuseppe A. and Flocchini, Paola and Santoro, Nicola and Viglietta, Giovanni and Yamashita, Masafumi},
title = {{Meeting in a Polygon by Anonymous Oblivious Robots}},
booktitle = {31st International Symposium on Distributed Computing (DISC 2017)},
pages = {14:1--14:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-053-8},
ISSN = {1868-8969},
year = {2017},
volume = {91},
editor = {Richa, Andr\'{e}a},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.14},
URN = {urn:nbn:de:0030-drops-79833},
doi = {10.4230/LIPIcs.DISC.2017.14},
annote = {Keywords: Meeting problem, Oblivious robots, Polygon, Self-stabilization}
}
Document
Three Notes on Distributed Property Testing
Abstract
In this paper we present distributed property-testing algorithms for graph properties in the CONGEST model, with emphasis on testing subgraph-freeness. Testing a graph property P means distinguishing graphs G = (V,E) having property P from graphs that are epsilon-far from having it, meaning that epsilon|E| edges must be added or removed from G to obtain a graph satisfying P.
We present a series of results, including:
- Testing H-freeness in O(1/epsilon) rounds, for any constant-sized graph H containing an edge (u,v) such that any cycle in H contain either u or v (or both). This includes all connected graphs over five vertices except K_5. For triangles, we can do even better when epsilon is not too small.
- A deterministic CONGEST protocol determining whether a graph contains a given tree as a subgraph in constant time.
- For cliques K_s with s >= 5, we show that K_s-freeness can be tested in O(m^(1/2-1/(s-2)) epsilon^(-1/2-1/(s-2))) rounds, where m is the number of edges in the network graph.
- We describe a general procedure for converting epsilon-testers with f(D) rounds, where D denotes the diameter of the graph, to work in O((log n)/epsilon)+f((log n)/epsilon) rounds, where n is the number of processors of the network. We then apply this procedure to obtain an epsilon-tester for testing whether a graph is bipartite and testing whether a graph is cycle-free. Moreover, for cycle-freeness, we obtain a corrector of the graph that locally corrects the graph so that the corrected graph is acyclic. Note that, unlike a tester, a corrector needs to mend the graph in many places in the case that the graph is far from having the property.
These protocols extend and improve previous results of [Censor-Hillel et al. 2016] and [Fraigniaud et al. 2016].
Cite as
Guy Even, Orr Fischer, Pierre Fraigniaud, Tzlil Gonen, Reut Levi, Moti Medina, Pedro Montealegre, Dennis Olivetti, Rotem Oshman, Ivan Rapaport, and Ioan Todinca. Three Notes on Distributed Property Testing. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 15:1-15:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{even_et_al:LIPIcs.DISC.2017.15,
author = {Even, Guy and Fischer, Orr and Fraigniaud, Pierre and Gonen, Tzlil and Levi, Reut and Medina, Moti and Montealegre, Pedro and Olivetti, Dennis and Oshman, Rotem and Rapaport, Ivan and Todinca, Ioan},
title = {{Three Notes on Distributed Property Testing}},
booktitle = {31st International Symposium on Distributed Computing (DISC 2017)},
pages = {15:1--15:30},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-053-8},
ISSN = {1868-8969},
year = {2017},
volume = {91},
editor = {Richa, Andr\'{e}a},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.15},
URN = {urn:nbn:de:0030-drops-79847},
doi = {10.4230/LIPIcs.DISC.2017.15},
annote = {Keywords: Property testing, Property correcting, Distributed algorithms, CONGEST model}
}
Document
Error-Sensitive Proof-Labeling Schemes
Abstract
Proof-labeling schemes are known mechanisms providing nodes of networks with certificates that can be verified locally by distributed algorithms. Given a boolean predicate on network states, such schemes enable to check whether the predicate is satisfied by the actual state of the network, by having nodes interacting with their neighbors only. Proof-labeling schemes are typically designed for enforcing fault-tolerance, by making sure that if the current state of the network is illegal with respect to some given predicate, then at least one node will detect it. Such a node can raise an alarm, or launch a recovery procedure enabling the system to return to a legal state. In this paper, we introduce error-sensitive proof-labeling schemes. These are proof-labeling schemes which guarantee that the number of nodes detecting illegal states is linearly proportional to the edit-distance between the current state and the set of legal states. By using error-sensitive proof-labeling schemes, states which are far from satisfying the predicate will be detected by many nodes, enabling fast return to legality. We provide a structural characterization of the set of boolean predicates on network states for which there exist error-sensitive proof-labeling schemes. This characterization allows us to show that classical predicates such as, e.g., acyclicity, and leader admit error-sensitive proof-labeling schemes, while others like regular subgraphs don't. We also focus on compact error-sensitive proof-labeling schemes. In particular, we show that the known proof-labeling schemes for spanning tree and minimum spanning tree, using certificates on O(log n) bits, and on O(log^2 n) bits, respectively, are error-sensitive, as long as the trees are locally represented by adjacency lists, and not just by parent pointers.
Cite as
Laurent Feuilloley and Pierre Fraigniaud. Error-Sensitive Proof-Labeling Schemes. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 16:1-16:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{feuilloley_et_al:LIPIcs.DISC.2017.16,
author = {Feuilloley, Laurent and Fraigniaud, Pierre},
title = {{Error-Sensitive Proof-Labeling Schemes}},
booktitle = {31st International Symposium on Distributed Computing (DISC 2017)},
pages = {16:1--16:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-053-8},
ISSN = {1868-8969},
year = {2017},
volume = {91},
editor = {Richa, Andr\'{e}a},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.16},
URN = {urn:nbn:de:0030-drops-80180},
doi = {10.4230/LIPIcs.DISC.2017.16},
annote = {Keywords: Fault-tolerance, distributed decision, distributed property testing}
}
Document
Improved Deterministic Distributed Matching via Rounding
Abstract
We present improved deterministic distributed algorithms for a number of well-studied matching problems, which are simpler, faster, more accurate, and/or more general than their known counterparts. The common denominator of these results is a deterministic distributed rounding method for certain linear programs, which is the first such rounding method, to our knowledge.
A sampling of our end results is as follows.
- An O(log^2 Delta log n)-round deterministic distributed algorithm for computing a maximal matching, in n-node graphs with maximum degree Delta. This is the first improvement in about 20 years over the celebrated O(log^4 n)-round algorithm of Hanckowiak, Karonski, and Panconesi [SODA'98, PODC'99].
- A deterministic distributed algorithm for computing a (2+epsilon)-approximation of maximum matching in O(log^2 Delta log(1/epsilon) + log^* n) rounds. This is exponentially faster than the classic O(Delta + log^* n)-round 2-approximation of Panconesi and Rizzi [DIST'01]. With some modifications, the algorithm can also find an epsilon-maximal matching which leaves only an epsilon-fraction of the edges on unmatched nodes.
- An O(log^2 Delta log(1/epsilon) + log^* n)-round deterministic distributed algorithm for computing a (2+epsilon)-approximation of a maximum weighted matching, and also for the more general problem of maximum weighted b-matching. These improve over the O(log^4 n log_(1+epsilon) W)-round (6+epsilon)-approximation algorithm of Panconesi and Sozio [DIST'10], where W denotes the maximum normalized weight.
- A deterministic local computation algorithm for a (2+epsilon)-approximation of maximum matching with 2^O(log^2 Delta) log^* n queries. This improves almost exponentially over the previous deterministic constant approximations which have query-complexity of 2^Omega(Delta log Delta) log^* n.
Cite as
Manuela Fischer. Improved Deterministic Distributed Matching via Rounding. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 17:1-17:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{fischer:LIPIcs.DISC.2017.17,
author = {Fischer, Manuela},
title = {{Improved Deterministic Distributed Matching via Rounding}},
booktitle = {31st International Symposium on Distributed Computing (DISC 2017)},
pages = {17:1--17:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-053-8},
ISSN = {1868-8969},
year = {2017},
volume = {91},
editor = {Richa, Andr\'{e}a},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.17},
URN = {urn:nbn:de:0030-drops-80027},
doi = {10.4230/LIPIcs.DISC.2017.17},
annote = {Keywords: distributed graph algorithms, deterministic distributed algorithms, rounding linear programs, maximal matching, maximum matching approximation}
}
Document
Sublogarithmic Distributed Algorithms for Lovász Local Lemma, and the Complexity Hierarchy
Abstract
Locally Checkable Labeling (LCL) problems include essentially all the classic problems of LOCAL distributed algorithms. In a recent enlightening revelation, Chang and Pettie [FOCS'17] showed that any LCL (on bounded degree graphs) that has an o(log n)-round randomized algorithm can be solved in T_(LLL)(n) rounds, which is the randomized complexity of solving (a relaxed variant of) the Lovasz Local Lemma (LLL) on bounded degree n-node graphs. Currently, the best known upper bound on T_(LLL)(n) is O(log n), by Chung, Pettie, and Su [PODC'14], while the best known lower bound is Omega(log log n), by Brandt et al. [STOC'16]. Chang and Pettie conjectured that there should be an O(log log n)-round algorithm (on bounded degree graphs).
Making the first step of progress towards this conjecture, and providing a significant improvement on the algorithm of Chung et al. [PODC'14], we prove that T_(LLL)(n)= 2^O(sqrt(log log n)). Thus, any o(log n)-round randomized distributed algorithm for any LCL problem on bounded degree graphs can be automatically sped up to run in 2^O(sqrt(log log n)) rounds.
Using this improvement and a number of other ideas, we also improve the complexity of a number of graph coloring problems (in arbitrary degree graphs) from the O(log n)-round results of Chung, Pettie and Su [PODC'14] to 2^O(sqrt(log log n)). These problems include defective coloring, frugal coloring, and list vertex-coloring.
Cite as
Manuela Fischer and Mohsen Ghaffari. Sublogarithmic Distributed Algorithms for Lovász Local Lemma, and the Complexity Hierarchy. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 18:1-18:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{fischer_et_al:LIPIcs.DISC.2017.18,
author = {Fischer, Manuela and Ghaffari, Mohsen},
title = {{Sublogarithmic Distributed Algorithms for Lov\'{a}sz Local Lemma, and the Complexity Hierarchy}},
booktitle = {31st International Symposium on Distributed Computing (DISC 2017)},
pages = {18:1--18:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-053-8},
ISSN = {1868-8969},
year = {2017},
volume = {91},
editor = {Richa, Andr\'{e}a},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.18},
URN = {urn:nbn:de:0030-drops-79732},
doi = {10.4230/LIPIcs.DISC.2017.18},
annote = {Keywords: Distributed Graph Algorithms, the Lov'\{a\}sz Local Lemma (LLL), Locally Checkable Labeling problems (LCL), Defective Coloring, Frugal Coloring, List Ve}
}
Document
Improved Distributed Degree Splitting and Edge Coloring
Abstract
The degree splitting problem requires coloring the edges of a graph red or blue such that each node has almost the same number of edges in each color, up to a small additive discrepancy. The directed variant of the problem requires orienting the edges such that each node has almost the same number of incoming and outgoing edges, again up to a small additive discrepancy.
We present deterministic distributed algorithms for both variants, which improve on their counterparts presented by Ghaffari and Su [SODA'17]: our algorithms are significantly simpler and faster, and have a much smaller discrepancy. This also leads to a faster and simpler deterministic algorithm for (2+o(1))Delta-edge-coloring, improving on that of Ghaffari and Su.
Cite as
Mohsen Ghaffari, Juho Hirvonen, Fabian Kuhn, Yannic Maus, Jukka Suomela, and Jara Uitto. Improved Distributed Degree Splitting and Edge Coloring. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 19:1-19:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{ghaffari_et_al:LIPIcs.DISC.2017.19,
author = {Ghaffari, Mohsen and Hirvonen, Juho and Kuhn, Fabian and Maus, Yannic and Suomela, Jukka and Uitto, Jara},
title = {{Improved Distributed Degree Splitting and Edge Coloring}},
booktitle = {31st International Symposium on Distributed Computing (DISC 2017)},
pages = {19:1--19:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-053-8},
ISSN = {1868-8969},
year = {2017},
volume = {91},
editor = {Richa, Andr\'{e}a},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.19},
URN = {urn:nbn:de:0030-drops-79794},
doi = {10.4230/LIPIcs.DISC.2017.19},
annote = {Keywords: Distributed Graph Algorithms, Degree Splitting, Edge Coloring, Discrepancy}
}
Document
Simple and Near-Optimal Distributed Coloring for Sparse Graphs
Abstract
Graph coloring is one of the central problems in distributed graph algorithms. Much of the research on this topic has focused on coloring with Delta+1 colors, where Delta denotes the maximum degree. Using Delta+1 colors may be unsatisfactory in sparse graphs, where not all nodes have such a high degree; it would be more desirable to use a number of colors that improves with sparsity. A standard measure that captures sparsity is arboricity, which is the smallest number of forests into which the edges of the graph can be partitioned.
We present simple randomized distributed algorithms that, with high probability, color any n-node alpha-arboricity graph:
- using (2+epsilon)alpha colors, for constant epsilon>0, in O(log n) rounds, if alpha=Omega(log n log log n), or
- using O(alpha log alpha) colors, in O(log n) rounds, or
- using O(alpha) colors, in O(log n min{log log n, log alpha}) rounds.
These algorithms are nearly-optimal, as it is known by results of Linial [FOCS'87] and Barenboim and Elkin [PODC'08] that coloring with Theta(alpha) colors, or even poly(alpha) colors, requires Omega(log_alpha n) rounds. The previously best-known O(log n)-time result was a deterministic algorithm due to Barenboim and Elkin [PODC'08], which uses Theta(alpha^2) colors. Barenboim and Elkin stated improving this number of colors as an open problem in their Distributed Graph Coloring Book.
Cite as
Mohsen Ghaffari and Christiana Lymouri. Simple and Near-Optimal Distributed Coloring for Sparse Graphs. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 20:1-20:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{ghaffari_et_al:LIPIcs.DISC.2017.20,
author = {Ghaffari, Mohsen and Lymouri, Christiana},
title = {{Simple and Near-Optimal Distributed Coloring for Sparse Graphs}},
booktitle = {31st International Symposium on Distributed Computing (DISC 2017)},
pages = {20:1--20:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-053-8},
ISSN = {1868-8969},
year = {2017},
volume = {91},
editor = {Richa, Andr\'{e}a},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.20},
URN = {urn:nbn:de:0030-drops-80178},
doi = {10.4230/LIPIcs.DISC.2017.20},
annote = {Keywords: Distributed Graph Algorithms, Graph Coloring, Arboricity}
}
Document
Near-Optimal Distributed DFS in Planar Graphs
Abstract
We present a randomized distributed algorithm that computes a Depth-First Search (DFS) tree in ~O(D) rounds, in any planar network G=(V,E) with diameter D, with high probability. This is the first sublinear-time distributed DFS algorithm, improving on a three decades-old O(n) algorithm of Awerbuch (1985), which remains the best known for general graphs. Furthermore, this ~O(D) round complexity is nearly-optimal as Omega(D) is a trivial lower bound.
A key technical ingredient in our results is the development of a distributed method for (recursively) computing a separator path, which is a path whose removal from the graph leaves connected components that are all a constant factor smaller. We believe that the general method we develop for computing path separators recursively might be of broader interest, and may provide the first step towards solving many other problems.
Cite as
Mohsen Ghaffari and Merav Parter. Near-Optimal Distributed DFS in Planar Graphs. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 21:1-21:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{ghaffari_et_al:LIPIcs.DISC.2017.21,
author = {Ghaffari, Mohsen and Parter, Merav},
title = {{Near-Optimal Distributed DFS in Planar Graphs}},
booktitle = {31st International Symposium on Distributed Computing (DISC 2017)},
pages = {21:1--21:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-053-8},
ISSN = {1868-8969},
year = {2017},
volume = {91},
editor = {Richa, Andr\'{e}a},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.21},
URN = {urn:nbn:de:0030-drops-80195},
doi = {10.4230/LIPIcs.DISC.2017.21},
annote = {Keywords: congest model, planar graphs, separator}
}
Document
Dynamic Analysis of the Arrow Distributed Directory Protocol in General Networks
Abstract
The Arrow protocol is a simple and elegant protocol to coordinate exclusive access to a shared object in a network. The protocol solves the underlying distributed queueing problem by using path reversal on a pre-computed spanning tree (or any other tree topology simulated on top of the given network).
It is known that the Arrow protocol solves the problem with a competitive ratio of O(log D) on trees of diameter D. This implies a distributed queueing algorithm with competitive ratio O(s log D) for general networks with a spanning tree of diameter D and stretch s. In this work we show that when running the Arrow protocol on top of the well-known probabilistic tree embedding of Fakcharoenphol, Rao, and Talwar [STOC'03], we obtain a randomized distributed online queueing algorithm with expected competitive ratio O(log n) against an oblivious adversary even on general n-node network topologies. The result holds even if the queueing requests occur in an arbitrarily dynamic and concurrent fashion and even if communication is asynchronous. The main technical result of the paper shows that the competitive ratio of the Arrow protocol is constant on a special family of tree topologies, known as hierarchically well separated trees.
Cite as
Abdolhamid Ghodselahi and Fabian Kuhn. Dynamic Analysis of the Arrow Distributed Directory Protocol in General Networks. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 22:1-22:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{ghodselahi_et_al:LIPIcs.DISC.2017.22,
author = {Ghodselahi, Abdolhamid and Kuhn, Fabian},
title = {{Dynamic Analysis of the Arrow Distributed Directory Protocol in General Networks}},
booktitle = {31st International Symposium on Distributed Computing (DISC 2017)},
pages = {22:1--22:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-053-8},
ISSN = {1868-8969},
year = {2017},
volume = {91},
editor = {Richa, Andr\'{e}a},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.22},
URN = {urn:nbn:de:0030-drops-79857},
doi = {10.4230/LIPIcs.DISC.2017.22},
annote = {Keywords: Arrow protocol, competitive analysis, distributed queueing, shared objects, tree embeddings}
}
Document
Consistency Models with Global Operation Sequencing and their Composition
Abstract
Modern distributed systems often achieve availability and scalability by providing consistency guarantees about the data they manage weaker than linearizability. We consider a class of such consistency models that, despite this weakening, guarantee that clients eventually agree on a global sequence of operations, while seeing a subsequence of this final sequence at any given point of time. Examples of such models include the classical Total Store Order (TSO) and recently proposed dual TSO, Global Sequence Protocol (GSP) and Ordered Sequential Consistency.
We define a unified model, called Global Sequence Consistency (GSC), that has the above models as its special cases, and investigate its key properties. First, we propose a condition under which multiple objects each satisfying GSC can be composed so that the whole set of objects satisfies GSC. Second, we prove an interesting relationship between special cases of GSC - GSP, TSO and dual TSO: we show that clients that do not communicate out-of-band cannot tell the difference between these models. To obtain these results, we propose a novel axiomatic specification of GSC and prove its equivalence to the operational definition of the model.
Cite as
Alexey Gotsman and Sebastian Burckhardt. Consistency Models with Global Operation Sequencing and their Composition. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 23:1-23:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{gotsman_et_al:LIPIcs.DISC.2017.23,
author = {Gotsman, Alexey and Burckhardt, Sebastian},
title = {{Consistency Models with Global Operation Sequencing and their Composition}},
booktitle = {31st International Symposium on Distributed Computing (DISC 2017)},
pages = {23:1--23:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-053-8},
ISSN = {1868-8969},
year = {2017},
volume = {91},
editor = {Richa, Andr\'{e}a},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.23},
URN = {urn:nbn:de:0030-drops-79748},
doi = {10.4230/LIPIcs.DISC.2017.23},
annote = {Keywords: Consistency conditions, Weak memory models, Compositionality}
}
Document
Improved Deterministic Distributed Construction of Spanners
Abstract
Graph spanners are fundamental graph structures with a wide range of applications in distributed networks. We consider a standard synchronous message passing model where in each round O(log n) bits can be transmitted over every edge (the CONGEST model).
The state of the art of deterministic distributed spanner constructions suffers from large messages. The only exception is the work of Derbel et al., which computes an optimal-sized (2k-1)-spanner but uses O(n^(1-1/k)) rounds.
In this paper, we significantly improve this bound. We present a deterministic distributed algorithm that given an unweighted n-vertex graph G = (V,E) and a parameter k > 2, constructs a (2k-1)-spanner with O(k n^(1+1/k)) edges within O(2^k n^(1/2 - 1/k)) rounds for every even k. For odd k, the number of rounds is O(2^k n^(1/2 - 1/(2k))). For the weighted case, we provide the first deterministic construction of a 3-spanner with O(n^(3/2)) edges that uses O(log n)-size messages and ~O(1) rounds. If the vertices have IDs in [1,Theta(n)], the spanner is computed in only 2 rounds!
Cite as
Ofer Grossman and Merav Parter. Improved Deterministic Distributed Construction of Spanners. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 24:1-24:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{grossman_et_al:LIPIcs.DISC.2017.24,
author = {Grossman, Ofer and Parter, Merav},
title = {{Improved Deterministic Distributed Construction of Spanners}},
booktitle = {31st International Symposium on Distributed Computing (DISC 2017)},
pages = {24:1--24:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-053-8},
ISSN = {1868-8969},
year = {2017},
volume = {91},
editor = {Richa, Andr\'{e}a},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.24},
URN = {urn:nbn:de:0030-drops-80085},
doi = {10.4230/LIPIcs.DISC.2017.24},
annote = {Keywords: spanners, clustering, deterministic algorithms, congest model}
}
Document
An Efficient Communication Abstraction for Dense Wireless Networks
Abstract
In this paper we study the problem of developing efficient distributed algorithms for dense wireless networks. For many problems in this setting, fast solutions must leverage the reality that radio signals fade with distance, which can be exploited to enable concurrent communication among multiple sender/receiver pairs. To simplify the development of these algorithms we describe a new communication abstraction called FadingMAC which exposes the benefits of this concurrent communication, but also hides the details of the underlying low-level radio signal behavior. This approach splits efforts between those who develop useful algorithms that run on the abstraction, and those who implement the abstraction in concrete low-level wireless models, or on real hardware.
After defining FadingMAC, we describe and analyze an efficient implementation of the abstraction in a standard low-level SINR-style network model. We then describe solutions to the following problems that run on the abstraction: max, min, sum, and mean computed over input values; process renaming; consensus and leader election; and optimal packet scheduling. Combining our abstraction implementation with these applications that run on the abstraction, we obtain near-optimal solutions to these problems in our low-level SINR model - significantly advancing the known results for distributed algorithms in this setting. Of equal importance to these concrete bounds, however, is the general idea advanced by this paper: as wireless networks become more dense, both theoreticians and practitioners must explore new communication abstractions that can help tame this density.
Cite as
Magnús M. Halldórsson, Fabian Kuhn, Nancy Lynch, and Calvin Newport. An Efficient Communication Abstraction for Dense Wireless Networks. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 25:1-25:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{halldorsson_et_al:LIPIcs.DISC.2017.25,
author = {Halld\'{o}rsson, Magn\'{u}s M. and Kuhn, Fabian and Lynch, Nancy and Newport, Calvin},
title = {{An Efficient Communication Abstraction for Dense Wireless Networks}},
booktitle = {31st International Symposium on Distributed Computing (DISC 2017)},
pages = {25:1--25:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-053-8},
ISSN = {1868-8969},
year = {2017},
volume = {91},
editor = {Richa, Andr\'{e}a},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.25},
URN = {urn:nbn:de:0030-drops-79898},
doi = {10.4230/LIPIcs.DISC.2017.25},
annote = {Keywords: wireless networks, abstractions, SINR, signal fading}
}
Document
Two-Party Direct-Sum Questions Through the Lens of Multiparty Communication Complexity
Abstract
Direct-sum questions in (two-party) communication complexity ask whether two parties, Alice and Bob, can compute the value of a function f on l inputs (x_1,y_1),...,(x_l,y_l) more efficiently than by applying the best protocol for f, independently on each input (x_i,y_i). In spite of significant efforts to understand these questions (under various communication-complexity measures), the general question is still far from being well understood.
In this paper, we offer a multiparty view of these questions: The direct-sum setting is just a two-player system with Alice having inputs x_1,...,x_l, Bob having inputs y_1,...,y_l and the desired output is f(x_1,y_1),...,f(x_l,y_l). The naive solution of solving the l problems independently, is modeled by a network with l (disconnected) pairs of players Alice i and Bob i, with inputs x_i,y_i respectively, and communication only within each pair. Then, we consider an intermediate ("star") model, where there is one Alice having l inputs x_1,...,x_l and l players Bob_1,...,Bob_l holding y_1,...,y_l, respectively (in fact, we consider few variants of this intermediate model, depending on whether communication between each Bob i and Alice is point-to-point or whether we allow broadcast). Our goal is to get a better understanding of the relation between the two extreme models (i.e., of the two-party direct-sum question). If, for instance, Alice and Bob can do better (for some complexity measure) than solving the l problems independently, we wish to understand what intermediate model already allows to do so (hereby understanding the "source" of such savings). If, on the other hand, we wish to prove that there is no better solution than solving the l problems independently, then our approach gives a way of breaking the task of proving such a statement into few (hopefully, easier) steps.
We present several results of both types. Namely, for certain complexity measures, communication problems f and certain pairs of models, we can show gaps between the complexity of solving f on l instances in the two models in question; while, for certain other complexity measures and pairs of models, we can show that such gaps do not exist (for any communication problem f). For example, we prove that if only point-to-point communication is allowed in the intermediate "star" model, then significant savings are impossible in the public-coin randomized setting. On the other hand, in the private-coin randomized setting, if Alice is allowed to broadcast messages to all Bobs in the "star" network, then some savings are possible. While this approach does not lead yet to new results on the original two-party direct-sum question, we believe that our work gives new insights on the already-known direct-sum results, and may potentially lead to more such results in the future.
Cite as
Itay Hazan and Eyal Kushilevitz. Two-Party Direct-Sum Questions Through the Lens of Multiparty Communication Complexity. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 26:1-26:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{hazan_et_al:LIPIcs.DISC.2017.26,
author = {Hazan, Itay and Kushilevitz, Eyal},
title = {{Two-Party Direct-Sum Questions Through the Lens of Multiparty Communication Complexity}},
booktitle = {31st International Symposium on Distributed Computing (DISC 2017)},
pages = {26:1--26:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-053-8},
ISSN = {1868-8969},
year = {2017},
volume = {91},
editor = {Richa, Andr\'{e}a},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.26},
URN = {urn:nbn:de:0030-drops-79998},
doi = {10.4230/LIPIcs.DISC.2017.26},
annote = {Keywords: Communication Complexity, Direct Sum, Multiparty Communication}
}
Document
Which Broadcast Abstraction Captures k-Set Agreement?
Abstract
It is well-known that consensus (one-set agreement) and total order broadcast are equivalent in asynchronous systems prone to process crash failures. Considering wait-free systems, this article addresses and answers the following question: which is the communication abstraction that "captures" k-set agreement? To this end, it introduces a new broadcast communication abstraction, called k-BO-Broadcast, which restricts the disagreement on the local deliveries of the messages that have been broadcast (1-BO-Broadcast boils down to total order broadcast). Hence, in this context, k=1 is not a special number, but only the first integer in an increasing integer sequence.
This establishes a new "correspondence" between distributed agreement problems and communication abstractions, which enriches our understanding of the relations linking fundamental issues of fault-tolerant distributed computing.
Cite as
Damien Imbs, Achour Mostéfaoui, Matthieu Perrin, and Michel Raynal. Which Broadcast Abstraction Captures k-Set Agreement?. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 27:1-27:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{imbs_et_al:LIPIcs.DISC.2017.27,
author = {Imbs, Damien and Most\'{e}faoui, Achour and Perrin, Matthieu and Raynal, Michel},
title = {{Which Broadcast Abstraction Captures k-Set Agreement?}},
booktitle = {31st International Symposium on Distributed Computing (DISC 2017)},
pages = {27:1--27:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-053-8},
ISSN = {1868-8969},
year = {2017},
volume = {91},
editor = {Richa, Andr\'{e}a},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.27},
URN = {urn:nbn:de:0030-drops-79943},
doi = {10.4230/LIPIcs.DISC.2017.27},
annote = {Keywords: Agreement problem, Antichain, Asynchronous system, Communication abstraction, Consensus, Message-passing system, Partially ordered set, Process crash}
}
Document
Extending Hardware Transactional Memory Capacity via Rollback-Only Transactions and Suspend/Resume
Abstract
Transactional memory (TM) aims at simplifying concurrent programming via the familiar abstraction of atomic transactions. Recently, Intel and IBM have integrated hardware based TM (HTM) implementations in commodity processors, paving the way for the mainstream adoption of the TM paradigm. Yet, existing HTM implementations suffer from a crucial limitation, which hampers the adoption of HTM as a general technique for regulating concurrent access to shared memory: the inability to execute transactions whose working sets exceed the capacity of CPU caches. In this paper we propose P8TM, a novel approach that mitigates this limitation on IBM's POWER8 architecture by leveraging a key combination of techniques: uninstrumented read-only transactions, Rollback Only Transaction-based update transactions, HTM-friendly (software-based) read-set tracking, and self-tuning. P8TM can dynamically switch between different execution modes to best adapt to the nature of the transactions and the experienced abort patterns. In-depth evaluation with several benchmarks indicates that P8TM can achieve striking performance gains in workloads that stress the capacity limitations of HTM, while achieving performance on par with HTM even in unfavourable workloads.
Cite as
Shady Issa, Pascal Felber, Alexander Matveev, and Paolo Romano. Extending Hardware Transactional Memory Capacity via Rollback-Only Transactions and Suspend/Resume. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 28:1-28:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{issa_et_al:LIPIcs.DISC.2017.28,
author = {Issa, Shady and Felber, Pascal and Matveev, Alexander and Romano, Paolo},
title = {{Extending Hardware Transactional Memory Capacity via Rollback-Only Transactions and Suspend/Resume}},
booktitle = {31st International Symposium on Distributed Computing (DISC 2017)},
pages = {28:1--28:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-053-8},
ISSN = {1868-8969},
year = {2017},
volume = {91},
editor = {Richa, Andr\'{e}a},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.28},
URN = {urn:nbn:de:0030-drops-79811},
doi = {10.4230/LIPIcs.DISC.2017.28},
annote = {Keywords: hardware transactional memory, self tuning, parallel programming}
}
Document
Some Lower Bounds in Dynamic Networks with Oblivious Adversaries
Abstract
This paper considers several closely-related problems in synchronous dynamic networks with oblivious adversaries, and proves novel Omega(d + poly(m)) lower bounds on their time complexity (in rounds). Here d is the dynamic diameter of the dynamic network and m is the total number of nodes. Before this work, the only known lower bounds on these problems under oblivious adversaries were the trivial Omega(d) lower bounds. Our novel lower bounds are hence the first non-trivial lower bounds and also the first lower bounds with a poly(m) term. Our proof relies on a novel reduction from a certain two-party communication complexity problem. Our central proof technique is unique in the sense that we consider the communication complexity with a special leaker. The leaker helps Alice and Bob in the two-party problem, by disclosing to Alice and Bob certain "non-critical" information about the problem instance that they are solving.
Cite as
Irvan Jahja, Haifeng Yu, and Yuda Zhao. Some Lower Bounds in Dynamic Networks with Oblivious Adversaries. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 29:1-29:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{jahja_et_al:LIPIcs.DISC.2017.29,
author = {Jahja, Irvan and Yu, Haifeng and Zhao, Yuda},
title = {{Some Lower Bounds in Dynamic Networks with Oblivious Adversaries}},
booktitle = {31st International Symposium on Distributed Computing (DISC 2017)},
pages = {29:1--29:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-053-8},
ISSN = {1868-8969},
year = {2017},
volume = {91},
editor = {Richa, Andr\'{e}a},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.29},
URN = {urn:nbn:de:0030-drops-79690},
doi = {10.4230/LIPIcs.DISC.2017.29},
annote = {Keywords: dynamic networks, oblivious adversary, adaptive adversary, lower bounds, communication complexity}
}
Document
Recoverable FCFS Mutual Exclusion with Wait-Free Recovery
Abstract
Traditional mutual exclusion locks are not resilient to failures: if there is a power outage, the memory is wiped out. Thus, when the system comes back on, the lock will have to be restored to the initial state, i.e., all processes are rolled back to the Remainder section and all variables are reset to their initial values. Recently, Golab and Ramaraju showed that we can improve this state of the art by exploiting the Non-Volatile RAM (NVRAM). They designed algorithms that, by maintaining shared variables in NVRAM, allow processes to recover from crashes on their own without a need for a global reset, even though a crash can wipe out the local memory of a process.
We present a Recoverable Mutual Exclusion algorithm using the commonly supported CAS primitive. The main features of our algorithm are that it satisfies FCFS, it ensures that each process recovers in a wait-free manner, and in the absence of failures, it guarantees a worst-case Remote Memory Reference (RMR) complexity of O(lg n) on both Cache Coherent (CC) and Distributed Shared Memory (DSM) machines, where n is the number of processes for which the algorithm is designed. This bound matches the Omega(lg n) RMR lower bound by Attiya, Hendler, and Woelfel for Mutual Exclusion algorithms that use comparison primitives.
Cite as
Prasad Jayanti and Anup Joshi. Recoverable FCFS Mutual Exclusion with Wait-Free Recovery. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 30:1-30:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{jayanti_et_al:LIPIcs.DISC.2017.30,
author = {Jayanti, Prasad and Joshi, Anup},
title = {{Recoverable FCFS Mutual Exclusion with Wait-Free Recovery}},
booktitle = {31st International Symposium on Distributed Computing (DISC 2017)},
pages = {30:1--30:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-053-8},
ISSN = {1868-8969},
year = {2017},
volume = {91},
editor = {Richa, Andr\'{e}a},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.30},
URN = {urn:nbn:de:0030-drops-80005},
doi = {10.4230/LIPIcs.DISC.2017.30},
annote = {Keywords: concurrent algorithm, synchronization, mutual exclusion, recovery, fault tolerance, non-volatile main memory, shared memory, multi-core algorithms}
}
Document
Interactive Compression for Multi-Party Protocol
Abstract
The field of compression studies the question of how many bits of communication are necessary to convey a given piece of data. For one-way communication between a sender and a receiver, the seminal work of Shannon and Huffman showed that the communication required is characterized by the entropy of the data; in recent years, there has been a great amount of interest in extending this line of research to interactive communication, where instead of a sender and a receiver we have two parties communication back-and-forth. In this paper we initiate the study of interactive compression for distributed multi-player protocols. We consider the classical shared blackboard model, where players take turns speaking, and each player's message is immediately seen by all the other players. We show that in the shared blackboard model with k players, one can compress protocols down to ~O(Ik), where I is the information content of the protocol and k is the number of players. We complement this result with an almost matching lower bound of ~Omega(Ik), which shows that a nearly-linear dependence on the number of players cannot be avoided.
Cite as
Gillat Kol, Rotem Oshman, and Dafna Sadeh. Interactive Compression for Multi-Party Protocol. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 31:1-31:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{kol_et_al:LIPIcs.DISC.2017.31,
author = {Kol, Gillat and Oshman, Rotem and Sadeh, Dafna},
title = {{Interactive Compression for Multi-Party Protocol}},
booktitle = {31st International Symposium on Distributed Computing (DISC 2017)},
pages = {31:1--31:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-053-8},
ISSN = {1868-8969},
year = {2017},
volume = {91},
editor = {Richa, Andr\'{e}a},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.31},
URN = {urn:nbn:de:0030-drops-80111},
doi = {10.4230/LIPIcs.DISC.2017.31},
annote = {Keywords: interactive compression, multi-party communication}
}
Document
Self-Stabilising Byzantine Clock Synchronisation is Almost as Easy as Consensus
Abstract
We give fault-tolerant algorithms for establishing synchrony in distributed systems in which each of the n nodes has its own clock. Our algorithms operate in a very strong fault model: we require self-stabilisation, i.e., the initial state of the system may be arbitrary, and there can be up to f<n/3 ongoing Byzantine faults, i.e., nodes that deviate from the protocol in an arbitrary manner. Furthermore, we assume that the local clocks of the nodes may progress at different speeds (clock drift) and communication has bounded delay. In this model, we study the pulse synchronisation problem, where the task is to guarantee that eventually all correct nodes generate well-separated local pulse events (i.e., unlabelled logical clock ticks) in a synchronised manner.
Compared to prior work, we achieve exponential improvements in stabilisation time and the number of communicated bits, and give the first sublinear-time algorithm for the problem:
- In the deterministic setting, the state-of-the-art solutions stabilise in time Theta(f) and have each node broadcast Theta(f log f) bits per time unit. We exponentially reduce the number of bits broadcasted per time unit to Theta(log f) while retaining the same stabilisation time.
- In the randomised setting, the state-of-the-art solutions stabilise in time Theta(f) and have each node broadcast O(1) bits per time unit. We exponentially reduce the stabilisation time to polylog f while each node broadcasts polylog f bits per time unit.
These results are obtained by means of a recursive approach reducing the above task of self-stabilising pulse synchronisation in the bounded-delay model to non-self-stabilising binary consensus in the synchronous model. In general, our approach introduces at most logarithmic overheads in terms of stabilisation time and broadcasted bits over the underlying consensus routine.
Cite as
Christoph Lenzen and Joel Rybicki. Self-Stabilising Byzantine Clock Synchronisation is Almost as Easy as Consensus. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 32:1-32:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{lenzen_et_al:LIPIcs.DISC.2017.32,
author = {Lenzen, Christoph and Rybicki, Joel},
title = {{Self-Stabilising Byzantine Clock Synchronisation is Almost as Easy as Consensus}},
booktitle = {31st International Symposium on Distributed Computing (DISC 2017)},
pages = {32:1--32:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-053-8},
ISSN = {1868-8969},
year = {2017},
volume = {91},
editor = {Richa, Andr\'{e}a},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.32},
URN = {urn:nbn:de:0030-drops-79914},
doi = {10.4230/LIPIcs.DISC.2017.32},
annote = {Keywords: Byzantine faults, self-stabilisation, clock synchronisation, consensus}
}
Document
Neuro-RAM Unit with Applications to Similarity Testing and Compression in Spiking Neural Networks
Abstract
We study distributed algorithms implemented in a simplified biologically inspired model for stochastic spiking neural networks. We focus on tradeoffs between computation time and network complexity, along with the role of noise and randomness in efficient neural computation.
It is widely accepted that neural spike responses, and neural computation in general, is inherently stochastic. In recent work, we explored how this stochasticity could be leveraged to solve the 'winner-take-all' leader election task. Here, we focus on using randomness in neural algorithms for similarity testing and compression. In the most basic setting, given two n-length patterns of firing neurons, we wish to distinguish if the patterns are equal or epsilon-far from equal.
Randomization allows us to solve this task with a very compact network, using O((sqrt(n) log n)/epsilon) auxiliary neurons, which is sublinear in the input size. At the heart of our solution is the design of a t-round neural random access memory, or indexing network, which we call a neuro-RAM. This module can be implemented with O(n/t) auxiliary neurons and is useful in many applications beyond similarity testing - e.g., we discuss its application to compression via random projection.
Using a VC dimension-based argument, we show that the tradeoff between runtime and network size in our neuro-RAM is nearly optimal. To the best of our knowledge, we are the first to apply these techniques to stochastic spiking networks. Our result has several implications - since our neuro-RAM can be implemented with deterministic threshold gates, it demonstrates that, in contrast to similarity testing, randomness does not provide significant computational advantages for this problem. It also establishes a separation between our networks, which spike with a sigmoidal probability function, and well-studied deterministic sigmoidal networks, whose gates output real number values, and which can implement a neuro-RAM much more efficiently.
Cite as
Nancy Lynch, Cameron Musco, and Merav Parter. Neuro-RAM Unit with Applications to Similarity Testing and Compression in Spiking Neural Networks. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 33:1-33:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{lynch_et_al:LIPIcs.DISC.2017.33,
author = {Lynch, Nancy and Musco, Cameron and Parter, Merav},
title = {{Neuro-RAM Unit with Applications to Similarity Testing and Compression in Spiking Neural Networks}},
booktitle = {31st International Symposium on Distributed Computing (DISC 2017)},
pages = {33:1--33:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-053-8},
ISSN = {1868-8969},
year = {2017},
volume = {91},
editor = {Richa, Andr\'{e}a},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.33},
URN = {urn:nbn:de:0030-drops-79863},
doi = {10.4230/LIPIcs.DISC.2017.33},
annote = {Keywords: spiking neural networks, biological distributed algorithms, circuit design}
}
Document
How Large Is Your Graph?
Abstract
We consider the problem of estimating the graph size, where one is given only local access to the graph. We formally define a query model in which one starts with a seed node and is allowed to make queries about neighbours of nodes that have already been seen. In the case of undirected graphs, an estimator of Katzir et al. (2014) based on a sample from the stationary distribution pi uses O(1/||pi||_2 + d_avg) queries; we prove that this is tight. In addition, we establish this as a lower bound even when the algorithm is allowed to crawl the graph arbitrarily; the results of Katzir et al. give an upper bound that is worse by a multiplicative factor t_mix(1/n^4).
The picture becomes significantly different in the case of directed graphs. We show that without strong assumptions on the graph structure, the number of nodes cannot be predicted to within a constant multiplicative factor without using a number of queries that are at least linear in the number of nodes; in particular, rapid mixing and small diameter, properties that most real-world networks exhibit, do not suffice. The question of interest is whether any algorithm can beat breadth-first search. We introduce a new parameter, generalising the well-studied conductance, such that if a suitable bound on it exists and is known to the algorithm, the number of queries required is sublinear in the number of edges; we show that this is tight.
Cite as
Varun Kanade, Frederik Mallmann-Trenn, and Victor Verdugo. How Large Is Your Graph?. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 34:1-34:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{kanade_et_al:LIPIcs.DISC.2017.34,
author = {Kanade, Varun and Mallmann-Trenn, Frederik and Verdugo, Victor},
title = {{How Large Is Your Graph?}},
booktitle = {31st International Symposium on Distributed Computing (DISC 2017)},
pages = {34:1--34:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-053-8},
ISSN = {1868-8969},
year = {2017},
volume = {91},
editor = {Richa, Andr\'{e}a},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.34},
URN = {urn:nbn:de:0030-drops-79767},
doi = {10.4230/LIPIcs.DISC.2017.34},
annote = {Keywords: Estimation, Random Walks, Social Networks}
}
Document
Tight Bounds for Connectivity and Set Agreement in Byzantine Synchronous Systems
Abstract
In this paper, we show that the protocol complex of a Byzantine synchronous system can remain (k-1)-connected for up to ceil(t/k) rounds, where t is the maximum number of Byzantine processes, and t >= k >= 1. This topological property implies that ceil(t/k) + 1 rounds are necessary to solve k-set agreement in Byzantine synchronous systems, compared to floor(t/k) + 1 rounds in synchronous crash-failure systems. We also show that our connectivity bound is tight as we indicate solutions to Byzantine k-set agreement in exactly ceil(t/k) + 1 synchronous rounds, at least when n is suitably large compared to t. In conclusion, we see how Byzantine failures can potentially require one extra round to solve k-set agreement, and, for n suitably large compared to t, at most that.
Cite as
Hammurabi Mendes and Maurice Herlihy. Tight Bounds for Connectivity and Set Agreement in Byzantine Synchronous Systems. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 35:1-35:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{mendes_et_al:LIPIcs.DISC.2017.35,
author = {Mendes, Hammurabi and Herlihy, Maurice},
title = {{Tight Bounds for Connectivity and Set Agreement in Byzantine Synchronous Systems}},
booktitle = {31st International Symposium on Distributed Computing (DISC 2017)},
pages = {35:1--35:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-053-8},
ISSN = {1868-8969},
year = {2017},
volume = {91},
editor = {Richa, Andr\'{e}a},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.35},
URN = {urn:nbn:de:0030-drops-79930},
doi = {10.4230/LIPIcs.DISC.2017.35},
annote = {Keywords: Byzantine, synchronous, k-set agreement, topology, connectivity}
}
Document
Recovering Shared Objects Without Stable Storage
Abstract
This paper considers the problem of building fault-tolerant shared objects when processes can crash and recover but lose their persistent state on recovery. This Diskless Crash-Recovery (DCR) model matches the way many long-lived systems are built. We show that it presents new challenges, as operations that are recorded at a quorum may not persist after some of the processes in that quorum crash and then recover.
To address this problem, we introduce the notion of crash-consistent quorums, where no recoveries happen during the quorum responses. We show that relying on crash-consistent quorums enables a recovery procedure that can recover all operations that successfully finished. Crash-consistent quorums can be easily identified using a mechanism we term the crash vector, which tracks the causal relationship between crashes, recoveries, and other operations.
We apply crash-consistent quorums and crash vectors to build two storage primitives. We give a new algorithm for multi-writer, multi-reader atomic registers in the DCR model that guarantees safety under all conditions and termination under a natural condition. It improves on the best prior protocol for this problem by requiring fewer rounds, fewer nodes to participate in the quorum, and a less restrictive liveness condition. We also present a more efficient single-writer, single-reader atomic set - a virtual stable storage abstraction. It can be used to lift any existing algorithm from the traditional Crash-Recovery model to the DCR model. We examine a specific application, state machine replication, and show that existing diskless protocols can violate their correctness guarantees, while ours offers a general and correct solution.
Cite as
Ellis Michael, Dan R. K. Ports, Naveen Kr. Sharma, and Adriana Szekeres. Recovering Shared Objects Without Stable Storage. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 36:1-36:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{michael_et_al:LIPIcs.DISC.2017.36,
author = {Michael, Ellis and Ports, Dan R. K. and Sharma, Naveen Kr. and Szekeres, Adriana},
title = {{Recovering Shared Objects Without Stable Storage}},
booktitle = {31st International Symposium on Distributed Computing (DISC 2017)},
pages = {36:1--36:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-053-8},
ISSN = {1868-8969},
year = {2017},
volume = {91},
editor = {Richa, Andr\'{e}a},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.36},
URN = {urn:nbn:de:0030-drops-80055},
doi = {10.4230/LIPIcs.DISC.2017.36},
annote = {Keywords: asynchronous system, fault-tolerance, crash-recovery, R/W register, state machine replication}
}
Document
Dalí: A Periodically Persistent Hash Map
Abstract
Technology trends suggest that byte-addressable nonvolatile memory (NVM) will supplant many uses of DRAM over the coming decade, raising the prospect of inexpensive recovery from power failures and similar faults. Ensuring the consistency of persistent state remains nontrivial, however, in the presence of volatile caches; cached values can "leak" back to persistent memory in arbitrary order. To ensure consistency, existing persistent memory algorithms use expensive, explicit write-back instructions to force each value back to memory before performing a dependent write, thereby incurring significant run-time overhead.
To reduce this overhead, we present a new design paradigm that we call periodic persistence. In a periodically persistent data structure, updates are made "in place," but can safely leak back to memory in any order, because only those updates that are known to be valid will be heeded during recovery. To guarantee forward progress, we periodically force a write-back of all dirty data in the cache, ensuring that all "sufficiently old" updates have indeed become persistent, at which point they become semantically visible to the recovery process.
As an example of periodic persistence, we present a transactional hash map, Dalí, together with an informal proof of safety (buffered durable linearizability). Experiments with a prototype implementation suggest that periodic persistence can offer substantially better performance than either file-based or incrementally persistent (per-access write-back) alternatives.
Cite as
Faisal Nawab, Joseph Izraelevitz, Terence Kelly, Charles B. Morrey III, Dhruva R. Chakrabarti, and Michael L. Scott. Dalí: A Periodically Persistent Hash Map. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 37:1-37:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{nawab_et_al:LIPIcs.DISC.2017.37,
author = {Nawab, Faisal and Izraelevitz, Joseph and Kelly, Terence and Morrey III, Charles B. and Chakrabarti, Dhruva R. and Scott, Michael L.},
title = {{Dal{\'\i}: A Periodically Persistent Hash Map}},
booktitle = {31st International Symposium on Distributed Computing (DISC 2017)},
pages = {37:1--37:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-053-8},
ISSN = {1868-8969},
year = {2017},
volume = {91},
editor = {Richa, Andr\'{e}a},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.37},
URN = {urn:nbn:de:0030-drops-80148},
doi = {10.4230/LIPIcs.DISC.2017.37},
annote = {Keywords: data structure, nonvolatile memory, durable linearizability}
}
Document
Symmetry Breaking in the Congest Model: Time- and Message-Efficient Algorithms for Ruling Sets
Abstract
We study local symmetry breaking problems in the Congest model, focusing on ruling set problems, which generalize the fundamental Maximal Independent Set (MIS) problem. The time (round) complexity of MIS (and ruling sets) have attracted much attention in the Local model. Indeed, recent results (Barenboim et al., FOCS 2012, Ghaffari SODA 2016) for the MIS problem have tried to break the long-standing O(log n)-round "barrier" achieved by Luby's algorithm, but these yield o(log n)-round complexity only when the maximum degree Delta is somewhat small relative to n. More importantly, these results apply only in the Local model. In fact, the best known time bound in the Congest model is still O(log n) (via Luby's algorithm) even for moderately small Delta (i.e., for Delta = Omega(log n) and Delta = o(n)). Furthermore, message complexity has been largely ignored in the context of local symmetry breaking. Luby's algorithm takes O(m) messages on m-edge graphs and this is the best known bound with respect to messages. Our work is motivated by the following central question: can we break the Theta(log n) time complexity barrier and the Theta(m) message complexity barrier in the Congest model for MIS or closely-related symmetry breaking problems?
This paper presents progress towards this question for the distributed ruling set problem in the Congest model. A beta-ruling set is an independent set such that every node in the graph is at most beta hops from a node in the independent set. We present the following results:
- Time Complexity: We show that we can break the O(log n) "barrier" for 2- and 3-ruling sets. We compute 3-ruling sets in O(log n/log log n) rounds with high probability (whp). More generally we show that 2-ruling sets can be computed in O(log Delta (log n)^(1/2 + epsilon) + log n/log log n) rounds for any epsilon > 0, which is o(log n) for a wide range of Delta values (e.g., Delta = 2^(log n)^(1/2-epsilon)). These are the first 2- and 3-ruling set algorithms to improve over the O(log n)-round complexity of Luby's algorithm in the Congest model.
- Message Complexity: We show an Omega(n^2) lower bound on the message complexity of computing an MIS (i.e., 1-ruling set) which holds also for randomized algorithms and present a contrast to this by showing a randomized algorithm for 2-ruling sets that, whp, uses only O(n log^2 n) messages and runs in O(Delta log n) rounds. This is the first message-efficient algorithm known for ruling sets, which has message complexity nearly linear in n (which is optimal up to a polylogarithmic factor).
Cite as
Shreyas Pai, Gopal Pandurangan, Sriram V. Pemmaraju, Talal Riaz, and Peter Robinson. Symmetry Breaking in the Congest Model: Time- and Message-Efficient Algorithms for Ruling Sets. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 38:1-38:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{pai_et_al:LIPIcs.DISC.2017.38,
author = {Pai, Shreyas and Pandurangan, Gopal and Pemmaraju, Sriram V. and Riaz, Talal and Robinson, Peter},
title = {{Symmetry Breaking in the Congest Model: Time- and Message-Efficient Algorithms for Ruling Sets}},
booktitle = {31st International Symposium on Distributed Computing (DISC 2017)},
pages = {38:1--38:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-053-8},
ISSN = {1868-8969},
year = {2017},
volume = {91},
editor = {Richa, Andr\'{e}a},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.38},
URN = {urn:nbn:de:0030-drops-80132},
doi = {10.4230/LIPIcs.DISC.2017.38},
annote = {Keywords: Congest model, Local model, Maximal independent set, Message complexity, Round complexity, Ruling sets, Symmetry breaking}
}
Document
Hybrid Consensus: Efficient Consensus in the Permissionless Model
Abstract
Consensus, or state machine replication is a foundational building block of distributed systems and modern cryptography. Consensus in the classical, "permissioned" setting has been extensively studied in the 30 years of distributed systems literature. Recent developments in Bitcoin and other decentralized cryptocurrencies popularized a new form of consensus in a "permissionless" setting, where anyone can join and leave dynamically, and there is no a-priori knowledge of the number of consensus nodes. So far, however, all known permissionless consensus protocols assume network synchrony, i.e., the protocol must know an upper bound of the network's delay, and transactions confirm slower than this a-priori upper bound.
We initiate the study of the feasibilities and infeasibilities of achieving responsiveness in permissionless consensus. In a responsive protocol, the transaction confirmation time depends only on the actual network delay, but not on any a-priori known upper bound such as a synchronous round. Classical protocols in the partial synchronous and asynchronous models naturally achieve responsiveness, since the protocol does not even know any delay upper bound. Unfortunately, we show that in the permissionless setting, consensus is impossible in the asynchronous or partially synchronous models.
On the positive side, we construct a protocol called Hybrid Consensus by combining classical-style and blockchain-style consensus. Hybrid Consensus shows that responsiveness is nonetheless possible to achieve in permissionless consensus (assuming proof-of-work) when 1) the protocol knows an upper bound on the network delay; 2) we allow a non-responsive warmup period after which transaction confirmation can become responsive; 3) honesty has some stickiness, i.e., it takes a short while for an adversary to corrupt a node or put it to sleep; and 4) less than 1/3 of the nodes are corrupt. We show that all these conditions are in fact necessary - if only one of them is violated, responsiveness would have been impossible. Our work makes a step forward in our understanding of the permissionless model and its differences and relations to classical consensus.
Cite as
Rafael Pass and Elaine Shi. Hybrid Consensus: Efficient Consensus in the Permissionless Model. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 39:1-39:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{pass_et_al:LIPIcs.DISC.2017.39,
author = {Pass, Rafael and Shi, Elaine},
title = {{Hybrid Consensus: Efficient Consensus in the Permissionless Model}},
booktitle = {31st International Symposium on Distributed Computing (DISC 2017)},
pages = {39:1--39:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-053-8},
ISSN = {1868-8969},
year = {2017},
volume = {91},
editor = {Richa, Andr\'{e}a},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.39},
URN = {urn:nbn:de:0030-drops-80040},
doi = {10.4230/LIPIcs.DISC.2017.39},
annote = {Keywords: Distributed Consensus, Permissionless, Responsiveness}
}
Document
Dynamic Reconfiguration: Abstraction and Optimal Asynchronous Solution
Abstract
Providing clean and efficient foundations and tools for reconfiguration is a crucial enabler for distributed system management today. This work takes a step towards developing such foundations. It considers classic fault-tolerant atomic objects emulated on top of a static set of fault-prone servers, and turns them into dynamic ones. The specification of a dynamic object extends the corresponding static (non-dynamic) one with an API for changing the underlying set of fault-prone servers. Thus, in a dynamic model, an object can start in some configuration and continue in a different one. Its liveness is preserved through the reconfigurations it undergoes, tolerating a versatile set of faults as it shifts from one configuration to another.
In this paper we present a general abstraction for asynchronous reconfiguration, and exemplify its usefulness for building two dynamic objects: a read/write register and a max-register. We first define a dynamic model with a clean failure condition that allows an administrator to reconfigure the system and switch off a server once the reconfiguration operation removing it completes. We then define the Reconfiguration abstraction and show how it can be used to build dynamic registers and max-registers. Finally, we give an optimal asynchronous algorithm implementing the Reconfiguration abstraction, which in turn leads to the first asynchronous (consensus-free) dynamic register emulation with optimal complexity. More concretely, faced with n requests for configuration changes, the number of configurations that the dynamic register is implemented over is n; and the complexity of each client operation is O(n).
Cite as
Alexander Spiegelman, Idit Keidar, and Dahlia Malkhi. Dynamic Reconfiguration: Abstraction and Optimal Asynchronous Solution. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 40:1-40:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{spiegelman_et_al:LIPIcs.DISC.2017.40,
author = {Spiegelman, Alexander and Keidar, Idit and Malkhi, Dahlia},
title = {{Dynamic Reconfiguration: Abstraction and Optimal Asynchronous Solution}},
booktitle = {31st International Symposium on Distributed Computing (DISC 2017)},
pages = {40:1--40:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-053-8},
ISSN = {1868-8969},
year = {2017},
volume = {91},
editor = {Richa, Andr\'{e}a},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.40},
URN = {urn:nbn:de:0030-drops-79673},
doi = {10.4230/LIPIcs.DISC.2017.40},
annote = {Keywords: Reconfiguration, Dynamic Objects, Optimal Algorithm}
}
Document
Brief Announcement
Brief Announcement: Practical Synchronous Byzantine Consensus
Abstract
This paper presents new protocols for Byzantine state machine replication and Byzantine agreement in the synchronous and authenticated setting. The PBFT state machine replication protocol tolerates f Byzantine faults in an asynchronous setting using n = 3f + 1 replicas. We improve the Byzantine fault tolerance to n = 2f + 1 by utilizing the synchrony assumption. Our protocol also solves synchronous authenticated Byzantine agreement in fewer expected rounds than the best existing solution (Katz and Koo, 2006).
Cite as
Ittai Abraham, Srinivas Devadas, Kartik Nayak, and Ling Ren. Brief Announcement: Practical Synchronous Byzantine Consensus. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 41:1-41:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{abraham_et_al:LIPIcs.DISC.2017.41,
author = {Abraham, Ittai and Devadas, Srinivas and Nayak, Kartik and Ren, Ling},
title = {{Brief Announcement: Practical Synchronous Byzantine Consensus}},
booktitle = {31st International Symposium on Distributed Computing (DISC 2017)},
pages = {41:1--41:4},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-053-8},
ISSN = {1868-8969},
year = {2017},
volume = {91},
editor = {Richa, Andr\'{e}a},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.41},
URN = {urn:nbn:de:0030-drops-79703},
doi = {10.4230/LIPIcs.DISC.2017.41},
annote = {Keywords: consensus, agreement, Byzantine fault tolerance, replication, synchrony}
}
Document
Brief Announcement
Brief Announcement: The Synergy of Finite State Machines
Abstract
What can be computed by a network of n randomized finite state machines communicating under the stone age model (a generalization of the beeping model’s communication scheme)? The inherent linear upper bound on the total space of the network implies that its global computational power is not larger than that of a randomized linear space Turing machine, but is this tight? The reported reseach answers this question affirmatively for bounded degree networks by introducing a stone age algorithm (operating under the most restrictive form of the model) that given a designated I/O node, constructs a tour in the network that enables the simulation of the Turing machine’s tape. To construct the tour, it is first shown how to 2-hop color the network concurrently with building a spanning tree with high probability.
Cite as
Yehuda Afek, Yuval Emek, and Noa Kolikant. Brief Announcement: The Synergy of Finite State Machines. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 42:1-42:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{afek_et_al:LIPIcs.DISC.2017.42,
author = {Afek, Yehuda and Emek, Yuval and Kolikant, Noa},
title = {{Brief Announcement: The Synergy of Finite State Machines}},
booktitle = {31st International Symposium on Distributed Computing (DISC 2017)},
pages = {42:1--42:3},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-053-8},
ISSN = {1868-8969},
year = {2017},
volume = {91},
editor = {Richa, Andr\'{e}a},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.42},
URN = {urn:nbn:de:0030-drops-80072},
doi = {10.4230/LIPIcs.DISC.2017.42},
annote = {Keywords: beeping communication, finite state machine, stone age model, distributed network complexity}
}
Document
Brief Announcement
Brief Announcement: Compact Self-Stabilizing Leader Election in Arbitrary Graphs
Abstract
We present the first self-stabilizing algorithm for leader election in arbitrary topologies whose space complexity is O(max{log Delta, log log n}) bits per node, where n is the network size and Delta its degree. This complexity is sub-logarithmic in n when Delta = n^o(1).
Cite as
Lélia Blin and Sébastien Tixeuil. Brief Announcement: Compact Self-Stabilizing Leader Election in Arbitrary Graphs. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 43:1-43:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{blin_et_al:LIPIcs.DISC.2017.43,
author = {Blin, L\'{e}lia and Tixeuil, S\'{e}bastien},
title = {{Brief Announcement: Compact Self-Stabilizing Leader Election in Arbitrary Graphs}},
booktitle = {31st International Symposium on Distributed Computing (DISC 2017)},
pages = {43:1--43:3},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-053-8},
ISSN = {1868-8969},
year = {2017},
volume = {91},
editor = {Richa, Andr\'{e}a},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.43},
URN = {urn:nbn:de:0030-drops-79829},
doi = {10.4230/LIPIcs.DISC.2017.43},
annote = {Keywords: Leader Election, Self-stabilization, Memory Complexity, Arbitrary Graphs}
}
Document
Brief Announcement
Brief Announcement: A Note on Hardness of Diameter Approximation
Abstract
We revisit the hardness of approximating the diameter of a network. In the CONGEST model, ~Omega(n) rounds are necessary to compute the diameter [Frischknecht et al. SODA'12]. Abboud et al. [DISC 2016] extended this result to sparse graphs and, at a more fine-grained level, showed that, for any integer 1 <= l <= polylog(n) , distinguishing between networks of diameter 4l + 2 and 6l + 1 requires ~Omega(n) rounds. We slightly tighten this result by showing that even distinguishing between diameter 2l + 1 and 3l + 1 requires ~Omega(n) rounds. The reduction of Abboud et al. is inspired by recent conditional lower bounds in the RAM model, where the orthogonal vectors problem plays a pivotal role. In our new lower bound, we make the connection to orthogonal vectors explicit, leading to a conceptually more streamlined exposition. This is suited for teaching both the lower bound in the CONGEST model and the conditional lower bound in the RAM model.
Cite as
Karl Bringmann and Sebastian Krinninger. Brief Announcement: A Note on Hardness of Diameter Approximation. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 44:1-44:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{bringmann_et_al:LIPIcs.DISC.2017.44,
author = {Bringmann, Karl and Krinninger, Sebastian},
title = {{Brief Announcement: A Note on Hardness of Diameter Approximation}},
booktitle = {31st International Symposium on Distributed Computing (DISC 2017)},
pages = {44:1--44:3},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-053-8},
ISSN = {1868-8969},
year = {2017},
volume = {91},
editor = {Richa, Andr\'{e}a},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.44},
URN = {urn:nbn:de:0030-drops-79874},
doi = {10.4230/LIPIcs.DISC.2017.44},
annote = {Keywords: diameter, fine-grained reductions, conditional lower bounds}
}
Document
Brief Announcement
Brief Announcement: Black-Box Concurrent Data Structures for NUMA Architectures
Abstract
Recent work introduced a method to automatically produce concurrent data structures for NUMA architectures. We present a summary of that work.
Cite as
Irina Calciu, Siddhartha Sen, Mahesh Balakrishnan, and Marcos K. Aguilera. Brief Announcement: Black-Box Concurrent Data Structures for NUMA Architectures. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 45:1-45:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{calciu_et_al:LIPIcs.DISC.2017.45,
author = {Calciu, Irina and Sen, Siddhartha and Balakrishnan, Mahesh and Aguilera, Marcos K.},
title = {{Brief Announcement: Black-Box Concurrent Data Structures for NUMA Architectures}},
booktitle = {31st International Symposium on Distributed Computing (DISC 2017)},
pages = {45:1--45:3},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-053-8},
ISSN = {1868-8969},
year = {2017},
volume = {91},
editor = {Richa, Andr\'{e}a},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.45},
URN = {urn:nbn:de:0030-drops-80122},
doi = {10.4230/LIPIcs.DISC.2017.45},
annote = {Keywords: concurrent data structures, log, NUMA architecture, replication}
}
Document
Brief Announcement
Brief Announcement: Crash-Tolerant Consensus in Directed Graph Revisited
Abstract
We revisit the problem of distributed consensus in directed graphs tolerating crash failures; we improve the round and communication complexity of the existing protocols. Moreover, we prove that our protocol requires the optimal number of communication rounds, required by any protocol belonging to a specific class of crash-tolerant consensus protocols in directed graphs.
Cite as
Ashish Choudhury, Gayathri Garimella, Arpita Patra, Divya Ravi, and Pratik Sarkar. Brief Announcement: Crash-Tolerant Consensus in Directed Graph Revisited. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 46:1-46:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{choudhury_et_al:LIPIcs.DISC.2017.46,
author = {Choudhury, Ashish and Garimella, Gayathri and Patra, Arpita and Ravi, Divya and Sarkar, Pratik},
title = {{Brief Announcement: Crash-Tolerant Consensus in Directed Graph Revisited}},
booktitle = {31st International Symposium on Distributed Computing (DISC 2017)},
pages = {46:1--46:4},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-053-8},
ISSN = {1868-8969},
year = {2017},
volume = {91},
editor = {Richa, Andr\'{e}a},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.46},
URN = {urn:nbn:de:0030-drops-79784},
doi = {10.4230/LIPIcs.DISC.2017.46},
annote = {Keywords: Directed graph, Consensus, Crash failure, Round complexity}
}
Document
Brief Announcement
Brief Announcement: On the Parallel Undecided-State Dynamics with Two Colors
Abstract
The Undecided-State Dynamics is a well-known protocol that achieves Consensus in distributed systems formed by a set of n anonymous nodes interacting via a communication network. We consider this dynamics in the parallel PULL communication model on the complete graph for the binary case, i.e., when every node can either support one of two possible colors or stay in the undecided state. Previous work in this setting only considers initial color configurations with no undecided nodes and a large bias (i.e., Theta(n)) towards the majority color. A interesting open question here is whether this dynamics reaches consensus quickly, i.e. within a polylogarithmic number of rounds. In this paper we present an unconditional analysis of the Undecided-State Dynamics which answers to the above question in the affirmative. Our analysis shows that, starting from any initial configuration, the Undecided-State Dynamics reaches a monochromatic configuration within O(log^2 n) rounds, with high probability (w.h.p.). Moreover, we prove that if the initial configuration has bias Omega(sqrt(n log n)), then the dynamics converges toward the initial majority color within O(log n) round, w.h.p. At the heart of our approach there is a new analysis of the symmetry-breaking phase that the process must perform in order to escape from (almost-)unbiased configurations. Previous symmetry-breaking analysis of consensus dynamics essentially concern sequential communication models (such as Population Protocols) and/or symmetric updated rules (such as majority rules).
Cite as
Andrea Clementi, Luciano Gualà, Francesco Pasquale, and Giacomo Scornavacca. Brief Announcement: On the Parallel Undecided-State Dynamics with Two Colors. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 47:1-47:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{clementi_et_al:LIPIcs.DISC.2017.47,
author = {Clementi, Andrea and Gual\`{a}, Luciano and Pasquale, Francesco and Scornavacca, Giacomo},
title = {{Brief Announcement: On the Parallel Undecided-State Dynamics with Two Colors}},
booktitle = {31st International Symposium on Distributed Computing (DISC 2017)},
pages = {47:1--47:4},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-053-8},
ISSN = {1868-8969},
year = {2017},
volume = {91},
editor = {Richa, Andr\'{e}a},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.47},
URN = {urn:nbn:de:0030-drops-79724},
doi = {10.4230/LIPIcs.DISC.2017.47},
annote = {Keywords: Distributed Consensus, Dynamics, Gossip model, Markov chains}
}
Document
Brief Announcement
Brief Announcement: Shape Formation by Programmable Particles
Abstract
Shape formation is a basic distributed problem for systems of computational mobile entities. Intensively studied for systems of autonomous mobile robots, it has recently been investigated in the realm of programmable matter. Namely, it has been studied in the geometric Amoebot model, where the anonymous entities, called particles, operate on a hexagonal tessellation of the plane, have constant memory, can only communicate with neighboring particles, and can only move from a grid node to an empty neighboring node; their activation is controlled by an adversarial scheduler. Recent investigations have shown how, starting from a well-structured configuration in which the particles form a (not necessarily complete) triangle, the particles can form a large class of shapes. This result has been established under several assumptions: agreement on the clockwise direction (i.e., chirality), a sequential activation schedule, and randomization.
In this paper we provide a characterization of which shapes can be formed deterministically starting from any simply connected initial configuration of n particles. As a byproduct, if randomization is allowed, then any input shape can be formed from any initial (simply connected) shape by our algorithm, provided that n is large enough. Our algorithm works without chirality, proving that chirality is computationally irrelevant for shape formation. Furthermore, it works under a strong adversarial scheduler, not necessarily sequential. We also consider the complexity of shape formation both in terms of the number of rounds and the total number of moves performed by the particles executing a universal shape formation algorithm. We prove that our solution has a complexity of O(n^2) rounds and moves: this number of moves is also asymptotically optimal.
Cite as
Giuseppe A. Di Luna, Paola Flocchini, Nicola Santoro, Giovanni Viglietta, and Yukiko Yamauchi. Brief Announcement: Shape Formation by Programmable Particles. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 48:1-48:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{diluna_et_al:LIPIcs.DISC.2017.48,
author = {Di Luna, Giuseppe A. and Flocchini, Paola and Santoro, Nicola and Viglietta, Giovanni and Yamauchi, Yukiko},
title = {{Brief Announcement: Shape Formation by Programmable Particles}},
booktitle = {31st International Symposium on Distributed Computing (DISC 2017)},
pages = {48:1--48:3},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-053-8},
ISSN = {1868-8969},
year = {2017},
volume = {91},
editor = {Richa, Andr\'{e}a},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.48},
URN = {urn:nbn:de:0030-drops-80019},
doi = {10.4230/LIPIcs.DISC.2017.48},
annote = {Keywords: Shape formation, pattern formation, programmable matter, Amoebots, leader election, distributed algorithms, self-assembly}
}
Document
Brief Announcement
Brief Announcement: Fast Aggregation in Population Protocols
Abstract
The coalescence protocol plays an important role in the population protocol model. The conceptual structure of the protocol is for two agents holding two non-zero values a, b respectively to take a transition (a,b) -> (a+b, 0), where + is an arbitrary commutative binary operation. Obviously, it eventually aggregates the sum of all initial values. In this paper, we present a fast coalescence protocol that converges in O(sqrt(n) log^2 n) parallel time with high probability in the model with an initial leader (equivalently, the model with a base station), which achieves an substantial speed-up compared with the naive implementation taking Omega(n) time.
Cite as
Ryota Eguchi and Taisuke Izumi. Brief Announcement: Fast Aggregation in Population Protocols. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 49:1-49:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{eguchi_et_al:LIPIcs.DISC.2017.49,
author = {Eguchi, Ryota and Izumi, Taisuke},
title = {{Brief Announcement: Fast Aggregation in Population Protocols}},
booktitle = {31st International Symposium on Distributed Computing (DISC 2017)},
pages = {49:1--49:3},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-053-8},
ISSN = {1868-8969},
year = {2017},
volume = {91},
editor = {Richa, Andr\'{e}a},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.49},
URN = {urn:nbn:de:0030-drops-79981},
doi = {10.4230/LIPIcs.DISC.2017.49},
annote = {Keywords: population protocol, aggregation}
}
Document
Brief Announcement
Brief Announcement: A Persistent Lock-Free Queue for Non-Volatile Memory
Abstract
Non-volatile memory is expected to coexist with (or even displace) volatile DRAM for main memory in upcoming architectures. As a result, there is increasing interest in the problem of designing and specifying durable data structures that can recover from system crashes. Data-structures may be designed to satisfy stricter or weaker durability guarantees to provide a balance between the strength of the provided guarantees and performance overhead.
This paper proposes three novel implementations of a concurrent lock-free queue. These implementations illustrate the algorithmic challenges in building persistent lock-free data structures with different levels of durability guarantees. We believe that by presenting these challenges, along with the proposed algorithmic designs, and the possible levels of durability guarantees, we can shed light on avenues for building a wide variety of durable data structures. We implemented the various designs and evaluate their performance overhead compared to a simple queue design for standard (volatile) memory.
Cite as
Michal Friedman, Maurice Herlihy, Virendra Marathe, and Erez Petrank. Brief Announcement: A Persistent Lock-Free Queue for Non-Volatile Memory. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 50:1-50:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{friedman_et_al:LIPIcs.DISC.2017.50,
author = {Friedman, Michal and Herlihy, Maurice and Marathe, Virendra and Petrank, Erez},
title = {{Brief Announcement: A Persistent Lock-Free Queue for Non-Volatile Memory}},
booktitle = {31st International Symposium on Distributed Computing (DISC 2017)},
pages = {50:1--50:4},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-053-8},
ISSN = {1868-8969},
year = {2017},
volume = {91},
editor = {Richa, Andr\'{e}a},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.50},
URN = {urn:nbn:de:0030-drops-79689},
doi = {10.4230/LIPIcs.DISC.2017.50},
annote = {Keywords: Non-volatile Memory, Concurrent Data Structures, Non-blocking, Lock-free}
}
Document
Brief Announcement
Brief Announcement: Lower Bounds for Asymptotic Consensus in Dynamic Networks
Abstract
In this work we study the performance of asymptotic and approximate consensus algorithms in dynamic networks. The asymptotic consensus problem requires a set of agents to repeatedly set their outputs such that the outputs converge to a common value within the convex hull of initial values. This problem, and the related approximate consensus problem, are fundamental building blocks in distributed systems where exact consensus among agents is not required, e.g., man-made distributed control systems, and have applications in the analysis of natural distributed systems, such as flocking and opinion dynamics. We prove new nontrivial lower bounds on the contraction rates of asymptotic consensus algorithms, from which we deduce lower bounds on the time complexity of approximate consensus algorithms. In particular, the obtained bounds show optimality of asymptotic and approximate consensus algorithms presented in [Charron-Bost et al., ICALP'16] for certain classes of networks that include classical failure assumptions, and confine the search for optimal bounds in the general case.
Central to our lower bound proofs is an extended notion of valency, the set of reachable limits of an asymptotic consensus algorithm starting from a given configuration. We further relate topological properties of valencies to the solvability of exact consensus, shedding some light on the relation of these three fundamental problems in dynamic networks.
Cite as
Matthias Függer, Thomas Nowak, and Manfred Schwarz. Brief Announcement: Lower Bounds for Asymptotic Consensus in Dynamic Networks. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 51:1-51:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{fugger_et_al:LIPIcs.DISC.2017.51,
author = {F\"{u}gger, Matthias and Nowak, Thomas and Schwarz, Manfred},
title = {{Brief Announcement: Lower Bounds for Asymptotic Consensus in Dynamic Networks}},
booktitle = {31st International Symposium on Distributed Computing (DISC 2017)},
pages = {51:1--51:3},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-053-8},
ISSN = {1868-8969},
year = {2017},
volume = {91},
editor = {Richa, Andr\'{e}a},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.51},
URN = {urn:nbn:de:0030-drops-79921},
doi = {10.4230/LIPIcs.DISC.2017.51},
annote = {Keywords: Asymptotic Consensus, Dynamic Networks, Contraction Rate, Time Commplexity, Lower Bounds}
}
Document
Brief Announcement
Brief Announcement: Applying Predicate Detection to the Stable Marriage Problem
Abstract
We show that many techniques developed in the context of predicate detection are applicable to the stable marriage problem. The standard Gale-Shapley algorithm can be derived as a special case of detecting linear predicates. We also show that techniques in computation slicing can be used to represent the set of all constrained stable matchings.
Cite as
Vijay K. Garg. Brief Announcement: Applying Predicate Detection to the Stable Marriage Problem. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 52:1-52:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{garg:LIPIcs.DISC.2017.52,
author = {Garg, Vijay K.},
title = {{Brief Announcement: Applying Predicate Detection to the Stable Marriage Problem}},
booktitle = {31st International Symposium on Distributed Computing (DISC 2017)},
pages = {52:1--52:3},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-053-8},
ISSN = {1868-8969},
year = {2017},
volume = {91},
editor = {Richa, Andr\'{e}a},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.52},
URN = {urn:nbn:de:0030-drops-79719},
doi = {10.4230/LIPIcs.DISC.2017.52},
annote = {Keywords: Stable Matching, Linear Predicates, Distributive Lattices}
}
Document
Brief Announcement
Brief Announcement: Towards Reduced Instruction Sets for Synchronization
Abstract
Contrary to common belief, a recent work by Ellen, Gelashvili, Shavit, and Zhu has shown that computability does not require multicore architectures to support "strong" synchronization instructions like compare-and-swap, as opposed to combinations of "weaker" instructions like decrement and multiply. However, this is the status quo, and in turn, most efficient concurrent data-structures heavily rely on compare-and-swap (e.g. for swinging pointers).
We show that this need not be the case, by designing and implementing a concurrent linearizable Log data-structure (also known as a History object), supporting two operations: append(item), which appends the item to the log, and get-log(), which returns the appended items so far, in order. Readers are wait-free and writers are lock-free, hence this data-structure can be used in a lock-free universal construction to implement any concurrent object with a given sequential specification. Our implementation uses atomic read, xor, decrement, and fetch-and-increment instructions supported on X86 architectures, and provides similar performance to a compare-and-swap-based solution on today's hardware. This raises a fundamental question about minimal set of synchronization instructions that the architectures have to support.
Cite as
Rati Gelashvili, Idit Keidar, Alexander Spiegelman, and Roger Wattenhofer. Brief Announcement: Towards Reduced Instruction Sets for Synchronization. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 53:1-53:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{gelashvili_et_al:LIPIcs.DISC.2017.53,
author = {Gelashvili, Rati and Keidar, Idit and Spiegelman, Alexander and Wattenhofer, Roger},
title = {{Brief Announcement: Towards Reduced Instruction Sets for Synchronization}},
booktitle = {31st International Symposium on Distributed Computing (DISC 2017)},
pages = {53:1--53:4},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-053-8},
ISSN = {1868-8969},
year = {2017},
volume = {91},
editor = {Richa, Andr\'{e}a},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.53},
URN = {urn:nbn:de:0030-drops-80201},
doi = {10.4230/LIPIcs.DISC.2017.53},
annote = {Keywords: Consensus hierarchy, universal construction, synchronization instruction.}
}
Document
Brief Announcement
Brief Announcement: On Connectivity in the Broadcast Congested Clique
Abstract
Recently, very fast deterministic and randomized algorithms have been obtained for connectivity and minimum spanning tree in the unicast congested clique. In contrast, no solution faster than a simple parallel implementation of the Boruvka's algorithm has been known for both problems in the broadcast congested clique. In this announcement, we present the first sub-logarithmic deterministic algorithm for connected components in the broadcast congested clique.
Cite as
Tomasz Jurdzínski and Krzysztof Nowicki. Brief Announcement: On Connectivity in the Broadcast Congested Clique. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 54:1-54:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{jurdzinski_et_al:LIPIcs.DISC.2017.54,
author = {Jurdz{\'\i}nski, Tomasz and Nowicki, Krzysztof},
title = {{Brief Announcement: On Connectivity in the Broadcast Congested Clique}},
booktitle = {31st International Symposium on Distributed Computing (DISC 2017)},
pages = {54:1--54:4},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-053-8},
ISSN = {1868-8969},
year = {2017},
volume = {91},
editor = {Richa, Andr\'{e}a},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.54},
URN = {urn:nbn:de:0030-drops-79903},
doi = {10.4230/LIPIcs.DISC.2017.54},
annote = {Keywords: congested clique, broadcast, connected components, bandwidth}
}
Document
Brief Announcement
Brief Announcement: Towards a Complexity Theory for the Congested Clique
Abstract
The congested clique model of distributed computing has been receiving attention as a model for densely connected distributed systems. While there has been significant progress on the side of upper bounds, we have very little in terms of lower bounds for the congested clique; indeed, it is now know that proving explicit congested clique lower bounds is as difficult as proving circuit lower bounds. In this work, we use traditional complexity-theoretic tools to build a clearer picture of the complexity landscape of the congested clique, proving non-constructive lower bounds and studying the relationships between natural problems.
Cite as
Janne H. Korhonen and Jukka Suomela. Brief Announcement: Towards a Complexity Theory for the Congested Clique. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 55:1-55:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{korhonen_et_al:LIPIcs.DISC.2017.55,
author = {Korhonen, Janne H. and Suomela, Jukka},
title = {{Brief Announcement: Towards a Complexity Theory for the Congested Clique}},
booktitle = {31st International Symposium on Distributed Computing (DISC 2017)},
pages = {55:1--55:3},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-053-8},
ISSN = {1868-8969},
year = {2017},
volume = {91},
editor = {Richa, Andr\'{e}a},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.55},
URN = {urn:nbn:de:0030-drops-79889},
doi = {10.4230/LIPIcs.DISC.2017.55},
annote = {Keywords: distributed computing, congested clique, complexity theory}
}
Document
Brief Announcement
Brief Announcement: Compact Topology of Shared-Memory Adversaries
Abstract
The paper proposes a simple topological characterization of a large class of adversarial distributed-computing models via affine tasks: sub-complexes of the second iteration of the standard chromatic subdivision. We show that the task computability of a model in the class is precisely captured by iterations of the corresponding affine task. While an adversary is in general defined as a non-compact set of infinite runs, its affine task is just a finite subset of runs of the 2-round iterated immediate snapshot (IIS) model. Our results generalize and improve all previously derived topological characterizations of distributed-computing models.
Cite as
Petr Kuznetsov, Thibault Rieutord, and Yuan He. Brief Announcement: Compact Topology of Shared-Memory Adversaries. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 56:1-56:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{kuznetsov_et_al:LIPIcs.DISC.2017.56,
author = {Kuznetsov, Petr and Rieutord, Thibault and He, Yuan},
title = {{Brief Announcement: Compact Topology of Shared-Memory Adversaries}},
booktitle = {31st International Symposium on Distributed Computing (DISC 2017)},
pages = {56:1--56:4},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-053-8},
ISSN = {1868-8969},
year = {2017},
volume = {91},
editor = {Richa, Andr\'{e}a},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.56},
URN = {urn:nbn:de:0030-drops-80108},
doi = {10.4230/LIPIcs.DISC.2017.56},
annote = {Keywords: Adversarial models, Affine tasks, Topological characterization}
}
Document
Brief Announcement
Brief Announcement: A Centralized Local Algorithm for the Sparse Spanning Graph Problem
Abstract
Constructing a sparse spanning subgraph is a fundamental primitive in graph theory. In this paper, we study this problem in the Centralized Local model, where the goal is to decide whether an edge is part of the spanning subgraph by examining only a small part of the input; yet, answers must be globally consistent and independent of prior queries.
Unfortunately, maximally sparse spanning subgraphs, i.e., spanning trees, cannot be constructed efficiently in this model. Therefore, we settle for a spanning subgraph containing at most (1+epsilon)n edges (where n is the number of vertices and epsilon is a given approximation/sparsity parameter). We achieve a query complexity of O(poly(Delta/epsilon)n^(2/3)) (up to polylogarithmic factors in n) where Delta is the maximum degree of the input graph. Our algorithm is the first to do so on arbitrary bounded degree graphs. Moreover, we achieve the additional property that our algorithm outputs a spanner, i.e., distances are approximately preserved. With high probability, for each deleted edge there is a path of O(log n (Delta+log n)/epsilon) hops in the output that connects its endpoints.
Cite as
Christoph Lenzen and Reut Levi. Brief Announcement: A Centralized Local Algorithm for the Sparse Spanning Graph Problem. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 57:1-57:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{lenzen_et_al:LIPIcs.DISC.2017.57,
author = {Lenzen, Christoph and Levi, Reut},
title = {{Brief Announcement: A Centralized Local Algorithm for the Sparse Spanning Graph Problem}},
booktitle = {31st International Symposium on Distributed Computing (DISC 2017)},
pages = {57:1--57:3},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-053-8},
ISSN = {1868-8969},
year = {2017},
volume = {91},
editor = {Richa, Andr\'{e}a},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.57},
URN = {urn:nbn:de:0030-drops-80064},
doi = {10.4230/LIPIcs.DISC.2017.57},
annote = {Keywords: local, spanning graph, sparse}
}
Document
Brief Announcement
Brief Announcement: Distributed SplayNets
Abstract
SplayNets are reconfigurable networks which adjust to the communication pattern over time. We present DiSplayNets, a distributed (concurrent and decentralized) implementation of SplayNets.
Cite as
Bruna S. Peres, Olga Goussevskaia, Stefan Schmid, and Chen Avin. Brief Announcement: Distributed SplayNets. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 58:1-58:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{peres_et_al:LIPIcs.DISC.2017.58,
author = {Peres, Bruna S. and Goussevskaia, Olga and Schmid, Stefan and Avin, Chen},
title = {{Brief Announcement: Distributed SplayNets}},
booktitle = {31st International Symposium on Distributed Computing (DISC 2017)},
pages = {58:1--58:3},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-053-8},
ISSN = {1868-8969},
year = {2017},
volume = {91},
editor = {Richa, Andr\'{e}a},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.58},
URN = {urn:nbn:de:0030-drops-79661},
doi = {10.4230/LIPIcs.DISC.2017.58},
annote = {Keywords: Decentralization, Concurrency, Reconfigurable Networks}
}
Document
Brief Announcement
Brief Announcement: Rapid Mixing of Local Dynamics on Graphs
Abstract
In peer-to-peer networks, it is desirable that the logical topology of connections between the constituting nodes make a well-connected graph, i.e., a graph with low diameter and high expansion. At the same time, this graph should evolve only through local modifications. These requirements prompt the following question: are there local graph dynamics that i) create a well-connected graph in equilibrium, and ii) converge rapidly to this equilibrium?
In this paper we provide an affirmative answer by exhibiting a local graph dynamic that mixes provably fast. Specifically, for a graph on N nodes, mixing has occurred after each node has performed O(polylog(N)) operations. This is in contrast with previous results, which required at least Omega(N polylog(N)) operations per node before the graph had properly mixed.
Cite as
Laurent Massoulié and Rémi Varloot. Brief Announcement: Rapid Mixing of Local Dynamics on Graphs. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 59:1-59:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{massoulie_et_al:LIPIcs.DISC.2017.59,
author = {Massouli\'{e}, Laurent and Varloot, R\'{e}mi},
title = {{Brief Announcement: Rapid Mixing of Local Dynamics on Graphs}},
booktitle = {31st International Symposium on Distributed Computing (DISC 2017)},
pages = {59:1--59:3},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-053-8},
ISSN = {1868-8969},
year = {2017},
volume = {91},
editor = {Richa, Andr\'{e}a},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.59},
URN = {urn:nbn:de:0030-drops-79649},
doi = {10.4230/LIPIcs.DISC.2017.59},
annote = {Keywords: Markov chains, Mixing time, Dynamic graphs, Local dynamics}
}