We present a simple deterministic distributed (2 vertical bar c) approximation algorithm for minimum weight vertex cover, which Delta completes in O(log Delta/epsilon log log A) rounds, where A is the maximum degree i...
详细信息
ISBN:
(纸本)9781450339643
We present a simple deterministic distributed (2 vertical bar c) approximation algorithm for minimum weight vertex cover, which Delta completes in O(log Delta/epsilon log log A) rounds, where A is the maximum degree in the graph, for any epsilon > 0 which is at most O(1). For a constant c, this implies a constant approximation in O(log Delta/ log log Delta) rounds, which contradicts the lower bound of [KMW10].
This paper presents the first (non-trivial) distributed planar embedding algorithm. We consider this a crucial first step in a broader program to design efficient distributed algorithms for planar networks. We work in...
详细信息
ISBN:
(纸本)9781450339643
This paper presents the first (non-trivial) distributed planar embedding algorithm. We consider this a crucial first step in a broader program to design efficient distributed algorithms for planar networks. We work in the standard distributed model in which nodes can send an O (log n)-bit message to each of their neighbors per round. In a planar network, with n nodes and diameter D, our deterministic planar embedding algorithm uses O (D . min{log n, D}) rounds to compute a combinatorial planar embedding, which consists of each node knowing the clockwise order of its incident edges in a fixed planar drawing. The complexity of our algorithm is near-optimal and matches the trivial lower bound of Omega(D) up to a log n factor. No algorithm outperforming the trivial round complexity of O(n) was known prior to this work.
The Minimum Dominating Set (MDS) problem is not only one of the most fundamental problems in distributedcomputing, it is also one of the most challenging ones. While it is well-known that minimum dominating sets cann...
详细信息
ISBN:
(纸本)9781450339643
The Minimum Dominating Set (MDS) problem is not only one of the most fundamental problems in distributedcomputing, it is also one of the most challenging ones. While it is well-known that minimum dominating sets cannot be approximated locally on general graphs, over the last years, several breakthroughs have been made on computing local approximations on sparse graphs. This paper presents a deterministic and local constant factor approximation for minimum dominating sets on bounded genus graphs, a large family of sparse graphs. Our main technical contribution is a new analysis of a slightly modified variant of an existing algorithm by Lenzen et al. Interestingly, unlike existing proofs for planar graphs, our analysis does not rely on direct topological arguments. We believe that our techniques can be useful for the study of local problems on sparse graphs beyond the scope of this paper.
The shared memory model helps parallel programming productivity, but it also has a high hardware cost and imposes scalability constraints. Ultimately, higher performance will use distributed memories, which scales bet...
详细信息
ISBN:
(纸本)9781450340922
The shared memory model helps parallel programming productivity, but it also has a high hardware cost and imposes scalability constraints. Ultimately, higher performance will use distributed memories, which scales better but requires programmers to manually transfer data between local memories, which is a complex task. distributed memories are also more energy efficient than shared memories, and are used in a family of embedded computing solutions called multi processor system on chip (MPSoC).
The proceedings contain 51 papers. The topics discussed include: asynchronous MPC with a strict honest majority using non-equivocation;distributing the setup in universally composable multi-party computation;the futur...
ISBN:
(纸本)9781450329446
The proceedings contain 51 papers. The topics discussed include: asynchronous MPC with a strict honest majority using non-equivocation;distributing the setup in universally composable multi-party computation;the future(s) of shared data structures;a paradox of eventual linearizability in shared memory;brief announcement: are lock-free concurrent algorithms practically wait-free?;brief announcement: a generic construction for nonblocking dual containers;multi-message broadcast with abstract MAC layers and unreliable links;simple and efficient local codes for distributed stable network construction;beyond set disjointness: the communication complexity of finding the intersection;breathe before speaking: efficient information dissemination despite noisy, limited and anonymous communication;and estimation for monotone sampling: competitiveness and customization.
Adaptive renaming can be viewed as a coordination task involving a set of asynchronous agents, each aiming at grabbing a single resource out of a set of resources totally ordered by their desirability. We consider a g...
详细信息
ISBN:
(纸本)9781450339643
Adaptive renaming can be viewed as a coordination task involving a set of asynchronous agents, each aiming at grabbing a single resource out of a set of resources totally ordered by their desirability. We consider a generalization of adaptive renaming to take into account scenarios in which resources are not independent. We model constraints between resources as an undirected graph: nodes represent the ressources, and an edge between two ressources indicates that these two ressources cannot be used simultaneously. In such a setting, the sets of resources that processes may use simultaneously form independent sets. In this note, we focus on this task in a model where such independent sets are computed by wait-free processes.
We consider an asynchronous shared memory system of n processes where processes may experience weak crash failures. A crash m-failure is a crash failure of a process that may occurs only while the point contention is ...
详细信息
ISBN:
(纸本)9781450339643
We consider an asynchronous shared memory system of n processes where processes may experience weak crash failures. A crash m-failure is a crash failure of a process that may occurs only while the point contention is at most m. It is known that there is no consensus algorithm for n processes using registers that can tolerate even a single crash n-failure. Is there a consensus algorithm for n processes using registers that can tolerate a single crash (n - 1)-failure? It is known that there is no k-set consensus algorithm for n > k processes using registers that can tolerate k crash n-failures. How may crash (n - l)-failures can a k-set consensus algorithm using registers tolerate, as a function of n, k and l? Answers to these questions follow from our results regarding the ability to tolerate weak crash failures.
Database research has witnessed a renewed interest for data processing in distributed and parallel settings. While distributed and parallel data management systems have been around for quite some time, it is the rise ...
详细信息
ISBN:
(纸本)9781450341912
Database research has witnessed a renewed interest for data processing in distributed and parallel settings. While distributed and parallel data management systems have been around for quite some time, it is the rise of cloud computing and the advent of Big Data that presents the community with new challenges. This paper highlights recent research concerning the logical foundations of massively parallel and distributed systems. The first part of the paper concerns massively parallel systems where computation proceeds in a number of synchronized rounds. Here, the focus is on evaluation algorithms for conjunctive queries as well as on reasoning about correctness and optimization of such algorithms. The second part of the paper addresses a distributed asynchronous setting where eventual consistency comes into play. Here, the focus is on coordination-free computation and its relationship to logical monotonicity and Datalog programs.
Finding a maximal independent set (MIS) in a graph is a cornerstone task in distributedcomputing. The local nature of an MIS allows for fast solutions in a static distributed setting, which are logarithmic in the num...
详细信息
ISBN:
(纸本)9781450339643
Finding a maximal independent set (MIS) in a graph is a cornerstone task in distributedcomputing. The local nature of an MIS allows for fast solutions in a static distributed setting, which are logarithmic in the number of nodes or in their degrees. The result trivially applies for the dynamic distributed model, in which edges or nodes may be inserted or deleted. In this paper, we take a different approach which exploits locality to the extreme, and show how to update an MIS in a dynamic distributed setting, either synchronous or asynchronous, with only a single adjustment and in a single round, in expectation. These strong guarantees hold for the complete fully dynamic setting: Insertions and deletions, of edges as well as nodes, gracefully and abruptly. This strongly separates the static and dynamic distributed models, as super-constant lower bounds exist for computing an MIS in the former. Our results are obtained by a novel analysis of the surprisingly simple solution of carefully simulating the greedy sequential MIS algorithm with a random ordering of the nodes. As such, our algorithm has a direct application as a 3-approximation algorithm for correlation clustering. This adds to the important toolbox of distributed graph decompositions, which are widely used as crucial building blocks in distributedcomputing. Finally, our algorithm enjoys a useful history-independence property, meaning the output is independent of the history of topology changes that constructed that graph. This means the output cannot be chosen, or even biased, by the adversary in case its goal is to prevent us from optimizing some objective function.
暂无评论