BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Pierre Fraigniaud

Pierre Fraigniaud appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Distributed, Parallel, and Cluster ComputingComputational ComplexityData Structures and AlgorithmsMultiagent SystemsSocial and Information NetworksArtificial IntelligenceComputer Science and Game TheoryDiscrete MathematicsLogic in Computer Sciencemath.OCmath.PRRobotics

Catalog footprint

What is connected

22works
12topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

22 published item(s)

preprint2022arXiv

Computing Power of Hybrid Models in Synchronous Networks

During the last two decades, a small set of distributed computing models for networks have emerged, among which LOCAL, CONGEST, and Broadcast Congested Clique (BCC) play a prominent role. We consider hybrid models resulting from combining these three models. That is, we analyze the computing power of models allowing to, say, perform a constant number of rounds of CONGEST, then a constant number of rounds of LOCAL, then a constant number of rounds of BCC, possibly repeating this figure a constant number of times. We specifically focus on 2-round models, and we establish the complete picture of the relative powers of these models. That is, for every pair of such models, we determine whether one is (strictly) stronger than the other, or whether the two models are incomparable. The separation results are obtained by approaching communication complexity through an original angle, which may be of independent interest. The two players are not bounded to compute the value of a binary function, but the combined outputs of the two players are constrained by this value. In particular, we introduce the XOR-Index problem, in which Alice is given a binary vector $x\in\{0,1\}^n$ together with an index $i\in[n]$, Bob is given a binary vector $y\in\{0,1\}^n$ together with an index $j\in[n]$, and, after a single round of 2-way communication, Alice must output a boolean $\textrm{out}_A$, and Bob must output a boolean $\textrm{out}_B$, such that $\mbox{out}_A\land\mbox{out}_B = x_j\oplus y_i$. We show that the communication complexity of XOR-Index is $Ω(n)$ bits.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Error-Sensitive Proof-Labeling Schemes

Proof-labeling schemes are known mechanisms providing nodes of networks with certificates that can be verified locally by distributed algorithms. Given a boolean predicate on network states, such schemes enable to check whether the predicate is satisfied by the actual state of the network, by having nodes interacting with their neighbors only. Proof-labeling schemes are typically designed for enforcing fault-tolerance, by making sure that if the current state of the network is illegal with respect to some given predicate, then at least one node will detect it. Such a node can raise an alarm, or launch a recovery procedure enabling the system to return to a legal state. In this paper, we introduce error-sensitive proof-labeling schemes. These are proof-labeling schemes which guarantee that the number of nodes detecting illegal states is linearly proportional to the edit-distance between the current state and the set of legal states. By using error-sensitive proof-labeling schemes, states which are far from satisfying the predicate will be detected by many nodes, enabling fast return to legality. We provide a structural characterization of the set of boolean predicates on network states for which there exist error-sensitive proof-labeling schemes. This characterization allows us to show that classical predicates such as, e.g., acyclicity, and leader admit error-sensitive proof-labeling schemes, while others like regular subgraphs don't. We also focus on compact error-sensitive proof-labeling schemes. In particular, we show that the known proof-labeling schemes for spanning tree and minimum spanning tree, using certificates on $O(\log n)$ bits, and on $O\left(\log^2n\right)$ bits, respectively, are error-sensitive, as long as the trees are locally represented by adjacency lists, and not just by parent pointers.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Compact Distributed Certification of Planar Graphs

Naor, Parter, and Yogev (SODA 2020) have recently demonstrated the existence of a \emph{distributed interactive proof} for planarity (i.e., for certifying that a network is planar), using a sophisticated generic technique for constructing distributed IP protocols based on sequential IP protocols. The interactive proof for planarity is based on a distributed certification of the correct execution of any given sequential linear-time algorithm for planarity testing. It involves three interactions between the prover and the randomized distributed verifier (i.e., it is a \dMAM\/ protocol), and uses small certificates, on $O(\log n)$ bits in $n$-node networks. We show that a single interaction from the prover suffices, and randomization is unecessary, by providing an explicit description of a \emph{proof-labeling scheme} for planarity, still using certificates on just $O(\log n)$ bits. We also show that there are no proof-labeling schemes -- in fact, even no \emph{locally checkable proofs} -- for planarity using certificates on $o(\log n)$ bits.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Local Certification of Graphs with Bounded Genus

Naor, Parter, and Yogev [SODA 2020] recently designed a compiler for automatically translating standard centralized interactive protocols to distributed interactive protocols, as introduced by Kol, Oshman, and Saxena [PODC 2018]. In particular, by using this compiler, every linear-time algorithm for deciding the membership to some fixed graph class can be translated into a $\mathsf{dMAM}(O(\log n))$ protocol for this class, that is, a distributed interactive protocol with $O(\log n)$-bit proof size in $n$-node graphs, and three interactions between the (centralizer) computationally-unbounded but non-trustable prover Merlin, and the (decentralized) randomized computationally-limited verifier Arthur. As a corollary, there is a $\mathsf{dMAM}(O(\log n))$ protocol for the class of planar graphs, as well as for the class of graphs with bounded genus. We show that there exists a distributed interactive protocol for the class of graphs with bounded genus performing just a single interaction, from the prover to the verifier, yet preserving proof size of $O(\log n)$ bits. This result also holds for the class of graphs with bounded demi-genus, that is, graphs that can be embedded on a non-orientable surface of bounded genus. The interactive protocols described in this paper are actually proof-labeling schemes, i.e., a subclass of interactive protocols, previously introduced by Korman, Kutten, and Peleg [PODC 2005]. In particular, these schemes do not require any randomization from the verifier, and the proofs may often be computed a priori, at low cost, by the nodes themselves. Our results thus extend the recent proof-labeling scheme for planar graphs by Feuilloley et al. [PODC 2020], to graphs of bounded genus, and to graphs of bounded demigenus.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Present-Biased Optimization

This paper explores the behavior of present-biased agents, that is, agents who erroneously anticipate the costs of future actions compared to their real costs. Specifically, the paper extends the original framework proposed by Akerlof (1991) for studying various aspects of human behavior related to time-inconsistent planning, including procrastination, and abandonment, as well as the elegant graph-theoretic model encapsulating this framework recently proposed by Kleinberg and Oren (2014). The benefit of this extension is twofold. First, it enables to perform fine grained analysis of the behavior of present-biased agents depending on the optimisation task they have to perform. In particular, we study covering tasks vs. hitting tasks, and show that the ratio between the cost of the solutions computed by present-biased agents and the cost of the optimal solutions may differ significantly depending on the problem constraints. Second, our extension enables to study not only underestimation of future costs, coupled with minimization problems, but also all combinations of minimization/maximization, and underestimation/overestimation. We study the four scenarios, and we establish upper bounds on the cost ratio for three of them (the cost ratio for the original scenario was known to be unbounded), providing a complete global picture of the behavior of present-biased agents, as far as optimisation tasks are concerned.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Redundancy in Distributed Proofs

Distributed proofs are mechanisms enabling the nodes of a network to collectivity and efficiently check the correctness of Boolean predicates on the structure of the network, or on data-structures distributed over the nodes (e.g., spanning trees or routing tables). We consider mechanisms consisting of two components: a \emph{prover} assigning a \emph{certificate} to each node, and a distributed algorithm called \emph{verifier} that is in charge of verifying the distributed proof formed by the collection of all certificates. In this paper, we show that many network predicates have distributed proofs offering a high level of redundancy, explicitly or implicitly. We use this remarkable property of distributed proofs for establishing perfect tradeoffs between the \emph{size of the certificate} stored at every node, and the \emph{number of rounds} of the verification protocol. If we allow every node to communicate to distance at most $t$, one might expect that the certificate sizes can be reduced by a multiplicative factor of at least~$t$. In trees, cycles and grids, we show that such tradeoffs can be established for \emph{all} network predicates, i.e., it is always possible to linearly decrease the certificate size. In arbitrary graphs, we show that any part of the certificates common to all nodes can be evenly redistributed among these nodes, achieving even a better tradeoff: this common part of the certificate can be reduced by the size of a smallest ball of radius $t$ in the network. In addition to these general results, we establish several upper and lower bounds on the certificate sizes used for distributed proofs for spanning trees, minimum-weight spanning trees, diameter, additive and multiplicative spanners, and more, improving and generalizing previous results from the literature.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Simple and Fast Distributed Computation of Betweenness Centrality

Betweenness centrality is a graph parameter that has been successfully applied to network analysis. In the context of computer networks, it was considered for various objectives, ranging from routing to service placement. However, as observed by Maccari et al. [INFOCOM 2018], research on betweenness centrality for improving protocols was hampered by the lack of a usable, fully distributed algorithm for computing this parameter. We resolve this issue by designing an efficient algorithm for computing betweenness centrality, which can be implemented by minimal modifications to any distance-vector routing protocol based on Bellman-Ford. The convergence time of our implementation is shown to be proportional to the diameter of the network

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

A hierarchy of local decision

We extend the notion of distributed decision in the framework of distributed network computing, inspired by recent results on so-called distributed graph automata. We show that, by using distributed decision mechanisms based on the interaction between a prover and a disprover, the size of the certificates distributed to the nodes for certifying a given network property can be drastically reduced. For instance, we prove that minimum spanning tree can be certified with $O(\log n)$-bit certificates in $n$-node graphs, with just one interaction between the prover and the disprover, while it is known that certifying MST requires $Ω(\log^2 n)$-bit certificates if only the prover can act. The improvement can even be exponential for some simple graph properties. For instance, it is known that certifying the existence of a nontrivial automorphism requires $Ω(n^2)$ bits if only the prover can act. We show that there is a protocol with two interactions between the prover and the disprover enabling to certify nontrivial automorphism with $O(\log n)$-bit certificates. These results are achieved by defining and analysing a local hierarchy of decision which generalizes the classical notions of proof-labelling schemes and locally checkable proofs.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

An Optimal Ancestry Labeling Scheme with Applications to XML Trees and Universal Posets

In this paper we solve the ancestry-labeling scheme problem which aims at assigning the shortest possible labels (bit strings) to nodes of rooted trees, so that ancestry queries between any two nodes can be answered by inspecting their assigned labels only. This problem was introduced more than twenty years ago by Kannan et al. [STOC '88], and is among the most well-studied problems in the field of informative labeling schemes. We construct an ancestry-labeling scheme for $n$-node trees with label size $\log_2 n + O(\log \log n)$ bits, thus matching the $\log_2 n + O(\log \log n)$ bits lower bound given by Alstrup et al. [SODA '03]. Our scheme is based on a simplified ancestry scheme that operates extremely well on a restricted set of trees. In particular, for the set of n-node trees with depth at most d, the simplified ancestry scheme enjoys label size of $\log_2 n + 2 \log_2 d + O(1)$ bits. Since the depth of most XML trees is at most some small constant, such an ancestry scheme may be of practical use. In addition, we also obtain an adjacency-labeling scheme that labels n-node trees of depth d with labels of size $\log_2 n + 3 \log_2 d + O(1)$ bits. All our schemes assign the labels in linear time, and guarantee that any query can be answered in constant time. Finally, our ancestry scheme finds applications to the construction of small universal partially ordered sets (posets). Specifically, for any fixed integer k, it enables the construction of a universal poset of size $\tilde O(n^k)$ for the family of $n$-element posets with tree-dimension at most $k$. Up to lower order terms, this bound is tight thanks to a lower bound of $n^{k-o(1)}$ due to Alon and Scheinerman [Order '88].

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Distributed Testing of Excluded Subgraphs

We study property testing in the context of distributed computing, under the classical CONGEST model. It is known that testing whether a graph is triangle-free can be done in a constant number of rounds, where the constant depends on how far the input graph is from being triangle-free. We show that, for every connected 4-node graph H, testing whether a graph is H-free can be done in a constant number of rounds too. The constant also depends on how far the input graph is from being H-free, and the dependence is identical to the one in the case of testing triangles. Hence, in particular, testing whether a graph is K_4-free, and testing whether a graph is C_4-free can be done in a constant number of rounds (where K_k denotes the k-node clique, and C_k denotes the k-node cycle). On the other hand, we show that testing K_k-freeness and C_k-freeness for k>4 appear to be much harder. Specifically, we investigate two natural types of generic algorithms for testing H-freeness, called DFS tester and BFS tester. The latter captures the previously known algorithm to test the presence of triangles, while the former captures our generic algorithm to test the presence of a 4-node graph pattern H. We prove that both DFS and BFS testers fail to test K_k-freeness and C_k-freeness in a constant number of rounds for k>4.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Local Distributed Algorithms for Selfish Agents

In the classical framework of local distributed network computing, it is generally assumed that the entities executing distributed algorithms are altruistic. However, in various scenarios, the value of the output produced by an entity may have a tremendous impact on its future. This is for instance the case of tasks such as computing maximal independent sets (MIS) in networks. Indeed, a node belonging to the MIS may be later asked more than to a node not in the MIS, e.g., because MIS in networks are often used as backbones to collect, transfer, and broadcast information, which is costly. In this paper, we revisit typical local distributed network computing tasks in the framework of algorithmic game theory. Specifically, we focus on the construction of solutions for locally checkable labeling (LCL) tasks, which form a large class of distributed tasks, including MIS, coloring, maximal matching, etc., and which have been studied for more than 20 years in distributed computing. Given an LCL task, the nodes are collectively aiming at computing a solution, but, at the individual level, every node plays rationally and selfishly with the objective of optimizing its own profit. Surprisingly, the classical frameworks for game theory are not fully appropriate for the purpose of our study. Moreover, we show that classical notions like Nash equilibria may yield algorithms requiring an arbitrarily large number of rounds to converge. Nevertheless, by extending and generalizing core results from game theory, we establish the existence of a so-called trembling-hand perfect equilibria, a subset of Nash equilibria that is well suited to LCL construction tasks. The main outcome of the paper is therefore that, for essentially all distributed tasks whose solutions are locally checkable, there exist construction algorithms which are robust to selfishness.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Local Distributed Verification

In the framework of distributed network computing, it is known that, for every network predicate, each network configuration that satisfies this predicate can be proved using distributed certificates which can be verified locally. However, this requires to leak information about the identities of the nodes in the certificates, which might not be applicable in a context in which privacy is desirable. Unfortunately, it is known that if one insists on certificates independent of the node identities, then not all network predicates can be proved using distributed certificates that can be verified locally. In this paper, we prove that, for every network predicate, there is a distributed protocol satisfying the following two properties: (1) for every network configuration that is legal w.r.t. the predicate, and for any attempt by an adversary to prove the illegality of that configuration using distributed certificates, there is a locally verifiable proof that the adversary is wrong, also using distributed certificates; (2) for every network configuration that is illegal w.r.t. the predicate, there is a proof of that illegality, using distributed certificates, such that no matter the way an adversary assigns its own set of distributed certificates in an attempt to prove the legality of the configuration, the actual illegality of the configuration will be locally detected. In both cases, the certificates are independent of the identities of the nodes. These results are achieved by investigating the so-called local hierarchy of complexity classes in which the certificates do not exploit the node identities. Indeed, we give a characterization of such a hierarchy, which is of its own interest

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Noisy Rumor Spreading and Plurality Consensus

Error-correcting codes are efficient methods for handling \emph{noisy} communication channels in the context of technological networks. However, such elaborate methods differ a lot from the unsophisticated way biological entities are supposed to communicate. Yet, it has been recently shown by Feinerman, Haeupler, and Korman {[}PODC 2014{]} that complex coordination tasks such as \emph{rumor spreading} and \emph{majority consensus} can plausibly be achieved in biological systems subject to noisy communication channels, where every message transferred through a channel remains intact with small probability $\frac{1}{2}+ε$, without using coding techniques. This result is a considerable step towards a better understanding of the way biological entities may cooperate. It has been nevertheless be established only in the case of 2-valued \emph{opinions}: rumor spreading aims at broadcasting a single-bit opinion to all nodes, and majority consensus aims at leading all nodes to adopt the single-bit opinion that was initially present in the system with (relative) majority. In this paper, we extend this previous work to $k$-valued opinions, for any $k\geq2$. Our extension requires to address a series of important issues, some conceptual, others technical. We had to entirely revisit the notion of noise, for handling channels carrying $k$-\emph{valued} messages. In fact, we precisely characterize the type of noise patterns for which plurality consensus is solvable. Also, a key result employed in the bivalued case by Feinerman et al. is an estimate of the probability of observing the most frequent opinion from observing the mode of a small sample. We generalize this result to the multivalued case by providing a new analytical proof for the bivalued case that is amenable to be extended, by induction, and that is of independent interest.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Notions of Connectivity in Overlay Networks

" How well connected is the network? " This is one of the most fundamental questions one would ask when facing the challenge of designing a communication network. Three major notions of connectivity have been considered in the literature, but in the context of traditional (single-layer) networks, they turn out to be equivalent. This paper introduces a model for studying the three notions of connectivity in multi-layer networks. Using this model, it is easy to demonstrate that in multi-layer networks the three notions may differ dramatically. Unfortunately, in contrast to the single-layer case, where the values of the three connectivity notions can be computed efficiently, it has been recently shown in the context of WDM networks (results that can be easily translated to our model) that the values of two of these notions of connectivity are hard to compute or even approximate in multi-layer networks. The current paper shed some positive light into the multi-layer connectivity topic: we show that the value of the third connectivity notion can be computed in polynomial time and develop an approximation for the construction of well connected overlay networks.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Parallel Exhaustive Search without Coordination

We analyze parallel algorithms in the context of exhaustive search over totally ordered sets. Imagine an infinite list of "boxes", with a "treasure" hidden in one of them, where the boxes' order reflects the importance of finding the treasure in a given box. At each time step, a search protocol executed by a searcher has the ability to peek into one box, and see whether the treasure is present or not. By equally dividing the workload between them, $k$ searchers can find the treasure $k$ times faster than one searcher. However, this straightforward strategy is very sensitive to failures (e.g., crashes of processors), and overcoming this issue seems to require a large amount of communication. We therefore address the question of designing parallel search algorithms maximizing their speed-up and maintaining high levels of robustness, while minimizing the amount of resources for coordination. Based on the observation that algorithms that avoid communication are inherently robust, we analyze the best running time performance of non-coordinating algorithms. Specifically, we devise non-coordinating algorithms that achieve a speed-up of $9/8$ for two searchers, a speed-up of $4/3$ for three searchers, and in general, a speed-up of $\frac{k}{4}(1+1/k)^2$ for any $k\geq 1$ searchers. Thus, asymptotically, the speed-up is only four times worse compared to the case of full-coordination, and our algorithms are surprisingly simple and hence applicable. Moreover, these bounds are tight in a strong sense as no non-coordinating search algorithm can achieve better speed-ups. Overall, we highlight that, in faulty contexts in which coordination between the searchers is technically difficult to implement, intrusive with respect to privacy, and/or costly in term of resources, it might well be worth giving up on coordination, and simply run our non-coordinating exhaustive search algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Polynomial-Time Space-Optimal Silent Self-Stabilizing Minimum-Degree Spanning Tree Construction

Motivated by applications to sensor networks, as well as to many other areas, this paper studies the construction of minimum-degree spanning trees. We consider the classical node-register state model, with a weakly fair scheduler, and we present a space-optimal \emph{silent} self-stabilizing construction of minimum-degree spanning trees in this model. Computing a spanning tree with minimum degree is NP-hard. Therefore, we actually focus on constructing a spanning tree whose degree is within one from the optimal. Our algorithm uses registers on $O(\log n)$ bits, converges in a polynomial number of rounds, and performs polynomial-time computation at each node. Specifically, the algorithm constructs and stabilizes on a special class of spanning trees, with degree at most $OPT+1$. Indeed, we prove that, unless NP $=$ coNP, there are no proof-labeling schemes involving polynomial-time computation at each node for the whole family of spanning trees with degree at most $OPT+1$. Up to our knowledge, this is the first example of the design of a compact silent self-stabilizing algorithm constructing, and stabilizing on a subset of optimal solutions to a natural problem for which there are no time-efficient proof-labeling schemes. On our way to design our algorithm, we establish a set of independent results that may have interest on their own. In particular, we describe a new space-optimal silent self-stabilizing spanning tree construction, stabilizing on \emph{any} spanning tree, in $O(n)$ rounds, and using just \emph{one} additional bit compared to the size of the labels used to certify trees. We also design a silent loop-free self-stabilizing algorithm for transforming a tree into another tree. Last but not least, we provide a silent self-stabilizing algorithm for computing and certifying the labels of a NCA-labeling scheme.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Rumor Spreading in Random Evolving Graphs

Randomized gossip is one of the most popular way of disseminating information in large scale networks. This method is appreciated for its simplicity, robustness, and efficiency. In the "push" protocol, every informed node selects, at every time step (a.k.a. round), one of its neighboring node uniformly at random and forwards the information to this node. This protocol is known to complete information spreading in $O(\log n)$ time steps with high probability (w.h.p.) in several families of $n$-node "static" networks. The Push protocol has also been empirically shown to perform well in practice, and, specifically, to be robust against dynamic topological changes. In this paper, we aim at analyzing the Push protocol in "dynamic" networks. We consider the "edge-Markovian" evolving graph model which captures natural temporal dependencies between the structure of the network at time $t$, and the one at time $t+1$. Precisely, a non-edge appears with probability $p$, while an existing edge dies with probability $q$. In order to fit with real-world traces, we mostly concentrate our study on the case where $p=Ω(1/n)$ and $q$ is constant. We prove that, in this realistic scenario, the Push protocol does perform well, completing information spreading in $O(\log n)$ time steps w.h.p. Note that this performance holds even when the network is, w.h.p., disconnected at every time step (e.g., when $p << (\log n) / n$). Our result provides the first formal argument demonstrating the robustness of the Push protocol against network changes. We also address other ranges of parameters $p$ and $q$ (e.g., $p+q=1$ with arbitrary $p$ and $q$, and $p=1/n$ with arbitrary $q$). Although they do not precisely fit with the measures performed on real-world traces, they can be of independent interest for other settings. The results in these cases confirm the positive impact of dynamism.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

What can be decided locally without identifiers?

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.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Randomized Distributed Decision

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.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Delays Induce an Exponential Memory Gap for Rendezvous in Trees

The aim of rendezvous in a graph is meeting of two mobile agents at some node of an unknown anonymous connected graph. In this paper, we focus on rendezvous in trees, and, analogously to the efforts that have been made for solving the exploration problem with compact automata, we study the size of memory of mobile agents that permits to solve the rendezvous problem deterministically. We assume that the agents are identical, and move in synchronous rounds. We first show that if the delay between the starting times of the agents is arbitrary, then the lower bound on memory required for rendezvous is Omega(log n) bits, even for the line of length n. This lower bound meets a previously known upper bound of O(log n) bits for rendezvous in arbitrary graphs of size at most n. Our main result is a proof that the amount of memory needed for rendezvous with simultaneous start depends essentially on the number L of leaves of the tree, and is exponentially less impacted by the number n of nodes. Indeed, we present two identical agents with O(log L + loglog n) bits of memory that solve the rendezvous problem in all trees with at most n nodes and at most L leaves. Hence, for the class of trees with polylogarithmically many leaves, there is an exponential gap in minimum memory size needed for rendezvous between the scenario with arbitrary delay and the scenario with delay zero. Moreover, we show that our upper bound is optimal by proving that Omega(log L + loglog n)$ bits of memory are required for rendezvous, even in the class of trees with degrees bounded by 3.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Local Distributed Decision

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.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Decidability Classes for Mobile Agents Computing

We establish a classification of decision problems that are to be solved by mobile agents operating in unlabeled graphs, using a deterministic protocol. The classification is with respect to the ability of a team of agents to solve the problem, possibly with the aid of additional information. In particular, our focus is on studying differences between the decidability of a decision problem by agents and its verifiability when a certificate for a positive answer is provided to the agents. We show that the class MAV of mobile agents verifiable problems is much wider than the class MAD of mobile agents decidable problems. Our main result shows that there exist natural MAV-complete problems: the most difficult problems in this class, to which all problems in MAV are reducible. Our construction of a MAV-complete problem involves two main ingredients in mobile agents computability: the topology of the quotient graph and the number of operating agents. Beyond the class MAV we show that, for a single agent, three natural oracles yield a strictly increasing chain of relative decidability classes.

0 citations0 reviewsNo code linkedOpen access