2022/08/17 by Balliu, Alkida, Ghaffari, Mohsen, Kuhn, Fabian +1 · 3 citations
#Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)
paper · doi:10.48550/arxiv.2208.08213
The node-averaged complexity of a distributed algorithm running on a graph G=(V,E) is the average over the times at which the nodes V of G finish their computation and commit to their outputs. We study the node-averaged complexity for some distributed symmetry breaking problems and provide the following results (among others): - The randomized node-averaged complexity of computing a maximal independent set (MIS) in n-node graphs of maximum degree Δ is at least Ω(min\(logΔ)/(loglogΔ),√((log n)/(loglog n))\). This bound is obtained by a novel adaptation of the well-known KMW lower bound [JACM'16]. As a side result, we obtain the same lower bound for the worst-case randomized round complexity for computing an MIS in trees -- this essentially answers open problem 11.15 in the book of Barenboim and Elkin and resolves the complexity of MIS on trees up to an O(√(loglog n)) factor. We also show that, (2,2)-ruling sets, which are a minimal relaxation of MIS, have O(1) randomized node-averaged complexity. - For maximal matching, we show that while the randomized node-averaged complexity is Ω(min\(logΔ)/(loglogΔ),√((log n)/(loglog n))\), the randomized edge-averaged complexity is O(1). Further, we show that the deterministic edge-averaged complexity of maximal matching is O(log2Δ+ log^* n) and the deterministic node-averaged complexity of maximal matching is O(log3Δ+ log^* n). - Finally, we consider the problem of computing a sinkless orientation of a graph. The deterministic worst-case complexity of the problem is known to be Θ(log n), even on bounded-degree graphs. We show that the problem can be solved deterministically with node-averaged complexity O(log^* n), while keeping the worst-case complexity in O(log n).