### Towards a complexity theory for local distributed computingTowards a complexity theory for local distributed computing

Access Restriction
Subscribed

 Author Fraigniaud, Pierre ♦ Korman, Amos ♦ Peleg, David Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2013 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Local distributed algorithms ♦ Local decision ♦ Nondeterminism ♦ Oracle ♦ Randomized algorithms Abstract A central theme in distributed network algorithms concerns understanding and coping with the issue of $\textit{locality}.$ Yet despite considerable progress, research efforts in this direction have not yet resulted in a solid basis in the form of a fundamental computational complexity theory for 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. We consider the standard LOCAL model of computation and define $LD(\textit{t})$ (for local decision) as the class of decision problems that can be solved in $\textit{t}$ 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(\textit{t},\textit{p},\textit{q}),$ containing all languages for which there exists a randomized algorithm that runs in $\textit{t}$ rounds, accepts correct instances with probability at least $\textit{p},$ and rejects incorrect ones with probability at least $\textit{q}.$ We show that $p^{2}$ + q = 1 is a threshold for the containment of $LD(\textit{t})$ in $BPLD(\textit{t},\textit{p},\textit{q}).$ More precisely, we show that there exists a language that does not belong to $LD(\textit{t})$ for any $\textit{t}=\textit{o}(\textit{n})$ but does belong to $BPLD(\textit{0},\textit{p},\textit{q})$ for any $\textit{p},\textit{q}$ ∈ (0,1) such that $p^{2}$ + q ≤ 1. On the other hand, we show that, restricted to hereditary languages, $BPLD(\textit{t},\textit{p},\textit{q})=LD(\textit{O}(\textit{t})),$ for any function $\textit{t},$ and any $\textit{p},$ $\textit{q}$ ∈ (0,1) such that $p^{2}$ + q > 1. In addition, we investigate the impact of nondeterminism on local decision, and establish several structural results inspired by classical computational complexity theory. Specifically, we show that nondeterminism does help, but that this help is limited, as there exist languages that cannot be decided locally nondeterministically. Perhaps surprisingly, it turns out that it is the combination of randomization with nondeterminism that enables to decide all languages in constant time. Finally, we introduce the notion of local reduction, and establish a couple of completeness results. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2013-10-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 60 Issue Number 5 Page Count 26 Starting Page 1 Ending Page 26

#### Open content in new tab

Source: ACM Digital Library