Distributed Computing

Journal: Distributed Computing

Abbreviation

Distrib. comput.

Publisher

Springer

ISSN

0178-2770
1432-0452

Show all metadata

Search Results

Publications 1 - 10 of 20

A tight lower bound for semi-synchronous collaborative grid exploration
Brandt, Sebastian; Uitto, Jara; Wattenhofer, Roger (2020)
Distributed Computing
Recently, there has been a growing interest in grid exploration by agents with limited capabilities. We show that the grid cannot be explored by three semi-synchronous finite automata, answering an open question by Emek et al. (Theor Comput Sci 608:255–267, 2015) in the negative. In the setting we consider, time is divided into discrete steps, where in each step, an adversarially selected subset of the agents executes one look–compute–move cycle. The agents operate according to a shared finite automaton, where every agent is allowed to have a distinct initial state. The only means of communication is to sense the states of the agents sharing the same grid cell. The agents are equipped with a global compass and whenever an agent moves, the destination cell of the movement is chosen by the agent’s automaton from the set of neighboring grid cells. In contrast to the four agent protocol by Emek et al., we show that three agents do not suffice for grid exploration.
An Optimal Maximal Independent Set Algorithm for Bounded-Independence Graphs
Schneider, Johannes; Wattenhofer, Roger (2010)
Distributed Computing
Low-Congestion shortcuts without embedding
Haeupler, Bernhard; Izumi, Taisuke; Zuzic, Goran (2021)
Distributed Computing
Distributed optimization algorithms are frequently faced with solving sub-problems on disjoint connected parts of a network. Unfortunately, the diameter of these parts can be significantly larger than the diameter of the underlying network, leading to slow running times. This phenomenon can be seen as the broad underlying reason for the pervasive Ω~(√n+D) lower bounds that apply to most optimization problems in the CONGEST model. On the positive side, [Ghaffari and Hauepler; SODA’16] introduced low-congestion shortcuts as an elegant solution to circumvent this problem in certain topologies of interest. Particularly, they showed that there exist good shortcuts for any planar network and more generally any bounded genus network. This directly leads to fast O(DlogO(1)n) distributed algorithms for MST and Min-Cut approximation, given that one can efficiently construct these shortcuts in a distributed manner. Unfortunately, the shortcut construction of [Ghaffari and Hauepler; SODA’16] relies heavily on having access to a genus embedding of the network. Computing such an embedding distributedly, however, is a hard problem—even for planar networks. No distributed embedding algorithm for bounded genus graphs is in sight. In this work, we side-step this problem by defining tree-restricted shortcuts: a more structured and restricted form of shortcuts. We give a novel construction algorithm which efficiently finds such shortcuts that are, up to a logarithmic factor, as good as the best restricted shortcuts that exist for a given network. This new construction algorithm directly leads to an O(DlogO(1)n)-round algorithm for solving optimization problems like MST for any topology for which good restricted shortcuts exist—without the need to compute any embedding. This greatly simplifies the existing planar algorithms and includes the first efficient algorithm for bounded genus graphs.
Lower bounds for searching robots, some faulty
Kupavskii, Andrey; Welzl, Emo (2021)
Distributed Computing
Suppose we are sending out k robots from 0 to search the real line at constant speed (with turns) to find a target at an unknown location; f of the robots are faulty, meaning that they fail to report the target although visiting its location (called crash type). The goal is to find the target in time at most λ| x| , if the target is located at x, | x| ≥ 1 , for λ as small as possible. We show that this cannot be achieved for λ<2ρρ(ρ-1)ρ-1+1,ρ:=2(f+1)k,which is tight due to earlier work (see Czyzowitz et al. in Proc PODC’16, pp 405–414, 2016, where this problem was introduced). This also gives some better than previously known lower bounds for so-called Byzantine-type faulty robots that may actually wrongly report a target. In the second part of the paper we deal with the m-rays generalization of the problem, where the hidden target is to be detected on m rays all emanating at the same point. Using a generalization of our methods, along with a useful relaxation of the original problem, we establish a tight lower for this setting as well (as above, with ρ:=m(f+1)k). When specialized to the case f= 0 , this resolves the question on parallel search on m rays, posed by three groups of scientists some 15–30 years ago: by Baeza-Yates, Culberson, and Rawlins; by Kao, Ma, Sipser, and Yin; and by Bernstein, Finkelstein, and Zilberstein. The m-rays generalization is known to have connections to other, seemingly unrelated, problems, including hybrid algorithms for on-line problems, and so-called contract algorithms. © 2019, Springer-Verlag GmbH Germany, part of Springer Nature.
Coloring unstructured radio networks
Moscibroda, Thomas; Wattenhofer, Roger (2008)
Distributed Computing
Almost universally optimal distributed Laplacian solvers via low-congestion shortcuts
Anagnostides, Ioannis; Lenzen, Christoph; Haeupler, Bernhard; et al. (2023)
Distributed Computing
In this paper, we refine the (almost) existentially optimal distributed Laplacian solver of Forster, Goranci, Liu, Peng, Sun, and Ye (FOCS ‘21) into an (almost) universally optimal distributed Laplacian solver. Specifically, when the topology is known (i.e., the Supported-CONGEST model), we show that any Laplacian system on an n-node graph with shortcut quality SQ(G) can be solved after n°⁽¹⁾SQ(G)log(1/ϵ) rounds, where ϵ>0 is the required accuracy. This almost matches our lower bound that guarantees that any correct algorithm on G requires Ω˜(SQ(G)) rounds, even for a crude solution with ϵ≤1/2. Several important implications hold in the unknown-topology (i.e., standard CONGEST) case: for excluded-minor graphs we get an almost universally optimal algorithm that terminates in D⋅n°⁽¹⁾log(1/ϵ) rounds, where D is the hop-diameter of the network; as well as n°⁽¹⁾log(1/ϵ)-round algorithms for the case of SQ(G)≤n°⁽¹⁾, which holds for most networks of interest. Moreover, following a recent line of work in distributed algorithms, we consider a hybrid communication model which enhances CONGEST with limited global power in the form of the node-capacitated clique model. In this model, we show the existence of a Laplacian solver with round complexity n°⁽¹⁾log(1/ϵ). The unifying thread of these results, and our main technical contribution, is the development of near-optimal algorithms for a novel ρ-congested generalization of the standard part-wise aggregation problem, which could be of independent interest.
Improved distributed Delta-coloring
Ghaffari, Mohsen; Hirvonen, Juho; Kuhn, Fabian; et al. (2021)
Distributed Computing
We present a randomized distributed algorithm that computes a Delta-coloring in any non-complete graph with maximum degree Delta >= 4 in O(log Delta)+ 2(O)(root(log log n)) rounds, as well as a randomized algorithm that computes a Delta-coloring in O((log log n)(2)) rounds when Delta is an element of [3, O(1)]. Both these algorithms improve on an O(log(3) n/log Delta)-round algorithm of Panconesi and Srinivasan (STOC'93), which has remained the state of the art for the past 25 years. Moreover, the latter algorithm gets (exponentially) closer to an Omega (log log n) round lower bound of Brandt et al. (STOC'16).
Improved distributed degree splitting and edge coloring
Ghaffari, Mohsen; Hirvonen, Juho; Kuhn, Fabian; et al. (2020)
Distributed Computing
Towards Worst-Case Churn Resistant Peer-to-Peer Systems
Kuhn, Fabian; Schmid, Stefan; Wattenhofer, Roger (2010)
Distributed Computing
Efficient adaptive collect using randomization
Attiya, Hagit; Kuhn, Fabian; Plaxton, C. Greg; et al. (2006)
Distributed Computing

Publications 1 - 10 of 20

Journal: Distributed Computing

Abbreviation

Publisher

Journal Volumes

ISSN

Description

Filters

Search Results