Distributed Lower Bounds for Ruling Sets
METADATA ONLY
Loading...
Author / Producer
Date
2022
Publication Type
Journal Article
ETH Bibliography
yes
Citations
Altmetric
METADATA ONLY
Data
Rights / License
Abstract
Given a graph G=(V, E), an ( α, β )-ruling set is a subset S⊆V such that the distance between any two vertices in S is at least α, and the distance between any vertex in V and the closest vertex in S is at most β . We present lower bounds for distributedly computing ruling sets. More precisely, for the problem of computing a ( 2, β)-ruling set (and hence also any ( α, β )-ruling set with α>2 ) in the LOCAL model of distributed computing, we show the following, where n denotes the number of vertices, Δ the maximum degree, and c is some universal constant independent of NAND Δ . •Any deterministic algorithm requires Ω(min{logΔβloglogΔ, logΔn})rounds, for all β≤cmin{logΔloglogΔ-√, logΔn} . By optimizing Δ, this impliesa deterministic lower bound of Ω(lognβloglogn-√) for all β≤clognloglogn-√3 . •Any randomized algorithm requires Ω(min{logΔβloglogΔ, logΔlogn}) rounds, for allβ≤cmin{logΔloglogΔ-√, logΔlogn} . By optimizing Δ, this implies a randomized lower bound of Ω(loglognβlogloglogn-?√) for all β≤cloglognlogloglogn √3 . For β>1, this improves on the previously best lower bound of Ω(log?n) rounds that follows from the 30-year-old bounds of Linial [FOCS'87] and Naor [J.Disc.Math.'91] (resp. Ω(1) rounds ifβ∈ω(log?n) ). For β=1, i.e. for the problem of computing a maximal independent set (which is nothing else than a (2, 1)-ruling set), our results improve on the previously best lower bound of Ω(log?n) on trees, as our bounds already hold on trees.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
51 (1)
Pages / Article No.
70 - 115
Publisher
SIAM
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
distributed computing; LOCAL model; lower bounds; maximal independent set; ruling set; round elimination