text: A central theme in distributed network algorithms concerns understanding and coping with the issue of locality. Inspired by sequential complexity theory, we focus on a complexity theory for distributed decision problems. In the context of locality, solving a decision problem requires the processors to independently inspect their local neighborhoods and then collectively decide whether a given global input instance belongs to some specified language. This paper introduces several classes of distributed decision problems, proves separation among them and presents some complete problems. More specifically, we consider the standard LOCAL model of computation and define LD (for local decision) as the class of decision problems that can be solved in constant number of communication rounds. We first study the intriguing question of whether randomization helps in local distributed computing, and to what extent. Specifically, we define the corresponding randomized class BPLD, and ask whether LD=BPLD. We provide a partial answer to this question by showing that in many cases, randomization does not help for deciding hereditary languages. In addition, we define the notion of local many-one reductions, and introduce the (nondeterministic) class NLD of decision problems for which there exists a certificate that can be verified in constant number of communication rounds. We prove that there exists an NLD-complete problem. We also show that there exist problems not in NLD. On the other hand, we prove that the class NLD#n, which is NLD assuming that each processor can access an oracle that provides the number of nodes in the network, contains all (decidable) languages. For this class we provide a natural complete problem as well.
  @cite_30: Suppose that n processors are arranged in a ring and can communicate only with their immediate neighbors. It is shown that any probabilistic algorithm for 3 coloring the ring must take at least @math rounds, otherwise the probability that all processors are colored legally is less than @math . A similar time bound holds for selecting a maximal independent set. The bound is tight (up to a constant factor) in light of the deterministic algorithms of Cole and Vishkin [Inform, and Control, 70 (1986), pp. 32–53] and extends the lower bound for deterministic algorithms of Linial [Proc. 28th IEEE Foundations of Computer Science Symposium, 1987, pp. 331–335].
  @cite_1: In this paper, we improve the bounds for computing a network decomposition distributively and deterministically. Our algorithm computes an (n?(n),n?(n))-decomposition innO(?(n))time, whereformula. As a corollary we obtain improved deterministic bounds for distributively computing several graph structures such as maximal independent sets and ?-vertex colorings. We also show that the class of graphs G whose maximum degree isnO(?(n))where ?(n)=1 log lognis complete for the task of computing a near-optimal decomposition, i.e., a (logn, logn)-decomposition, in polylog(n) time. This is a corollary of a more general characterization, which pinpoints the weak points of existing network decomposition algorithms. Completeness is to be intended in the following sense: if we have an algorithmAthat computes a near-optimal decomposition in polylog(n) time for graphs inG, then we can compute a near-optimal decomposition in polylog(n) time for all graphs.
  @cite_6: Two basic design strategies are used to develop a very simple and fast parallel algorithms for the maximal independent set (MIS) problem. The first strategy consists of assigning identical copies of a simple algorithm to small local portions of the problem input. The algorithm is designed so that when the copies are executed in parallel the correct problem output is produced very quickly. A very simple Monte Carlo algorithm for the MIS problem is presented which is based upon this strategy. The second strategy is a general and powerful technique for removing randomization from algorithms. This strategy is used to convert the Monte Carlo algorithm for this MIS problem into a simple deterministic algorithm with the same parallel running time.
  @cite_39: Abstract A simple parallel randomized algorithm to find a maximal independent set in a graph G = ( V , E ) on n vertices is presented. Its expected running time on a concurrent-read concurrent-write PRAM with O (| E | d max ) processors is O (log n ), where d max denotes the maximum degree. On an exclusive-read exclusive-write PRAM with O (| E |) processors the algorithm runs in O (log 2 n ). Previously, an O (log 4 n ) deterministic algorithm was given by Karp and Wigderson for the EREW-PRAM model. This was recently (independently of our work) improved to O (log 2 n ) by M. Luby. In both cases randomized algorithms depending on pairwise independent choices were turned into deterministic algorithms. We comment on how randomized combinatorial algorithms whose analysis only depends on d -wise rather than fully independent random choices (for some constant d ) can be converted into deterministic algorithms. We apply a technique due to A. Joffe (1974) and obtain deterministic construction in fast parallel time of various combinatorial objects whose existence follows from probabilistic arguments.
  @cite_24: We study deterministic, distributed algorithms for two weak variants of the standard graph coloring problem. We consider defective colorings, i.e., colorings where nodes of a color class may induce a graph of maximum degree d for some parameter d>0. We also look at colorings where a minimum number of multi-chromatic edges is required. For an integer k>0, we call a coloring k-partially proper if every node v has at least min k,deg(v) neighbors with a different color. We show that for all d∈ 1,...,Δ , it is possible to compute a O(Δ2 d2)-coloring with defect d in time O(log*n) where Δ is the largest degree of the network graph. Similarly, for all k∈ 1,...,Δ , a k-partially proper O(k2)-coloring can be computed in O(log*n) rounds. As an application of our weak defective coloring algorithm, we obtain a faster deterministic algorithm for the standard vertex coloring problem on graphs with moderate degrees. We show that in time O(Δ+log*n), a (Δ+1)-coloring can be computed, a task for which the best previous algorithm required time O(Δ*log(Δ) + log*n). The same result holds for the problem of computing a maximal independent set.
  @cite_27: We introduce Multi-Trials, a new technique for symmetry breaking for distributed algorithms and apply it to various problems in general graphs. For instance, we present three randomized algorithms for distributed (vertex or edge) coloring improving on previous algorithms and showing a time color trade-off. To get a Δ+1 coloring takes time O(log Δ+ √ log n). To obtain an O(Δ+log1+1 log*nn) coloring takes time O(log* n). This is more than an exponential improvement in time for graphs of polylogarithmic degree. Our fastest algorithm works in constant time using O(Δlog(c) n+ log1+1 c n) colors, where c denotes an arbitrary constant and log(c ) n denotes the c times (recursively) applied logarithm ton. We also use the Multi-Trials technique to compute network decompositions and to compute maximal independent set (MIS), obtaining new results for several graph classes.
  @cite_40: 
summary: The question of whether randomization helps in decreasing the locality parameter of construction problems has been the focus of numerous studies. To date, there exists evidence that, for some problems at least, randomization does not help. For instance, @cite_30 proves this for 3-coloring the ring. In fact, for low degree graphs, the gaps between the efficiencies of the best known randomized and deterministic algorithms for problems like MIS, @math -coloring, and Maximal Matching are very small. On the other hand, for graphs of arbitrarily large degrees, there seem to be indications that randomization does help, at least in some cases. For instance, @math -coloring can be randomly computed in expected @math communication rounds on @math -node graphs @cite_39 @cite_6 , whereas the best known deterministic algorithm for this problem performs in @math rounds @cite_1 . @math -coloring results whose performances are measured also with respect to the maximum degree @math illustrate this phenomena as well. Specifically, @cite_27 shows that @math -coloring can be randomly computed in expected @math communication rounds whereas the best known deterministic algorithm performs in @math rounds @cite_40 @cite_24 .