We provide new deterministic algorithms for the edge coloring problem, which is one of the classic and highly studied distributed local symmetry breaking problems. As our main result, we show that a (2 Delta - 1)-edge...
详细信息
ISBN:
(纸本)9781450392624
We provide new deterministic algorithms for the edge coloring problem, which is one of the classic and highly studied distributed local symmetry breaking problems. As our main result, we show that a (2 Delta - 1)-edge coloring can be computed in time poly log Delta + O(log* n) in the LOCAL model. This improves a result of Balliu, Kuhn, and Olivetti [PODC '20], who gave an algorithm with a quasi-polylogarithmic dependency on Delta. We further show that in the CONGEST model, an (8 + epsilon)Delta-edge coloring can be computed in poly log Delta + O(log* n) rounds. The best previous O(Delta)-edge coloring algorithm that can be implemented in the CONGEST model is by Barenboim and Elkin [PODC '11] and it computes a 2(O(1/epsilon)) Delta-edge coloring in time O(Delta(epsilon) + log* n) for any epsilon is an element of(0, 1].
This brief announcement presents an algorithm for (1 + epsilon) approximate single-source shortest paths for directed graphs with non-negative real edge weights in the CONGEST model that runs in (O) over tilde (n(1/2)...
详细信息
ISBN:
(纸本)9781450385480
This brief announcement presents an algorithm for (1 + epsilon) approximate single-source shortest paths for directed graphs with non-negative real edge weights in the CONGEST model that runs in (O) over tilde (n(1/2) + D + n(2/5)(+o)((1)) D-2/5) log W/epsilon(2)) rounds, where W is the ratio between the largest and smallest non-zero edge weights.
OpenMP has a long and successful history in parallel programming for CPUs, and more recently GPUs through accelerator offloading. In this work we show that the OpenMP accelerator offloading model is sufficient to seam...
详细信息
ISBN:
(纸本)9781450392044
OpenMP has a long and successful history in parallel programming for CPUs, and more recently GPUs through accelerator offloading. In this work we show that the OpenMP accelerator offloading model is sufficient to seamlessly and efficiently utilize more than a single compute node, and its connected accelerators, without source code or compiler modifications. For applications that support multi-device offloading, any combination of local and remote CPUs and accelerators can be utilized simultaneously, fully transparent to the user. Our low-overhead implementation of Remote OpenMP Offloading is publicly available in the LLVM/OpenMP compiler infrastructure with LLVM 12 and later. To evaluate our work we provide detailed studies on micro benchmarks, as well as scaling results for two HPC proxy applications. We show perfect (weak) scaling across dozens of GPUs in multiple hosts with effectiveness that is directly proportional to the ratio of computation versus memory transfer time. Our work outlines the capabilities and limits of OpenMP 5.1 to efficiently utilize a distributed heterogeneous system without source, compiler, or language modifications.
Graph coloring is fundamental to distributedcomputing. We give the first sub-logarithmic distributed algorithm for coloring cluster graphs. These graphs are obtained from the underlying communication network by contr...
详细信息
ISBN:
(纸本)9798400718854
Graph coloring is fundamental to distributedcomputing. We give the first sub-logarithmic distributed algorithm for coloring cluster graphs. These graphs are obtained from the underlying communication network by contracting nodes and edges, and they appear frequently as components in the study of distributed algorithms. In particular, we give a O (log* n)-round algorithm to (Δ + 1)-color cluster graphs of at least polylogarithmic degree. The previous best bound known was poly(log n) [Flin et al., SODA'24]. This properly generalizes results in the CONGEST model and shows that distributed graph problems can be solved quickly even when the node itself is decentralized.
Approximate agreement is a weaker version of consensus where two or more processes must agree on a real number within a distance e of each other. Many variants of this task have been considered in the literature: cont...
详细信息
ISBN:
(纸本)9781450385480
Approximate agreement is a weaker version of consensus where two or more processes must agree on a real number within a distance e of each other. Many variants of this task have been considered in the literature: continuous or discrete ones;multi-dimensional ones;as well as agreement on graphs and other spaces. We focus on two variants of approximate agreement on graphs, edge agreement and clique agreement. We show that both tasks arise as special cases of a more general, higher-dimensional, approximate agreement task, where the processes must agree on the vertices of a simplex in a given simplicial complex. This new point of view gives rise to a novel topological perspective on the solvability of clique agreement.
BFT protocols in the synchronous setting rely on a strong assumption: every message sent by a party will arrive at its destination within a known bounded time. To allow some degree of asynchrony while still tolerating...
详细信息
ISBN:
(纸本)9781450385480
BFT protocols in the synchronous setting rely on a strong assumption: every message sent by a party will arrive at its destination within a known bounded time. To allow some degree of asynchrony while still tolerating a minority corruption, recently, in Crypto'19, a weaker synchrony assumption called mobile sluggish faults was introduced. In this work, we investigate the support for mobile sluggish faults in existing synchronous protocols such as Dfinity, Streamlet, Sync HotStuff, OptSync and the optimal latency BFT protocol. We identify key principles that can be used to "compile" these synchronous protocols to tolerate mobile sluggish faults.
This work focuses on understanding the quantum message complexity of two central problems in distributedcomputing, namely, leader election and agreement in synchronous message-passing communication networks. We show ...
详细信息
ISBN:
(纸本)9798400718854
This work focuses on understanding the quantum message complexity of two central problems in distributedcomputing, namely, leader election and agreement in synchronous message-passing communication networks. We show that quantum communication gives an advantage for both problems by presenting quantum distributed algorithms that significantly outperform their respective classical counterparts under various network *** prior works have studied and analyzed quantum distributed algorithms in the context of (improving) round complexity, a key conceptual contribution of our work is positing a framework to design and analyze the message complexity of quantum distributed algorithms. We present and demonstrate how quantum algorithmic techniques, such as Grover search, quantum counting, and quantum walks, can significantly enhance the message efficiency of distributed *** particular, our leader election protocol for diameter-2 networks uses quantum walks to achieve the improved message complexity. To the best of our knowledge, this is the first such application of quantum walks in distributedcomputing.
Real-time data processing applications with low latency requirements have led to the increasing popularity of stream processing systems. While such systems offer convenient APIs that can be used to achieve data parall...
详细信息
ISBN:
(纸本)9781450392044
Real-time data processing applications with low latency requirements have led to the increasing popularity of stream processing systems. While such systems offer convenient APIs that can be used to achieve data parallelism automatically, they offer limited support for computations that require synchronization between parallel nodes. In this paper, we propose dependency-guided synchronization (DGS), an alternative programming model for stateful streaming computations with complex synchronization requirements. In the proposed model, the input is viewed as partially ordered, and the program consists of a set of parallelization constructs which are applied to decompose the partial order and process events independently. Our programming model maps to an execution model called synchronization plans which supports synchronization between parallel nodes. Our evaluation shows that APIs offered by two widely used systems-Flink and Timely Dataflow-cannot suitably expose parallelism in some representative applications. In contrast, DGS enables implementations with scalable performance, the resulting synchronization plans offer throughput improvements when implemented manually in existing systems, and the programming overhead is small compared to writing sequential code.
We present poly log log n-round randomized distributed algorithms to compute vertex splittings, a partition of the vertices of a graph into k parts such that a node of degree d(u) has ≈ d(u)/k neighbors in each part....
详细信息
Population protocols are a model of computation in which an arbitrary number of indistinguishable finite-state agents interact in pairs. The goal of the agents is to decide by stable consensus whether their initial gl...
详细信息
ISBN:
(纸本)9781450385480
Population protocols are a model of computation in which an arbitrary number of indistinguishable finite-state agents interact in pairs. The goal of the agents is to decide by stable consensus whether their initial global configuration satisfies a given property, specified as a predicate on the set of configurations. The state complexity of a predicate is the number of states of a smallest protocol that computes it. Previous work by Blondin et al. has shown that the counting predicates x >= eta have state complexity O(log eta) for leaderless protocols and O(log log eta) for protocols with leaders. We obtain the first non-trivial lower bounds: the state complexity of x >= eta is Omega(log log log eta) for leaderless protocols, and the inverse of a non-elementary function for protocols with leaders.
暂无评论