We study the gathering problem to make multiple agents initially scattered in arbitrary networks gather at a single node. There exist k agents with unique identifiers (IDs) in the network, and.. of them are weakly Byz...
详细信息
ISBN:
(纸本)9781450392624
We study the gathering problem to make multiple agents initially scattered in arbitrary networks gather at a single node. There exist k agents with unique identifiers (IDs) in the network, and.. of them are weakly Byzantine agents, which behave arbitrarily except for falsifying their IDs. The agents behave in synchronous rounds, and each node does not have any memory like a whiteboard. In the literature, there exists a gathering algorithm that tolerates any number of Byzantine agents, while the fastest gathering algorithm requires Omega(f(2)) non-Byzantine agents. This paper proposes an algorithm that solves the gathering problem efficiently with Omega(f(2)) non-Byzantine agents since there is a large gap between the number of non-Byzantine agents in the previous works. The proposed algorithm achieves the gathering in O(f center dot |Lambda(good) | center dot X (Nu)) rounds in case of 9f + 8 <= k and simultaneous startup if.. is given to agents, where ||Lambda(good) | | is the length of the largest ID among nonByzantine agents, and |Lambda(good) | is the number of rounds required to explore any network composed of n nodes. This algorithm is faster than the most fault-tolerant existing algorithm and requires fewer non-Byzantine agents than the fastest algorithm if.. is given to agents, although the guarantees on simultaneous termination and startup delay are not the same. To achieve this property, we propose a new technique to simulate a Byzantine consensus algorithm for synchronous message-passing systems on agent systems.
The proceedings contain 49 papers. The topics discussed include: managing the cyber risk in a decoupled world: does this bring potential opportunities in computer science?;using linearizable objects in randomized conc...
ISBN:
(纸本)9783959772556
The proceedings contain 49 papers. The topics discussed include: managing the cyber risk in a decoupled world: does this bring potential opportunities in computer science?;using linearizable objects in randomized concurrent programs;good-case early-stopping latency of synchronous byzantine reliable broadcast: the deterministic case;polynomial-time verification and testing of implementations of the snapshot data structure;almost universally optimal distributed Laplacian solvers via low-congestion shortcuts;byzantine connectivity testing in the congested clique;efficient classification of locally checkable problems in regular trees;holistic verification of blockchain consensus;how to meet at a node of any connected graph;liveness and latency of byzantine state-machine replication;and how to wake up your neighbors: safe and nearly optimal generic energy conservation in radio networks.
The Quantum CONGEST model is a variant of the CONGEST model, where messages consist of O(log(n)) qubits. In this paper, we give a general framework for implementing quantum query algorithms efficiently in a Quantum CO...
详细信息
ISBN:
(纸本)9781450392624
The Quantum CONGEST model is a variant of the CONGEST model, where messages consist of O(log(n)) qubits. In this paper, we give a general framework for implementing quantum query algorithms efficiently in a Quantum CONGEST network, using the concept of parallel-query quantum algorithms. We apply our framework for distributed quantum queries in two settings: problems where data is distributed over the network, and graph theoretical problems where the network defines the input. The first setting is slightly unusual in CONGEST but here our results follow almost directly from the quantum query setting. The second setting is more traditional for the CONGEST model but here our framework requires also some classical CONGEST steps to apply. In the setting with distributed data, we show how a network can pick one of k dates for a meeting such that a maximum number of nodes is available, using (O) over tilde(root kD + D) rounds, with D the network diameter. The classical complexity is linear in k. We also give an efficient algorithm for element distinctness: if all nodes together holds a list of k numbers, we show that the nodes can determine whether there are any duplicates in (O) over tilde (k(2/3) D-1/3 + D) rounds. Classically this problem requires (Omega) over tilde (k + D) rounds. We also generalize the protocol for the distributed Deutsch-Jozsa problem from the two-party setting considered by Buhrman, Cleve, and Wigderson [4] to general networks. This gives a novel separation between exact classical and exact quantum protocols in the CONGEST model. In the setting where the input is the network structure itself, our framework almost directly allows us to recover the O(root nD) round diameter computation algorithm of Le Gall and Magniez [21]. We extend this approach to also compute the radius in the same number of rounds, and to give an epsilon-additive approximation of the average eccentricity in (O) over tilde (D-3/2/epsilon) rounds. Finally, we give the first quantum
In this brief announcement, we define operation asymmetry, which captures how processes may interact with an object differently, and discuss its implications in the context of a popular network communication technolog...
详细信息
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.
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.
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.
暂无评论