Deterministic Distributed Algorithms for Hitting and Dominating Sets, Spanners, and Network Decomposition
OPEN ACCESS
Loading...
Author / Producer
Date
2023
Publication Type
Doctoral Thesis
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
Abstract
We study four key combinatorial problems in distributed computing. Broadly speaking, our aim is to investigate the possibilities and limitations of deterministic algorithms through which we enhance and develop different tools for distributed derandomization. Our study starts with the hitting set problem, where the goal is to find a small set that contains at least one element from each set in a given collection. This problem appears as a subproblem in various contexts, and the standard randomized algorithm of sampling each element with a high enough probability is effective for several applications.
We design an efficient derandomization for this sampling procedure, leading to closing the gap between the randomized and deterministic results for several problems. We then proceed to explore deterministic constructions of spanners. A spanner is a subgraph with few edges that preserves pairwise distances in the original graph up to some distortion. By leveraging our deterministic algorithm for the hitting set problem, we are able to provide nearly optimal results for constructing spanners in the following settings: (i) spanners with small distortion, (ii) sparse spanners, which are subgraphs with a linear number of edges, and (iii) ultra-sparse spanners, which are subgraphs that consist of a tree plus a sublinear number of edges. Next, we study the classical problem of the minimum dominating set for bounded arboricity graphs.
A subset of nodes is a dominating set if it hits all closed neighborhoods and a graph has arboricity α if it can be partitioned into α forests. We present a deterministic O(α)-approximation algorithm improving on the previous results. We also show that our result is almost tight by reducing the problem to the known lower bound for vertex cover in general graphs. We conclude by presenting an improvement for deterministic network decomposition using a novel approach, and almost closing the gap between the “quality” of the best randomized and deterministic construction. Network decomposition is a central object in distributed computing, and in particular, it plays a key role in systematic distributed derandomization.
Permanent link
Publication status
published
External links
Editor
Contributors
Examiner : Ghaffari, Mohsen
Examiner : Gärtner, Bernd
Examiner : Baswana, Surender
Examiner : Kuhn, Fabian
Book title
Journal / series
Volume
Pages / Article No.
Publisher
ETH Zurich
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Distributed algorithms; Theoretical computer science
Organisational unit
09587 - Ghaffari, Mohsen (ehemalig) / Ghaffari, Mohsen (former)