What can be decided locally without identifiers?

Pierre Fraigniaud, Mika Göös, Amos Korman, and Jukka Suomela


Do unique node identifiers help in deciding whether a network G has a prescribed property P? We study this question in the context of distributed local decision, where the objective is to decide whether G \in P by having each node run a constant-time distributed decision algorithm. If G \in P, all the nodes should output yes; if G \notin P, at least one node should output no. A recent work (Fraigniaud et al., OPODIS 2012) studied the role of identifiers in local decision and gave several conditions under which identifiers are not needed. In this  article, we answer their original question. More than that, we do so under all combinations of the following two critical variations on the underlying model of distributed computing: (B): the size of the identifiers is bounded by a function of the size of the input network; as  opposed to (\neg B): the identifiers are unbounded. (C): the nodes run a computable algorithm; as opposed to (\neg C): the nodes can compute any, possibly uncomputable function. While it is easy to see that under (\neg B, \neg C) identifiers are not needed, we show that under all other combinations there are properties that can be decided locally if and only if identifiers are present. Our constructions use ideas from classical computability theory.

Guest: Mika Göös
Host: Stefan Schmid

Randomized Distributed Decision

Pierre Fraigniaud, Amos Korman, Merav Parter, David Peleg

Abstract: The paper tackles the power of randomization in the context of locality by analyzing the ability to`boost’ the success probability of deciding a distributed language. The main outcome of this analysis is that the distributed computing setting contrasts significantly with the sequential one as far as randomization is concerned. Indeed, we prove that in some cases, the ability to increase the success probability for deciding distributed languages is rather limited. Informally, a (p,q)-decider for a language L is a distributed randomized algorithm which accepts instances in L with probability at least p and rejects instances outside of L with probability at least q. It is known that every hereditary language that can be decided in t rounds by a (p,q)-decider, where p^2+q>1, can actually be decided deterministically in O(t) rounds. In one of our results we give evidence supporting the conjecture that the above statement holds for all distributed languages. This is achieved by considering the restricted case of path topologies. We then turn our attention to the range below the aforementioned threshold, namely, the case where p^2+q\leq1. We define B_k(t) to be the set of all languages decidable in at most t rounds by a (p,q)-decider, where p^{1+1/k}+q>1. It is easy to see that every language is decidable (in zero rounds) by a (p,q)-decider satisfying p+q=1. Hence, the hierarchy B_k provides a spectrum of complexity classes between determinism and complete randomization. We prove that all these classes are separated: for every integer k\geq 1, there exists a language L satisfying L\in B_{k+1}(0) but L\notin B_k(t) for any t=o(n). In addition, we show that B_\infty(t) does not contain all languages, for any t=o(n). Finally, we show that if the inputs can be restricted in certain ways, then the ability to boost the success probability becomes almost null.

Guest: Merav Parter

Host: Yvonne-Anne Pignolet


Lower Bounds for Local Approximation

Mika Göös, Juho Hirvonen, Jukka Suomela

Abstract: In the study of deterministic distributed algorithms it is commonly assumed that each node has a unique $O(\log n)$-bit identifier. We prove that for a general class of graph problems, local algorithms (constant-time distributed algorithms) do not need such identifiers: a port numbering and orientation is sufficient.
Our result holds for so-called simple PO-checkable graph optimisation problems; this includes many classical packing and covering problems such as vertex covers, edge covers, matchings, independent sets, dominating sets, and edge dominating sets. We focus on the case of bounded-degree graphs and show that if a local algorithm finds a constant-factor approximation of a simple PO-checkable graph problem with the help of unique identifiers, then the same approximation ratio can be achieved on anonymous networks.
As a corollary of our result and by prior work, we derive a tight lower bound on the local approximability of the minimum edge dominating set problem.
Our main technical tool is an algebraic construction of homogeneously ordered graphs: We say that a graph is $(\alpha,r)$-homogeneous if its nodes are linearly ordered so that an $\alpha$ fraction of nodes have pairwise isomorphic radius-$r$ neighbourhoods. We show that there exists a finite $(\alpha,r)$-homogeneous $2k$-regular graph of girth at least $g$ for any $\alpha < 1$ and any $r$, $k$, and $g$.

Guest: Jukka Suomela
Host: Merav Parter

Toward more Localized Local Algorithms: Removing Assumptions concerning Global Knowledge

Amos Korman, Jean-Sébastien Sereni and Laurent Viennot

Numerous sophisticated local algorithm were suggested in the literature for various fundamental problems. Notable examples are the MIS and (∆ + 1)-coloring algorithms by Barenboim and Elkin [6], by Kuhn [22], and by Panconesi and Srinivasan [33], as well as the O(∆^2)-coloring algorithm by Linial [27]. Unfortunately, most known local algorithms (including, in particular, the aforementioned algorithms) are non-uniform, that is, they assume that all nodes know good estimations of one or more global parameters of the network, e.g., the maximum degree ∆ or the number of nodes n. This paper provides a rather general method for transforming a non-uniform local algorithm into a uniform one. Furthermore, the resulting algorithm enjoys the same asymptotic running time as the original non-uniform algorithm. Our method applies to a wide family of both deterministic and randomized algorithms. Specifically, it applies to almost all of the state of the art non-uniform algorithms regarding MIS and Maximal Matching, as well as to many results concerning the coloring problem. (In particular, it applies to all aforementioned algorithms.) To obtain our transformations we introduce a new distributed tool called pruning algorithms, which we believe may be of independent interest.

Guest: Amos Korman
Host: Zvi Lotker