BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
The sinkless orientation problem plays a key role in understanding the foundations of distributed computing. The problem can be used to separate two fundamental models of distributed graph algorithms, LOCAL and SLOCAL: the locality of sinkless orientation is Ω(logn) in the deterministic LOCAL model and O(loglogn) in the deterministic SLOCAL model. Both of these results are known by prior work, but here we give new simple, self-contained proofs for them.
We introduce a new graph problem, the token dropping game, and we show how to solve it efficiently in a distributed setting. We use the token dropping game as a tool to design an efficient distributed algorithm for stable orientations and more generally for locally optimal semi-matchings. The prior work by Czygrinow et al. (DISC 2012) finds a stable orientation in O(Δ5) rounds in graphs of maximum degree Δ, while we improve it to O(Δ4) and also prove a lower bound of Ω(Δ).
Consider a distributed task where the communication network is fixed but the local inputs given to the nodes of the distributed system may change over time. In this work, we explore the following question: if some of the local inputs change, can an existing solution be updated efficiently, in a dynamic and distributed manner? To address this question, we define the batch dynamic CONGEST model in which we are given a bandwidth-limited communication network and a dynamic edge labelling defines the problem input. The task is to maintain a solution to a graph problem on the labeled graph under batch changes. We investigate, when a batch of α edge label changes arrive, -- how much time as a function of α we need to update an existing solution, and -- how much information the nodes have to keep in local memory between batches in order to update the solution quickly. Our work lays the foundations for the theory of input-dynamic distributed network algorithms. We give a general picture of the complexity landscape in this model, design both universal algorithms and algorithms for concrete problems, and present a general framework for lower bounds. In particular, we derive non-trivial upper bounds for two selected, contrasting problems: maintaining a minimum spanning tree and detecting cliques.
We show that any randomised Monte Carlo distributed algorithm for the Lovász local lemma requires Ω(loglogn) communication rounds, assuming that it finds a correct assignment with high probability. Our result holds even in the special case of d=O(1), where d is the maximum degree of the dependency graph. By prior work, there are distributed algorithms for the Lovász local lemma with a running time of O(logn) rounds in bounded-degree graphs, and the best lower bound before our work was Ω(log∗n) rounds [Chung et al. 2014].
We prove exact bounds on the time complexity of distributed graph colouring. If we are given a directed path that is properly coloured with n colours, by prior work it is known that we can find a proper 3-colouring in 21log∗(n)±O(1) communication rounds. We close the gap between upper and lower bounds: we show that for infinitely many n the time complexity is precisely 21log∗n communication rounds.
Consider a complete communication network of n nodes, where the nodes receive a common clock pulse. We study the synchronous c-counting problem: given any starting state and up to f faulty nodes with arbitrary behaviour, the task is to eventually have all correct nodes counting modulo c in agreement. Thus, we are considering algorithms that are self-stabilizing despite Byzantine failures. In this work, we give new algorithms for the synchronous counting problem that (1) are deterministic, (2) have linear stabilisation time in f, (3) use a small number of states, and (4) achieve almost-optimal resilience. Prior algorithms either resort to randomisation, use a large number of states, or have poor resilience. In particular, we achieve an exponential improvement in the space complexity of deterministic algorithms, while still achieving linear stabilisation time and almost-linear resilience.
We study the problem of finding large cuts in d-regular triangle-free graphs. In prior work, Shearer (1992) gives a randomised algorithm that finds a cut of expected size (1/2+0.177/d)m, where m is the number of edges. We give a simpler algorithm that does much better: it finds a cut of expected size (1/2+0.28125/d)m. As a corollary, this shows that in any d-regular triangle-free graph there exists a cut of at least this size. Our algorithm can be interpreted as a very efficient randomised distributed algorithm: each node needs to produce only one random bit, and the algorithm runs in one synchronous communication round. This work is also a case study of applying computational techniques in the design of distributed algorithms: our algorithm was designed by a computer program that searched for optimal algorithms for small values of d.
A local algorithm is a distributed algorithm that completes after a constant number of synchronous communication rounds. We present local approximation algorithms for the minimum dominating set problem and the maximum matching problem in 2-coloured and weakly 2-coloured graphs. In a weakly 2-coloured graph, both problems admit a local algorithm with the approximation factor (Δ+1)/2, where Δ is the maximum degree of the graph. We also give a matching lower bound proving that there is no local algorithm with a better approximation factor for either of these problems. Furthermore, we show that the stronger assumption of a 2-colouring does not help in the case of the dominating set problem, but there is a local approximation scheme for the maximum matching problem in 2-coloured graphs.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.