2012/07/01 by Pierre Fraigniaud, Fraigniaud, Pierre, Amos Korman +5
Computer Science · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Cryptography and Data Security #Distributed #FOS: Computer and information sciences #Optimization and Search Problems #Parallel #and Cluster Computing (cs.DC) #cs.CC #cs.DC
paper · pdf · doi:10.48550/arxiv.1207.0252
arxiv created 2012/07/01 · openalex publication_date 2012/07/01 · arxiv updated 2012/07/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 p2+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 p2+q≤1. We define Bk(t) to be the set of all languages decidable in at most t rounds by a (p,q)-decider, where p1+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 Bk provides a spectrum of complexity classes between determinism and complete randomization. We prove that all these classes are separated: for every integer k≥ 1, there exists a language L satisfying L∈ Bk+1(0) but L∉ Bk(t) for any t=o(n). In addition, we show that B_∞(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.