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

 

Locality and checkability in wait-free computing

Pierre Fraigniaud, Sergio Rajsbaum and Corentin Travers

Abstract:
This paper studies  notions of locality that are inherent to the specification of a
distributed task and independent of the computing environment, in a shared
memory wait-free system.
A  task T =(I,O,D) is checkable if there exists a wait-free distributed algorithm that, given s in I and t in O,  determines whether t in D(s), i.e., if t is a valid output for s according to
the specification D of T. Determining whether a projection-closed task is
wait-free solvable remains undecidable, demonstrating the richness of this
class. A locality property called projection-closed is identified,  that completely characterizes tasks that are wait-free  checkable.
A stronger notion of locality considers tasks  where the outputs look identically to the inputs at every vertex (input value of  a process). A task T =(I,O,D)  is said to be locality-preserving} if  O is a  covering complex of I. This topological property yields obstacles for wait-free  solvability different in nature from the classical agreement impossibility
results. On the other hand, locality-preserving tasks are projection-closed and
therefore always wait-free checkable.  A classification of locality-preserving
tasks in term of their relative computational power is provided.
A correspondence between locality-preserving tasks and subgroups of the edgepath
group of an input complex shows the existence of  hierarchies of  locality-preserving tasks, each one containing at the top the universal task  (induced by the universal covering complex), and at the bottom the trivial identity task.
Guest: Pierre Fraigniaud
Host: Merav Parter