The question of "what can be computed locally?" lies at the heart of distributed computing in networks. As established in Naor and Stockmeyer's seminal paper (STOC 1993, Edsger W. Dijkstra Prize in Distributed Computing 2025), this question is undecidable, even for graph problems whose solutions can be checked locally. In this paper, we adopt a novel perspective on the question, by asking for which classes Π of problems, and for which classes G of graphs, all problems in Π can be solved efficiently in a distributed manner in all graphs of G. This paper focuses on two natural candidates for such an approach, namely the class of problems expressible in first-order logic (FO), because they possess an intrinsic form of locality thanks to Gaifman's theorem, and the class of graphs with bounded expansion, because they form a large class of graphs encompassing, e.g., planar, bounded-genus, bounded-treewidth, and bounded-degree graphs, as well as graphs excluding a fixed minor or topological minor, sparse Erdös--Rényi graphs (a.a.s.), and several network models such as stochastic block models for suitable parameter ranges.

Abstract We establish that every monadic second-order logic (MSO) formula on graphs with bounded treedepth is decidable in a constant number of rounds within the model. To our knowledge, this marks the first meta-theorem regarding distributed model checking. Various optimization problems on graphs are expressible in MSO. Examples include determining whether a graph G has a clique of size k , whether it admits a coloring with k colors, whether it contains a graph H as a subgraph or minor, or whether terminal vertices in G could be connected via vertex-disjoint paths. Our meta-theorem significantly enhances the work of Bousquet et al. (in: 41st ACM Symposium on Principles of Distributed Computing (PODC), 2022), which was focused on distributed certification of MSO on graphs with bounded treedepth. Moreover, our results can be extended to solving optimization and counting problems expressible in MSO, in graphs of bounded treedepth.

International audience

A key result of distributed computing in asynchronous systems is a characterization for the wait-free solvability of colorless tasks by the existence of a continuous map from the task's input complex (representing the valid input configurations) to its output complex (representing the valid output configurations) which respects that task's specification. This natural characterization led to many proofs, mainly of impossibility: showing that a colorless task is not wait-free solvable, can be done by proving that there is no continuous map (respecting the task's specification) between two simplicial complexes, which can be done using classical topological machinery.

We study the awake complexity of graph problems that belong to the class O-LOCAL, which includes a subset of problems solvable by sequential greedy algorithms, such as (Δ + 1)-coloring and maximal independent set. It is known from previous work that, in n-node graphs of maximum degree Δ, any problem in the class O-LOCAL can be solved by a deterministic distributed algorithm with awake complexity O (log Δ + log* n).

We establish that for every first-order logic (FO) formula ϕ, which captures a vast number of computational problems on graphs, and every graph class G of bounded expansion, there exists a deterministic distributed algorithm that, for any n-node graph G ∈ G with diameter D, determines whether G ⊨ ϕ within O(D+log n) rounds in the standard CONGEST model. Graph classes of bounded expansion encompass many well-known families of sparse graphs, including planar graphs, bounded-genus graphs, bounded-treedepth graphs, bounded-treewidth graphs, bounded-degree graphs, graphs that exclude a fixed graph H as a minor or topological minor, random graphs with constant average degree (a.a.s.), and many network models (e.g., stochastic block models) for some ranges of parameters.

Consensus is arguably the most studied problem in distributed computing as a whole, and particularly in the distributed message-passing setting. In this latter framework, research on consensus has considered various hypotheses regarding the failure types, the memory constraints, the algorithmic performances (e.g., early stopping and obliviousness), etc. Surprisingly, almost all of this work assumes that messages are passed in a complete network, i.e., each process has a direct link to every other process. A noticeable exception is the recent work of Castañeda et al. (Inf. Comput. 2023) who designed a generic oblivious algorithm for consensus running in radius(G,t) rounds in every graph G, when up to t nodes can crash by irrevocably stopping, where t is smaller than the node-connectivity κ of G. Here, radius(G,t) denotes a graph parameter called the radius of G whenever up to t nodes can crash. For t = 0, this parameter coincides with radius(G), the standard radius of a graph, and, for G = K_n, the running time radius(K_n,t) = t+1 of the algorithm exactly matches the known round-complexity of consensus in the clique K_n. Our main result is a proof that radius(G,t) rounds are necessary for oblivious algorithms solving consensus in G when up to t nodes can crash, thus validating a conjecture of Castañeda et al., and demonstrating that their consensus algorithm is optimal for any graph G. We also extend the result of Castañeda et al. to two different settings: First, to the case where the number t of failures is not necessarily smaller than the connectivity κ of the considered graph; Second, to the k-set agreement problem for which agreement is not restricted to be on a single value as in consensus, but on up to k different values.

We develop a new lower bound for k-set agreement in synchronous message-passing systems connected by an arbitrary directed communication network, where up to t processes may crash. Our result thus generalizes the ⌊t/k⌋ + 1 lower bound for complete networks in the t-resilient model by Chaudhuri, Herlihy, Lynch, and Tuttle [JACM 2000]. Moreover, it generalizes two lower bounds for oblivious algorithms in synchronous systems connected by an arbitrary undirected communication network known to the processes, namely, the domination number-based lower bound by Castañeda, Fraigniaud, Paz, Rajsbaum, Roy, and Travers [TCS 2021] for failure-free processes, and the radius-based lower bound in the t-resilient model by Fraigniaud, Nguyen, and Paz [STACS 2024]. Our topological proof non-trivially generalizes and extends the connectivity-based approach for the complete network, as presented in the book by Herlihy, Kozlov, and Rajsbaum (2013). It is based on a sequence of shellable carrier maps that, starting from a shellable input complex, determine the evolution of the protocol complex: During the first ⌊t/k⌋ rounds, carrier maps that crash exactly k processes per round are used, which ensure high connectivity of their images. A Sperner’s lemma style argument can thus be used to prove that k-set agreement is still impossible by that round. From round ⌊t/k⌋ + 1 up to our actual lower bound, a novel carrier map is employed, which maintains high connectivity. As a by-product, our proof also provides a strikingly simple lower-bound for k-set agreement in synchronous systems with an arbitrary communication network, where exactly t ≥ 0 processes crash initially, i.e., before taking any step. We demonstrate that the resulting additional agreement overhead can be expressed via an appropriately defined radius of the communication graphs, and show that the usual input pseudosphere complex for k-set agreement can be replaced by an exponentially smaller input complex based on Kuhn triangulations, which we prove to be also shellable.

We consider a stochastic network model consisting of a set of n synchronous processes communicating by message passing. In each round, processes send messages directly to each other over a complete communication graph. The processes do not fail, but messages can be lost. Each message is delivered with probability p, for a given parameter p ∈ [0,1]. We study the following optimization version of approximate agreement in this model. We assume that processes start with binary input values, execute an algorithm for a fixed number of rounds, and decide values in [0,1] satisfying the usual validity requirement stating that if all processes start with the same input value, then they should all decide that value. We propose deterministic algorithms that minimize the expected discrepancy, namely, the expected maximum distance between the decided values. We also present lower bounds on the expected discrepancy, which demonstrate the optimality of our algorithms for two processes. Finally, we present applications of our algorithms to solve randomized consensus and randomized approximate agreement.

Abstract We study two fundamental problems of distributed computing, consensus and approximate agreement, through a novel approach for proving lower bounds and impossibility results, that we call the asynchronous speedup theorem. For a given n-process task $$\Pi $$ Π and a given computational model M, we define a new task, called the closure of $$\Pi $$ Π with respect to M. The asynchronous speedup theorem states that if a task $$\Pi $$ Π is solvable in $$t\ge 1$$ t ≥ 1 rounds in M, then its closure w.r.t. M is solvable in $$t-1$$ t - 1 rounds in M. We prove this theorem for iterated models, as long as the model allows solo executions. We illustrate the power of our asynchronous speedup theorem by providing a new proof of the wait-free impossibility of consensus using read/write registers, and a new proof of the wait-free impossibility of solving consensus using registers and test&set objects for $$n>2$$ n > 2 . The proof is merely by showing that, in each case, the closure of consensus (w.r.t. the corresponding model) is consensus itself. Our main application is the study of the power of additional objects, namely test&set and binary consensus, for wait-free solving approximate agreement faster. By analyzing the closure of approximate agreement w.r.t. each of the two models, we show that while these objects are more powerful than read/write registers from the computability perspective, they are not more powerful as far as helping solving approximate agreement faster is concerned.

The celebrated Asynchronous Computability Theorem of Herlihy and Shavit (JACM 1999) provided a topological characterization of the tasks that are wait-free solvable by processes communicating through writing and reading shared registers. This characterization assumes the use of full-information protocols, in which each time a process writes in the shared memory, it communicates everything it learned since the beginning of the execution. Thus, each register in the shared memory is of unbounded size. Whether unbounded size registers are unavoidable for the model of computation to be universal is the central question studied in this paper. More generally, when at most t out of n processes can crash, is the model with bounded size registers universal?

We establish that every monadic second-order logic (MSO) formula on graphs with bounded treedepth is decidable in a constant number of rounds within the CONGEST model. To our knowledge, this marks the first meta-theorem regarding distributed model-checking. Various optimization problems on graphs are expressible in MSO. Examples include determining whether a graph G has a clique of size k, whether it admits a coloring with k colors, whether it contains a graph H as a subgraph or minor, or whether terminal vertices in G could be connected via vertex-disjoint paths. Our meta-theorem significantly enhances the work of Bousquet et al. [PODC 2022], which was focused on distributed certification of MSO on graphs with bounded treedepth. Moreover, our results can be extended to solving optimization and counting problems expressible in MSO, in graphs of bounded treedepth.

We show that, for every k ≥ 2, C2k-freeness can be decided in O(n1--1/k) rounds in the CONGEST model by a randomized Monte-Carlo distributed algorithm with one-sided error probability 1/3. This matches the best round-complexities of previously known algorithms for k ∈ {2, 3, 4, 5} by Drucker et al. [PODC'14] and Censor-Hillel et al. [DISC'20], but improves the complexities of the known algorithms for k > 5 by Eden et al. [DISC'19], which were essentially of the form Õ (n1--2/k2). Our algorithm uses colored BFS-explorations with threshold, but with an original global approach that enables to overcome a recent impossibility result by Fraigniaud et al. [SIROCCO'23] about using colored BFS-exploration with local threshold for detecting cycles.

The topological view on distributed computing represents a task T as a relation Δ between the complex ℐ of its inputs and the complex 𝒪 of its outputs. A cornerstone result in the field is an elegant computability characterization of the solvability of colorless tasks in terms of ℐ, 𝒪 and Δ. Essentially, a colorless task is wait-free solvable if and only if there is a continuous map from the geometric realization of ℐ to that of 𝒪 that respects Δ. This paper makes headway towards providing an analogous characterization for general tasks, which are not necessarily colorless, by concentrating on the case of three-process inputless tasks. Our key contribution is identifying local articulation points as an obstacle for the solvability of general tasks, and defining a topological deformation on the output complex of a task T, which eliminates these points by splitting them, to obtain a new task T', with an adjusted relation Δ' between the input complex ℐ and an output complex 𝒪' without articulation points. We obtain a new characterization of wait-free solvability of three-process general tasks: T is wait-free solvable if and only if there is a continuous map from the geometric realization of ℐ to that of 𝒪' that respects Δ'.

We revisit asynchronous computing in networks of crash-prone processes, under the asynchronous variant of the standard LOCAL model, recently introduced by Fraigniaud et al. [DISC 2022]. We focus on the vertex coloring problem, and our contributions concern both lower and upper bounds for this problem. On the upper bound side, we design an algorithm tolerating an arbitrarily large number of crash failures that computes an $O(Δ^2)$-coloring of any $n$-node graph of maximum degree $Δ$, in $O(\log^\star n)$ rounds. This extends Linial's seminal result from the (synchronous failure-free) LOCAL model to its asynchronous crash-prone variant. Then, by allowing a dependency on $Δ$ on the runtime, we show that we can reduce the colors to $\big(\frac12(Δ+1)(Δ+2)-1 \big)$. For cycles (i.e., for $Δ=2$), our algorithm achieves a 5-coloring of any $n$-node cycle, in $O(\log^\star n)$ rounds. This improves the known 6-coloring algorithm by Fraigniaud et al., and fixes a bug in their algorithm, which was erroneously claimed to produce a 5-coloring. On the lower bound side, we show that, for $k<5$, and for every prime integer~$n$, no algorithm can $k$-color the $n$-node cycle in the asynchronous crash-prone variant of LOCAL, independently from the round-complexities of the algorithms. This lower bound is obtained by reduction from an original extension of the impossibility of solving weak symmetry-breaking in the wait-free shared-memory model. We show that this impossibility still holds even if the processes are provided with inputs susceptible to help breaking symmetry.

We establish that every monadic second-order logic (MSO) formula on graphs with bounded treedepth is decidable in a constant number of rounds within the CONGEST model. To our knowledge, this marks the first meta-theorem regarding distributed model-checking. Various optimization problems on graphs are expressible in MSO. Examples include determining whether a graph $G$ has a clique of size $k$, whether it admits a coloring with $k$ colors, whether it contains a graph $H$ as a subgraph or minor, or whether terminal vertices in $G$ could be connected via vertex-disjoint paths. Our meta-theorem significantly enhances the work of Bousquet et al. [PODC 2022], which was focused on distributed certification of MSO on graphs with bounded treedepth. Moreover, our results can be extended to solving optimization and counting problems expressible in MSO, in graphs of bounded treedepth.

Consensus is arguably the most studied problem in distributed computing as a whole, and particularly in distributed message-passing settings. Research on consensus has considered various failure types, memory constraints, and much more. Surprisingly, almost all of this work assumes that messages are passed in a complete network, i.e., each process has a direct link to every other process. Set agreement, a relaxed variant of consensus, has also been heavily studied in different settings, yet research on it has also been limited to complete networks. We address this situation by considering consensus and set agreement in general networks, i.e., that can have an arbitrary graph G as their communication graph. We focus on fault-prone networks, where up to t nodes may crash and irrevocably stop communicating, and present upper and lower bounds for such networks. We establish the following collection of results: - The consensus algorithm by [Castañeda et al., 2023] is optimal for all graphs, and not only for symmetric graphs. - This algorithm can be extended to a generic algorithm for k-set agreement, for every k ≥ 1. For k = 1, our generic algorithm coincides with the existing one for consensus. - All these algorithms can be extended to the case where the number t of failures exceeds the connectivity κ of the graph, while the existing consensus algorithm assumed that t < κ.

The task of the broadcast problem is, given a graph G and a source vertex s, to compute the minimum number of rounds required to disseminate a piece of information from s to all vertices in the graph. It is assumed that, at each round, an informed vertex can transmit the information to at most one of its neighbors. The broadcast problem is known to NP-hard. We show that the problem is FPT when parametrized by the size k of a feedback edge set, or by the size k of a vertex cover, or by k=n−t, where t is the input deadline for the broadcast protocol to complete.

For k ≥ 0, k-partial (k+1)-coloring asks to color the nodes of an n-node graph using a palette of k+1 colors such that every node v has at least min{k,deg(v)} neighbors colored with colors different from its own color. Hence, proper (Δ+1)-coloring is the special case of k-partial (k+1)-coloring when k = Δ. Ghaffari and Kuhn [FOCS 2021] recently proved that there exists a deterministic distributed algorithm that solves proper (Δ+1)-coloring of n-node graphs with maximum degree Δ in O(log n ⋅ log²Δ) rounds under the LOCAL model of distributed computing. This breakthrough result is achieved via an original iterated rounding approach. Using the same technique, Ghaffari and Kuhn also showed that there exists a deterministic algorithm that solves proper O(a)-coloring of n-node graphs with arboricity a in O(log n ⋅ log³a) rounds. It directly follows from this latter result that k-partial O(k)-coloring can be solved deterministically in O(log n ⋅ log³k) rounds. We develop an extension of the Ghaffari and Kuhn algorithm for proper (Δ+1)-coloring, and show that it solves k-partial (k+1)-coloring, thus generalizing their main result. Our algorithm runs in O(log n ⋅ log³k) rounds, like the algorithm that follows from Ghaffari and Kuhn’s algorithm for graphs with bounded arboricity, but uses only k+1 color, i.e., the smallest number c of colors such that every graph has a k-partial c-coloring. Like all the previously mentioned algorithms, our algorithm actually solves the general list-coloring version of the problem. Specifically, every node v receives as input an integer demand d(v) ≤ deg(v), and a list of at least d(v)+1 colors. Every node must then output a color from its list such that the resulting coloring satisfies that every node v has at least d(v) neighbors with colors different from its own. Our algorithm solves this problem in O(log n ⋅ log³k) rounds where k = max_v d(v). Moreover, in the specific case where all lists of colors given to the nodes as input share a common colors c^* known to all nodes, one can save one log k factor. In particular, for standard k-partial (k+1)-coloring, which corresponds to the case where all nodes are given the same list {1,… ,k+1}, one can modify our algorithm so that it runs in O(log n ⋅ log²k) rounds, and thus matches the complexity of Ghaffari and Kuhn’s algorithm for (Δ+1)-coloring for k = Δ.

The paper compares two generic techniques for deriving lower bounds and impossibility results in distributed computing. First, we prove a speedup theorem (a-la Brandt, 2019), for wait-free colorless algorithms, aiming at capturing the essence of the seminal round-reduction proof establishing a lower bound on the number of rounds for 3-coloring a cycle (Linial, 1992), and going by backward induction. Second, we consider FLP-style proofs, aiming at capturing the essence of the seminal consensus impossibility proof (Fischer, Lynch, and Paterson, 1985) and using forward induction. We show that despite their very different natures, these two forms of proof are tightly connected. In particular, we show that for every colorless task $Π$, if there is a round-reduction proof establishing the impossibility of solving $Π$ using wait-free colorless algorithms, then there is an FLP-style proof establishing the same impossibility. For 1-dimensional colorless tasks (for an arbitrary number $n\geq 2$ of processes), we prove that the two proof techniques have exactly the same power, and more importantly, both are complete: if a 1-dimensional colorless task is not wait-free solvable by $n\geq 2$ processes, then the impossibility can be proved by both proof techniques. Moreover, a round-reduction proof can be automatically derived, and an FLP-style proof can be automatically generated from it. Finally, we illustrate the use of these two techniques by establishing the impossibility of solving any colorless covering task of arbitrary dimension by wait-free algorithms.

A proof-labeling scheme (PLS) for a boolean predicate Π on labeled graphs is a mechanism used for certifying the legality with respect to Π of global network states in a distributed manner. In a PLS, a certificate is assigned to each processing node of the network, and the nodes are in charge of checking that the collection of certificates forms a global proof that the system is in a correct state, by exchanging the certificates once, between neighbors only. The main measure of complexity is the size of the certificates. Many PLSs have been designed for certifying specific predicates, including cycle-freeness, minimum-weight spanning tree, planarity, etc. In 2021, a breakthrough has been obtained, as a "meta-theorem" stating that a large set of properties have compact PLSs in a large class of networks. Namely, for every MSO₂ property Π on labeled graphs, there exists a PLS for Π with O(log n)-bit certificates for all graphs of bounded tree-depth. This result has been extended to the larger class of graphs with bounded tree-width, using certificates on O(log² n) bits. We extend this result even further, to the larger class of graphs with bounded clique-width, which, as opposed to the other two aforementioned classes, includes dense graphs. We show that, for every MSO₁ property Π on labeled graphs, there exists a PLS for Π with O(log² n)-bit certificates for all graphs of bounded clique-width. As a consequence, certifying families of graphs such as distance-hereditary graphs and (induced) P₄-free graphs (a.k.a., cographs) can be done using a PLS with O(log² n)-bit certificates, merely because each of these two classes can be specified in MSO₁. In fact, we show that certifying P₄-free graphs can be done with certificates on O(log n) bits only. This is in contrast to the class of C₄-free graphs (which does not have bounded clique-width) which requires Ω̃(√n)-bit certificates.

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 an 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 ∈ {0,1}ⁿ together with an index i ∈ [n], Bob is given a binary vector y ∈ {0,1}ⁿ together with an index j ∈ [n], and, after a single round of 2-way communication, Alice must output a boolean out_A, and Bob must output a boolean out_B, such that out_A ∧ out_B = x_j⊕ y_i. We show that the communication complexity of XOR-Index is Ω(n) bits.

Many exceptionally high-quality doctoral dissertations were submitted for the 2022 Principles of Distributed Computing Doctoral Dissertation Award. After careful long deliberation, the award committee decided to share the award among two:

We present a wait-free algorithm for proper coloring the n ≥ 3 nodes of the asynchronous cycle Cn, where each crash-prone node starts with its (unique) identifier as input. The algorithm is independent of n and uses up to five colors, and each node terminates upon completing at most O(log*n) write-read-compute steps.

We study two fundamental problems of distributed computing, consensus and approximate agreement, through a novel approach for proving lower bounds and impossibility results, that we call the asynchronous speedup theorem. For a given n-process task Ρ and a given computational model M, we define a new task, called the closure of Ρ with respect to M. The asynchronous speedup theorem states that if a task Ρ is solvable in t ≥ 1 rounds in M, then its closure w.r.t. M is solvable in t ≥ 1 rounds in M. We prove this theorem for iterated models, as long as the model allows solo executions. We illustrate the power of our asynchronous speedup theorem by providing a new proof of the wait-free impossibility of consensus using read/write registers, and a new proof of the wait-free impossibility of solving consensus using registers and test&set objects for > 2. The proof is merely by showing that, in each case, the closure of consensus (w.r.t. the corresponding model) is consensus itself. Our main application is the study of the power of additional objects, namely test&set and binary consensus, for wait-free solving approximate agreement faster. By analyzing the closure of approximate agreement w.r.t. each of the two models, we show that while these objects are more powerful than read/write registers from the computability perspective, they are not more powerful as far as helping solving approximate agreement faster is concerned.

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.

We present a wait-free algorithm for proper coloring the n nodes of the asynchronous cycle C_n, where each crash-prone node starts with its (unique) identifier as input. The algorithm is independent of n ≥ 3, and runs in O(log^*n) rounds in C_n. This round-complexity is optimal thanks to a known matching lower bound, which applies even to synchronous (failure-free) executions. The range of colors used by our algorithm, namely {0,…,4}, is optimal too, thanks to a known lower bound on the minimum number of names for which renaming is solvable wait-free in shared-memory systems, whenever n is a power of a prime. Indeed, our model coincides with the shared-memory model whenever n = 3, and the minimum number of names for which renaming is possible in 3-process shared-memory systems is 5.

Runtime verification is a lightweight method for monitoring the formal specification of a system during its execution. It has recently been shown that a given state predicate can be monitored consistently by a set of crash-prone asynchronous distributed monitors observing the system, only if each monitor can emit verdicts taken from a large enough finite set. We revisit this impossibility result in the concrete context of linear-time logic ( ltl ) semantics for runtime verification, that is, when the correctness of the system is specified by an ltl formula on its execution traces. First, we show that monitors synthesized based on the 4-valued semantics of ltl ( rv-ltl ) may result in inconsistent distributed monitoring, even for some simple ltl formulas. More generally, given any ltl formula φ, we relate the number of different verdicts required by the monitors for consistently monitoring φ, with a specific structural characteristic of φ called its alternation number . Specifically, we show that, for every k ≥ 0 , there is an ltl formula φ with alternation number k that cannot be verified at runtime by distributed monitors emitting verdicts from a set of cardinality smaller than k + 1. On the positive side, we define a family of logics, called distributed ltl (abbreviated as dltl ), parameterized by k ≥ 0, which refines rv-ltl by incorporating 2k + 4 truth values. Our main contribution is to show that, for every k ≥ 0, every ltl formula φ with alternation number k can be consistently monitored by distributed monitors, each running an automaton based on a (2 ⌈ k /2 ⌉ +4)-valued logic taken from the dltl family.

No abstract available.

Studying distributed computing through the lens of algebraic topology has been the source of many significant breakthroughs during the last two decades, especially in the design of lower bounds or impossibility results for deterministic algorithms. In a nutshell, this approach consists of capturing all the possible states of a distributed system at a certain time as a simplicial complex called protocol complex, and viewing computation as a simplicial map from that complex to the so-called output complex, that captures all possible legal output states of the system.

Given any task $Π$, Brandt's speedup theorem (PODC 2019) provides a mechanical way to design another task~$Π'$ on the same input-set as $Π$ such that, for any $t\geq 1$, $Π$ is solvable in $t$ rounds if and only if $Π'$ is solvable in $t-1$ rounds. The theorem applies to the anonymous variant of the LOCAL model, in graphs with sufficiently large girth, and to locally checkable labeling (LCL) tasks. In this paper, using combinatorial topology applied to distributed computing, we dissect the construction in Brandt's speedup theorem for expressing it in the broader framework of round-based models supporting full information protocols, which includes models as different as wait-free shared-memory computing with iterated immediate snapshots, and synchronous failure-free network computing. In particular, we provide general definitions for notions such as local checkability and local independence, in our broader framework. In this way, we are able to identify the hypotheses on the computing model, and on the tasks, that are sufficient for Brandt's speedup theorem to apply. More precisely, we identify which hypotheses are sufficient for the each direction of the if-and-only-if condition. Interestingly, these hypotheses are of different natures. Our general approach enables to extend Brandt's speedup theorem from LOCAL to directed networks, to hypergraphs, to dynamic networks, and even to graphs including short cyclic dependencies between processes (i.e., the large girth condition is, to some extend, not necessary). The theorem can even be extended to shared-memory wait-free computing. In particular, we provide new impossibility proofs for consensus and perfect renaming in 2-process systems.

Naor M., Parter M., Yogev E.: (The power of distributed verifiers in interactive proofs. In: 31st ACM-SIAM symposium on discrete algorithms (SODA), pp 1096–115, 2020. https://doi.org/10.1137/1.9781611975994.67 ) have recently demonstrated the existence of a 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 with the prover suffices, and randomization is unecessary, by providing an explicit description of a 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 locally checkable proofs—for planarity using certificates on $$o(\log n)$$ bits.

Abstract Distributed proofs are mechanisms that enable the nodes of a network to collectively and efficiently check the correctness of Boolean predicates on the structure of the network (e.g., having a specific diameter), or on objects distributed over the nodes (e.g., a spanning tree). We consider well known mechanisms consisting of two components: aproverthat assigns acertificateto each node, and a distributed algorithm called averifierthat is in charge of verifying the distributed proof formed by the collection of all certificates. 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 to establish perfect tradeoffs between thesize of the certificatestored at every node, and thenumber of roundsof the verification protocol.

Modeling distributed computing in a way enabling the use of formal methods is a challenge that has been approached from different angles, among which two techniques emerged at the turn of the century: protocol complexes, and directed algebraic topology. In both cases, the considered computational model generally assumes communication via shared objects (typically a shared memory consisting of a collection of read-write registers), or message-passing enabling direct communication between any pair of processes. Our paper is concerned with network computing, where the processes are located at the nodes of a network, and communicate by exchanging messages along the edges of that network (only neighboring processes can communicate directly). Applying the topological approach for verification in network computing is a considerable challenge, mainly because the presence of identifiers assigned to the nodes yields protocol complexes whose size grows exponentially with the size of the underlying network. However, many of the problems studied in this context are of local nature, and their definitions do not depend on the identifiers or on the size of the network. We leverage this independence in order to meet the above challenge, and present local protocol complexes, whose sizes do not depend on the size of the network. As an application of the design of "compacted" protocol complexes, we reformulate the celebrated lower bound of Ω(log^*n) rounds for 3-coloring the n-node ring, in the algebraic topology framework.

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.

Naor, Parter, and Yogev (SODA 2020) have recently demonstrated the existence of a 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 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 locally checkable proofs --- for planarity using certificates on o(log n) bits.

The paper tackles the issue of $\textit{checking}$ that all copies of a large data set replicated at several nodes of a network are identical. The fact that the replicas may be located at distant nodes prevents the system from verifying their equality locally, i.e., by having each node consult only nodes in its vicinity. On the other hand, it remains possible to assign $\textit{certificates}$ to the nodes, so that verifying the consistency of the replicas can be achieved locally. However, we show that, as the data set is large, classical certification mechanisms, including distributed Merlin-Arthur protocols, cannot guarantee good completeness and soundness simultaneously, unless they use very large certificates. The main result of this paper is a distributed $\textit{quantum}$ Merlin-Arthur protocol enabling the nodes to collectively check the consistency of the replicas, based on small certificates, and in a single round of message exchange between neighbors, with short messages. In particular, the certificate-size is logarithmic in the size of the data set, which gives an exponential advantage over classical certification mechanisms.

More than two decades ago, combinatorial topology was shown to be useful for analyzing distributed fault-tolerant algorithms in shared memory systems and in message passing systems. In this work, we show that combinatorial topology can also be useful for analyzing distributed algorithms in networks of arbitrary structure. To illustrate this, we analyze consensus, set-agreement, and approximate agreement in networks, and derive lower bounds for these problems under classical computational settings, such as the LOCAL model and dynamic networks.

The study of interactive proofs in the context of distributed network computing is a novel topic, recently introduced by Kol, Oshman, and Saxena [PODC 2018]. In the spirit of sequential interactive proofs theory, we study the power of distributed interactive proofs. This is achieved via a series of results establishing trade-offs between various parameters impacting the power of interactive proofs, including the number of interactions, the certificate size, the communication complexity, and the form of randomness used. Our results also connect distributed interactive proofs with the established field of distributed verification. In general, our results contribute to providing structure to the landscape of distributed interactive proofs.

On the one hand, the correctness of routing protocols in networks is an issue of utmost importance for guaranteeing the delivery of messages from any source to any target. On the other hand, a large collection of routing schemes have been proposed during the last two decades, with the objective of transmitting messages along short routes, while keeping the routing tables small. Regrettably, all these schemes share the property that an adversary may modify the content of the routing tables with the objective of, e.g. blocking the delivery of messages between some pairs of nodes, without being detected by any node. In this paper, we present a simple certification mechanism which enables the nodes to locally detect any alteration of their routing tables.In particular, we show how to locally verify the stretch-3 routing scheme by Thorup and Zwick, presented in SPAA in 2001, by adding certificates of the same order of magnitude as the original routing tables. We also propose a new name-independent routing scheme using routing tables of size O˜(n) bits at each node in n-node networks. This new routing scheme can be locally verified using certificates of O˜(n) bits. Its stretch is 3 if using handshaking, and 5 otherwise.

Error-correcting codes are efficient methods for handling 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 et al. (PODC 2014) that complex coordination tasks such as rumor spreading and 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}+\epsilon $$ , without using coding techniques. This result is a considerable step towards a better understanding of the way biological entities may cooperate. It has nevertheless been established only in the case of 2-valued 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 constant $$k\ge 2$$ . 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-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.

Coordinating the actions of agents (e.g., volunteers analyzing radio signals in SETI@home) yields efficient search algorithms. However, such an efficiency is often at the cost of implementing complex coordination mechanisms which may be expensive in terms of communication and/or computation overheads. Instead, non-coordinating algorithms, in which each agent operates independently from the others, are typically very simple, and easy to implement. They are also inherently robust to slight misbehaviors, or even crashes of agents. In this article, we investigate the “price of non-coordinating,” in terms of search performance, and we show that this price is actually quite small. Specifically, we consider a parallel version of a classical Bayesian search problem, where set of k ≥1 searchers are looking for a treasure placed in one of the boxes indexed by positive integers, according to some distribution p . Each searcher can open a random box at each step, and the objective is to find the treasure in a minimum number of steps. We show that there is a very simple non-coordinating algorithm which has expected running time at most 4(1−1/ k +1) 2 OPT+10, where OPT is the expected running time of the best fully coordinated algorithm. Our algorithm does not even use the precise description of the distribution p , but only the relative likelihood of the boxes. We prove that, under this restriction, our algorithm has the best possible competitive ratio with respect to OPT. For the case where a complete description of the distribution p is given to the search algorithm, we describe an optimal non-coordinating algorithm for Bayesian search. This latter algorithm can be twice as fast as our former algorithm in practical scenarios such as uniform distributions. All these results provide a complete characterization of non-coordinating Bayesian search. The take-away message is that, for their simplicity and robustness, non-coordinating algorithms are viable alternatives to complex coordinating mechanisms subject to significant overheads. Most of these results apply as well to linear search, in which the indices of the boxes reflect their relative importance, and where important boxes must be visited first.

Distributed tasks such as constructing a maximal independent set (MIS) in a network, or properly coloring the nodes or the edges of a network with reasonably few colors, are known to admit efficient distributed randomized algorithms. Those algorithms essentially proceed according to some simple generic rules, by letting each node choosing a temptative value at random, and checking whether this choice is consistent with the choices of the nodes in its vicinity. If this is the case, then the node outputs the chosen value, else it repeats the same process. Although such algorithms are, with high probability, running in a polylogarithmic number of rounds, they are not robust against actions performed by rational but selfish nodes. Indeed, such nodes may prefer specific individual outputs over others, e.g., because the formers suit better with some individual constraints. For instance, a node may prefer not being placed in a MIS as it is not willing to serve as a relay node. Similarly, a node may prefer not being assigned some radio frequencies (i.e., colors) as these frequencies would interfere with other devices running at that node. In this paper, we show that the probability distribution governing the choices of the output values in the generic algorithm can be tuned such that no nodes will rationally deviate from this distribution. More formally, and more generally, we prove that the large class of so-called LCL tasks, including MIS and coloring, admit simple "Luby's style" algorithms where the probability distribution governing the individual choices of the output values forms a Nash equilibrium. In fact, we establish the existence of a stronger form of equilibria, called symmetric trembling-hand perfect equilibria for those games.

This paper demonstrates that the Preferential Attachment rule naturally emerges in the context of evolutionary network formation, as the unique Nash equilibrium of a simple social network game. In this game, each node aims at maximizing its degree in the future, representing its social capital in the "society" formed by the nodes and their connections. This result provides additional formal support to the commonly used Preferential Attachment model, initially designed to capture the "rich get richer" aphorism. In the process of establishing our result, we expose new connections between Preferential Attachment, random walks, and Young»s Lattice.

Distributed property testing in networks has been introduced by Brakerski and Patt-Shamir (2011), with the objective of detecting the presence of large dense sub-networks in a distributed manner. Recently, Censor-Hillel et al. (2016) have shown how to detect 3-cycles in a constant number of rounds by a distributed algorithm. In a follow up work, Fraigniaud et al. (2016) have shown how to detect 4-cycles in a constant number of rounds as well. However, the techniques in these latter works were shown not to generalize to larger cycles Ck with k ≥ 5. In this paper, we completely settle the problem of cycle detection, by establishing the following result. For every k ≥ 3, there exists a distributed property testing algorithm for Ck-freeness, performing in a constant number of rounds. All these results hold in the classical congest/ model for distributed network computing. Our algorithm is 1-sided error. Its round-complexity is O(1/ε) where ε ∈(0,1) is the property testing parameter measuring the gap between legal and illegal instances.

We are considering distributed network computing, in which computing entities are connected by a network modeled as a connected graph. These entities are located at the nodes of the graph, and they exchange information by message-passing along its edges. In this context, we are adopting the classical framework for local distributed decision, in which nodes must collectively decide whether their network configuration satisfies some given boolean predicate, by having each node interacting with the nodes in its vicinity only. A network configuration is accepted if and only if every node individually accepts. It is folklore that not every Turing-decidable network property (e.g., whether the network is planar) can be decided locally whenever the computing entities are Turing machines (TM). On the other hand, it is known that every Turing-decidable network property can be decided locally if nodes are running non-deterministic Turing machines (NTM). However, this holds only if the nodes have the ability to guess the identities of the nodes currently in the network. That is, for different sets of identities assigned to the nodes, the correct guesses of the nodes might be different. If one asks the nodes to use the same guess in the same network configuration even with different identity assignments, i.e., to perform identity-oblivious guesses, then it is known that not every Turing-decidable network property can be decided locally. In this paper, we show that every Turing-decidable network property can be decided locally if nodes are running alternating Turing machines (ATM), and this holds even if nodes are bounded to perform identity-oblivious guesses. More specifically, we show that, for every network property, there is a local algorithm for ATMs, with at most 2 alternations, that decides that property. To this aim, we define a hierarchy of classes of decision tasks where the lowest level contains tasks solvable with TMs, the first level those solvable with NTMs, and level k contains those tasks solvable with ATMs with k alternations. We characterize the entire hierarchy, and show that it collapses in the second level. In addition, we show separation results between the classes of network properties that are locally decidable with TMs, NTMs, and ATMs. Finally, we establish the existence of completeness results for each of these classes, using novel notions of local reduction.

In this paper we present distributed testing algorithms of graph properties in the CONGEST-model [Censor-Hillel et al. 2016]. We present one-sided error testing algorithms in the general graph model. We first describe a general procedure for converting $ε$-testers with a number of rounds $f(D)$, where $D$ denotes the diameter of the graph, to $O((\log n)/ε)+f((\log n)/ε)$ rounds, where $n$ is the number of processors of the network. We then apply this procedure to obtain an optimal tester, in terms of $n$, for testing bipartiteness, whose round complexity is $O(ε^{-1}\log n)$, which improves over the $poly(ε^{-1} \log n)$-round algorithm by Censor-Hillel et al. (DISC 2016). Moreover, for cycle-freeness, we obtain a \emph{corrector} of the graph that locally corrects the graph so that the corrected graph is acyclic. Note that, unlike a tester, a corrector needs to mend the graph in many places in the case that the graph is far from having the property. In the second part of the paper we design algorithms for testing whether the network is $H$-free for any connected $H$ of size up to four with round complexity of $O(ε^{-1})$. This improves over the $O(ε^{-2})$-round algorithms for testing triangle freeness by Censor-Hillel et al. (DISC 2016) and for testing excluded graphs of size $4$ by Fraigniaud et al. (DISC 2016). In the last part we generalize the global tester by Iwama and Yoshida (ITCS 2014) of testing $k$-path freeness to testing the exclusion of any tree of order $k$. We then show how to simulate this algorithm in the CONGEST-model in $O(k^{k^2+1}\cdotε^{-k})$ rounds.

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(log^2 n) bits, respectively, are error-sensitive, as long as the trees are locally represented by adjacency lists, and not just by parent pointers.

In this paper we analyse the core-periphery clustering properties of collaboration networks, where the core of a network is formed by the nodes with highest degree. In particular, we first observe that, even for random graph models aiming at matching the degree-distribution and/or the clustering coefficient of real networks, these models produce synthetic graphs which have a spatial distribution of the triangles with respect to the core and to the periphery which does not match the spatial distribution of the triangles in the real networks. We therefore propose a new model, called CPCL, whose aim is to distribute the triangles in a way fitting with their real core-periphery distribution, and thus producing graphs matching the core-periphery clustering of real networks.

Locally finding a solution to symmetry-breaking tasks such as vertex-coloring, edge-coloring, maximal matching, maximal independent set, etc., is a long-standing challenge in distributed network computing. More recently, it has also become a challenge in the framework of centralized local computation. We introduce conflict coloring as a general symmetry-breaking task that includes all the aforementioned tasks as specific instantiations - conflict coloring includes all locally checkable labeling tasks from [Naor & Stockmeyer, STOC 1993]. Conflict coloring is characterized by two parameters l and d, where the former measures the amount of freedom given to the nodes for selecting their colors, and the latter measures the number of constraints which colors of adjacent nodes are subject to. We show that, in the standard LOCAL model for distributed network computing, if l/d > Δ, then conflict coloring can be solved in Õ(√Δ)+log*n rounds in n-node graphs with maximum degree Δ, where Õ ignores the polylog factors in Δ. The dependency in n is optimal, as a consequence of the Ω(log*n) lower bound by [Linial, SIAM J. Comp. 1992] for (Δ + 1)-coloring. An important special case of our result is a significant improvement over the best known algorithm for distributed (Δ + 1)-coloring due to [Barenboim, PODC 2015], which required Õ(Δ3/4) + log*n rounds. Improvements for other variants of coloring, including (Δ + 1)-list-coloring, (2Δ-1)-edge-coloring, coloring with forbidden color distances, etc., also follow from our general result on conflict coloring. Likewise, in the framework of centralized local computation algorithms (LCAs), our general result yields an LCA which requires a smaller number of probes than the previously best known algorithm for vertex-coloring, and works for a wide range of coloring problems.

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 Omega(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 Omega(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.

Adaptive renaming can be viewed as a coordination task involving a set of asynchronous agents, each aiming at grabbing a single resource out of a set of resources totally ordered by their desirability. We consider a generalization of adaptive renaming to take into account scenarios in which resources are not independent.

Error-correcting codes are efficient methods for handling 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 rumor spreading and 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 1 over 2 + ε, without using coding techniques. This result is a considerable step towards a better understanding of the way biological entities may cooperate. It has nevertheless been established only in the case of 2-valued 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 constant k≥2.

We analyse 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. Clearly, the best strategy of a single searcher would be to open the boxes one by one, in increasing order. Moreover, by equally dividing the workload between them, k searchers can trivially 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 focus our attention on identifying 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 k/4(1+1/k)2 for any k≥ 1 searchers. Thus, asymptotically, the speed-up is only four times worse compared to the case of full coordination. Moreover, these bounds are tight in a strong sense as no non-coordinating search algorithm can achieve better speed-ups. Our algorithms are surprisingly simple and hence applicable. However they are memory intensive and so we suggest a practical, memory efficient version, with a speed-up of (k2 − 1)/4k. That is, it is only a factor of (k+1)/(k−1) slower than the optimal algorithm. 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.

In this article, we solve the ancestry -labeling scheme problem, which aims at assigning the shortest possible labels (bit strings) to nodes of rooted trees, so ancestry queries between any two nodes can be answered by inspecting their assigned labels only. This problem was introduced more than 20 years ago by Kannan et al. [1988] 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 + Ω(log log n ) bits lower bound given by Alstrup et al. [2003]. 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 a depth of at most d , the simplified ancestry scheme enjoys label size of log 2 n + 2log 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 + 3log 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 Õ ( n k ) for the family of n -element posets with a tree dimension of at most k . Up to lower-order terms, this bound is tight thanks to a lower bound of n k − o (1) by to Alon and Scheinerman [1988].

Self-stabilizing algorithms are distributed algorithms supporting transient failures. Starting from any configuration, they allow the system to detect whether the actual configuration is legal, and, if not, they allow the system to eventually reach a legal configuration. In the context of network computing, it is known that, for every task, there is a self-stabilizing algorithm solving that task, with optimal space-complexity, but converging in an exponential number of rounds. On the other hand, it is also known that, for every task, there is a self-stabilizing algorithm solving that task in a linear number of rounds, but with large space-complexity. It is however not known whether for every task there exists a self-stabilizing algorithm that is simultaneously space-efficient and time-efficient. In this paper, we make a first attempt for answering the question of whether such an efficient algorithm exists for every task, by focussing on constrained spanning tree construction tasks. We present a general roadmap for the design of silent space-optimal self-stabilizing algorithms solving such tasks, converging in polynomially many rounds under the unfair scheduler. By applying our roadmap to the task of constructing minimum-weight spanning tree (MST), and to the task of constructing minimum-degree spanning tree (MDST), we provide algorithms that outperform previously known algorithms designed and optimized specifically for solving each of these two tasks.

Proof-labeling schemes, introduced by Korman, Kutten and Peleg [PODC 2005], are a mechanism to certify that a network configuration satisfies a given boolean predicate. Such mechanisms find applications in many contexts, e.g., the design of fault-tolerant distributed algorithms. In a proof-labeling scheme, predicate verification consists of neighbors exchanging labels, whose contents depends on the predicate. In this paper, we introduce the notion of randomized proof-labeling schemes where messages are randomized and correctness is probabilistic. We show that randomization reduces label size exponentially while guaranteeing probability of correctness arbitrarily close to one. In addition, we present a novel label-size lower bound technique that applies to both deterministic and randomized proof-labeling schemes. Using this technique, we establish several tight bounds on the verification complexity of MST, acyclicity, connectivity, and longest cycle size.

In this paper, we carry on investigating the line of research questioning the power of randomization for the design of distributed algorithms. In their seminal paper, Naor and Stockmeyer [STOC 1993] established that, in the context of network computing, in which all nodes execute the same algorithm in parallel, any construction task that can be solved locally by a randomized Monte-Carlo algorithm can also be solved locally by a deterministic algorithm. This result however holds in a specific context. In particular, it holds only for distributed tasks whose solutions can be locally checked by a deterministic algorithm. In this paper, we extend the result of Naor and Stockmeyer to a wider class of tasks. Specifically, we prove that the same derandomization result holds for every task whose solutions can be locally checked using a 2-sided error randomized Monte-Carlo algorithm. This extension finds applications to, e.g., the design of lower bounds for construction tasks which tolerate that some nodes compute incorrect values. In a nutshell, we show that randomization does not help for solving such resilient tasks.

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 has property P by having each node run a constant-time distributed decision algorithm. In a yes-instance all nodes should output yes, while in a no-instance at least one node should output no.

A central theme in distributed network algorithms concerns understanding and coping with the issue of 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( t ) (for local decision ) as the class of decision problems that can be solved in 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( t , p , q ), containing all languages for which there exists a randomized algorithm that runs in t rounds, accepts correct instances with probability at least p , and rejects incorrect ones with probability at least q . We show that p 2 + q = 1 is a threshold for the containment of LD( t ) in BPLD( t , p , q ). More precisely, we show that there exists a language that does not belong to LD( t ) for any t = o ( n ) but does belong to BPLD( 0 , p , q ) for any p , q ∈ (0,1) such that p 2 + q ≤ 1. On the other hand, we show that, restricted to hereditary languages, BPLD( t , p , q )=LD( O ( t )), for any function t , and any p , 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.

The aim of rendezvous in a graph is meeting of two mobile agents at some node of an unknown anonymous connected graph. In this article, 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 Ω (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 ℓ 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 ℓ + log log n ) bits of memory that solve the rendezvous problem in all trees with at most n nodes and at most ℓ 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 Ω (log ℓ + log log n ) bits of memory are required for rendezvous, even in the class of trees with degrees bounded by 3.

When playing the boolean game (δ,f), two players, upon reception of respective inputs x and y, must respectively output a and b satisfying δ(a, b)=f(x, y), in absence of any communication. It is known that, for δ(a, b)=a ⊕ b, the ability for the players to use entangled quantum bits (qbits) helps. In this paper, we show that, for δ different from the exclusive-or operator, quantum correlations do not help. This result is an invitation to revisit the theory of distributed checking, a.k.a. distributed verification, currently sticked to the usage of decision functions δ based on the AND-operator, hence potentially preventing us from using the potential benefit of quantum effects.

A central theme in distributed network algorithms concerns understanding and coping with the issue of locality. 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(t) (for local decision) as the class of decision problems that can be solved in 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(t,p,q), containing all languages for which there exists a randomized algorithm that runs in t rounds, accepts correct instances with probability at least p and rejects incorrect ones with probability at least q. We show that p2+q = 1 is a threshold for the containment of LD(t) in BPLD(t,p,q). More precisely, we show that there exists a language that does not belong to LD(t) for any t=o(n) but does belong to BPLD(0,p,q) for any p,q ∈ (0,1] such that p2+q≤1. On the other hand, we show that, restricted to hereditary languages, BPLD(t,p,q) = LD(O(t)), for any function t and any p,q ∈ (0,1] such that p2+q>;1. In addition, we investigate the impact of non-determinism on local decision, and establish some structural results inspired by classical computational complexity theory. Specifically, we show that non-determinism does help, but that this help is limited, as there exist languages that cannot be decided non-deterministically. Perhaps surprisingly, it turns out that it is the combination of randomization with non-determinism that enables to decide all languages in constant time. Finally, we introduce the notion of local reduction, and establish some completeness results.

We extend and relax the concept of tree-farm previously implicitly introduced for the design of the multicast protocol SplitStream. Our extension enables the tree-farm concept to be applied to non vertex-symmetric overlay networks. In particular, we demonstrate that, in the case of the de Bruijn overlay network used in P2P systems such as Koorde and D2B, our relaxed notion of tree-farm achieves higher multicast throughput than when using a single BFS tree rooted at every source, or when the sources share a common set of trees like in PrefixStream.

Network representations play an important role in many domains of computer science, ranging from data structures and graph algorithms, to parallel and distributed computing, and communication networks. Traditional network representations are usually global in nature. That is, in order to retrieve useful information, one must access a global data structure representing the entire network, even if the desired information is solely local, pertaining to only a few nodes. In contrast, the notion of informative labeling schemes suggests the use of a local representation of the network. The principle is to associate a label with each node, selected in a way that enables to infer information about any two nodes directly from their labels, without using any additional sources of information. Hence in essence, this method bases the entire representation on the set of labels alone. Obviously, labels of unrestricted size can be used to encode any desired information, including in particular the entire graph structure. The focus is thus on informative labeling schemes which use labels as short as possible.This talk will introduce the notion of informative labeling scheme to the audience, and will survey some of the important results achieved in this context. In particular, we will focus on the design of compact adjacency-, ancestry-, and distance-labeling schemes for trees. These schemes find applications in various contexts, including the design of small universal graphs, and the design of small universal posets. We will actually specifically emphasis the importance of ancestry- labeling scheme for the design of compact such schemes finds applications in XML search engines. In this context, even small improvements in the label size are important, and we will survey the most recent results in this domain.The interested person is referred to the following paper, that includes pointers to many of the most important references on informative labeling schemes: Pierre Fraigniaud and Amos Korman, Compact Ancestry Labeling Schemes for XML Trees, in ACM-SIAM Symposium on Discrete Algorithms (SODA), 2010.

Roughly speaking, and if one ignores important research topics driven by modern applications of distributed computing (like, e.g., P2P systems and multi-core technology), the PODC community can be viewed as the union of two non-necessarily disjoint sub-communities. One is mostly focussing on the combined impact of asynchronism and faults on distributed computation, while the other is mostly focussing on the impact of network structural properties on distributed computation. Both communities address various forms of distributed computational complexities, through the analysis of different concepts. This includes, e.g., failure detectors and wait-free hierarchy for the former community, and compact labeling schemes and computing with advice for the latter community. This talk will describe examples taken from these latter frameworks aiming at demonstrating that many important notions of Distributed Computing seem to fit well with standard computational complexity, although they are not expressed using the traditional computational complexity format, i.e., complexity classes. The thesis that will be defended in the talk is that the traditional computational complexity format might well apply to Distributed Computing, and that our community may in fact take benefit from expressing its main challenges in this standard framework for making them accessible to a wider audience.

We study the communication complexity of rumor spreading in the random phone-call model. Suppose nplayers communicate in parallel rounds, where in each round every player calls a randomly selected communication partner. A player u is allowed to exchange messages during a round only with the player that u called, and with all the players that $u$ received calls from, in that round. In every round, a (possibly empty) set of rumors to be distributed among all players is generated, and each of the rumors is initially placed in a subset of the players. Karp et. al \cite{Karp2000} showed that no rumor-spreading algorithm that spreads a rumor to all players with constant probability can be both time-optimal, taking O(lg n) rounds, and message-optimal, using O(n) messages per rumor. For address-oblivious algorithms, in particular, they showed that Ω(n lg lg n) messages per rumor are required, and they described an algorithm that matches this bound and takes O(lg n) rounds.

The aim of rendezvous in a graph is meeting of two mobile agents at some node of an unknown anonymous connected graph. The two identical agents start from arbitrary nodes in the graph and move from node to node with the goal of meeting. 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.

Revisiting the "small-world" experiments of the '60s, Kleinberg observed that individuals are very effective at constructing short chains of acquaintances between any two people, and he proposed a mathematical model of this phenomenon. In this model, individuals are the nodes of a base graph, the square grid, capturing the underlying structure of the social network; and this base graph is augmented with additional edges from each node to a few long-range contacts of this node, chosen according to some natural distance-based distribution. In this augmented graph, a greedy search algorithm takes only a polylogarithmic number of steps in the graph size. Following this work, several papers investigated the correlations between underlying structure and long-range connections that yield efficient decentralized search, generalizing Kleinberg's results to broad classes of underlying structures, such as metrics of bounded doubling dimension, and minor-excluding graphs.

In this paper, we solve the ancestry problem, which 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. Specifically, we construct an ancestry labeling scheme for n-node trees with label size log2 n + O(log log n) bits, thus matching the log2 n + Ω(log log n) bits lower bound given by Alstrup et al. [SODA '03]. Besides its optimal label size, our scheme assigns the labels in linear time, and guarantees that any ancestry query can be answered in constant time. In addition to its potential impact in terms of improving the performances of XML search engines, our ancestry scheme is also useful in the context of partially ordered sets. Specifically, for any fixed integer k, our scheme enables the construction of a universal poset of size O(nk log4k n) for the family of n-element posets with tree-dimension at most k. This bound is almost tight thanks to a lower bound of nk-o(1) due to Alon and Scheinerman [Order '88].

In his seminal work, Kleinberg showed how to augment meshes using random edges, so that they become navigable; that is, greedy routing computes paths of polylogarithmic expected length between any pairs of nodes. This yields the crucial question of determining whether such an augmentation is possible for all graphs. In this paper, we answer this question negatively by exhibiting an infinite family of graphs that cannot be augmented to become navigable whatever the distribution of random edges is. Precisely, it was known that graphs of doubling dimension at most $O(\log\log n)$ are navigable. We show that for doubling dimension $\gg\log\log n$, an infinite family of graphs cannot be augmented to become navigable. Finally, we present a positive navigability result by studying the special case of square meshes of arbitrary dimension that we prove to always be augmentable to become navigable. This latter result complements Kleinberg's original result and shows that adding extra links can sometimes break the navigability.

An edge-Markovian process with birth-rate p and death-rate q generates sequences of graphs (G0,G1,G2,…) with the same node set [n] such that Gt is obtained from Gt−1 as follows: if e ∉ E(Gt−1) then e ∈ E(Gt) with probability p, and if e ∈ E(Gt−1) then e ∉ E(Gt) with probability q. Clementi et al. (PODC 2008) analyzed thoroughly information dissemination in such dynamic graphs, by establishing bounds on their flooding time--flooding is the basic mechanism in which every node becoming aware of an information at step t forwards this information to all its neighbors at all forthcoming steps t∦ > t. In this paper, we establish tight bounds on the complexity of flooding for all possible birth rates and death rates, completing the previous results by Clementi et al. Moreover, we note that despite its many advantages in term of simplicity and robustness, flooding suffers from its high bandwidth consumption. Hence we also show that flooding in dynamic graphs can be implemented in a more parsimonious manner, so that to save bandwidth, yet preserving efficiency in term of simplicity and completion time.

We analyze decentralized routing in small-world networks that combine a wide variation in node degrees with a notion of spatial embedding. Specifically, we consider a variation of Kleinberg's augmented-lattice model (STOC 2000), where the number of long-range contacts for each node is drawn from a power-law distribution. This model is motivated by the experimental observation that many "real-world" networks have power-law degrees. In such networks, the exponent α of the power law is typically between 2 and 3. We prove that, in our model, for this range of values, 2 < α < 3, the expected number of steps of greedy routing from any source to any target is O(logα-1 n) steps. This bound is tight in a strong sense. Indeed, we prove that the expected number of steps of greedy routing for a uniformly-random pair of source-target nodes is Ω(logα-1 n) steps. We also show that for α < 2 or α ≥ 3, greedy routing performs in Θ(log2 n) xexpected steps, and for α = 2, Θ(log1+ε n) expected steps are required, where 1/3 ≤ ε ≤ 1/2. To the best of our knowledge, these results are the first to formally quantify the effect of the power-law degree distribution on the navigability of small worlds. Moreover, they show that this effect is significant. In particular, as α approaches 2 from above, the expected number of steps of greedy routing in the augmented lattice with power-law degrees approaches the square-root of the expected number of steps of greedy routing in the augmented lattice with fixed degrees, although both networks have the same average degree.

Informative labeling schemes consist in labeling the nodes of graphs so that queries regarding any two nodes (e.g., are the two nodes adjacent?) can be answered by inspecting merely the labels of the corresponding nodes. Typically, the main goal of such schemes is to minimize the label size, that is, the maximum number of bits stored in a label. This concept was introduced by Kannan et al. [STOC'88] and was illustrated by giving very simple and elegant labeling schemes, for supporting adjacency and ancestry queries in n-node trees; both these schemes have label size 2log n. Motivated by relations between such schemes and other important notions such as universal graphs, extensive research has been made by the community to further reduce the label sizes of such schemes as much as possible. The current state of the art adjacency labeling scheme for trees has label size log n+O(log*n) by Alstrup and Rauhe [FOCS'02], and the best known ancestry scheme for (rooted) trees has label size log n+O(√log n) by Abiteboul et al., [SICOMP 2006].

A large amount of algorithms has recently been designed for the Internet under the assumption that the distance defined by the round-trip delay (RTT) is a metric. Moreover, many of these algorithms (e.g., overlay network construction, routing scheme design, sparse spanner construction) rely on the assumption that the metric has bounded ball growth or bounded doubling dimension. This paper analyzes the validity of these assumptions and proposes a tractable model matching experimental observations. On the one hand, based on Skitter data collected by CAIDA and King matrices of Meridian and P2PSim projects, we verify that the ball growth of the Internet, as well as its doubling dimension, can actually be quite large. Nevertheless, we observed that the doubling dimension is much smaller when restricting the measures to balls of large enough radius. Moreover, by computing the number of balls of radius r required to cover balls of radius R > r, we observed that this number grows with R much slower than what is predicted by a large doubling dimension. On the other hand, based on data collected on the PlanetLab platform by the All-Sites-Pings project, we confirm that the triangle inequality does not hold for a significant fraction of the nodes. Nevertheless, we demonstrate that RTT measures satisfy a weak version of the triangle inequality: there exists a small constant p such that for any triple u, v, w, we have RTT(u,v) les rho-max{RTT(u,w),RTT(w,v)}. (Smaller bounds on p can even be obtained when the triple u, v, w is skewed). We call inframetric a distance function satisfying this latter inequality. Inframetrics subsume standard metrics and ultrametrics. Based on inframetrics and on our observations concerning the doubling dimension, we propose an analytical model for Internet RTT latencies. This model is tuned by a small set of parameters concerning the violation of the triangle inequality and the geometrical dimension of the network. We demonstrate the tractability of our model by designing a simple and efficient compact routing scheme with low stretch. Precisely, the scheme has constant multiplicative stretch and logarithmic additive stretch.

We present a dynamic process for network evolution, aiming at explaining the emergence of the small world phenomenon. We prove that a local forgetting process combined with mobility produces shortcuts allowing navigability.

Graph augmentation theory is a general framework for analyzing navigability in social networks. It is known that, for large classes of graphs, there exist augmentations of these graphs such that greedy routing according to the shortest path metric performs in polylogarithmic expected number of steps. However, it is also known that there are classes of graphs for which no augmentations can enable greedy routing according to the shortest path metric to perform better than Ω(n1/√log n) expected number of steps. In fact, the best known universal bound on the greedy diameter of arbitrary graph is essentially n1/3. That is, for any graph, there is an augmentation such that greedy routing according to the shortest path metric performs in Õ(n1/3) expected number of steps. Hence, greedy routing according to the shortest path metric has at least two drawbacks. First, it is in general space-consuming to encode locally the shortest path distances to all the other nodes, and, second, greedy routing according to the shortest path metric performs poorly in some graphs.

A finite automaton, simply referred to as a robot , has to explore a graph, that is, visit all the nodes of the graph. The robot has no a priori knowledge of the topology of the graph, nor of its size. It is known that for any k -state robot, there exists a graph of maximum degree 3 that the robot cannot explore. This article considers the effects of allowing the system designer to add short labels to the graph nodes in a preprocessing stage, for helping the exploration by the robot. We describe an exploration algorithm that, given appropriate 2-bit labels (in fact, only 3-valued labels), allows a robot to explore all graphs. Furthermore, we describe a suitable labeling algorithm for generating the required labels in linear time. We also show how to modify our labeling scheme so that a robot can explore all graphs of bounded degree, given appropriate 1-bit labels. In other words, although there is no robot able to explore all graphs of maximum degree 3, there is a robot R, and a way to color in black or white the nodes of any bounded-degree graph G , so that R can explore the colored graph G . Finally, we give impossibility results regarding graph exploration by a robot with no internal memory (i.e., a single-state automaton).

Augmented graphs were introduced for the purpose of analyzing the "six degrees of separation between individuals" observed experimentally by the sociologist Standley Milgram in the 60's. Formally, an augmented graph is a pair (G,φ) where G is a graph, and φ is a collection of probability distributions {φu, u ∈ V(G)}. Every node u ∈ V(G) is given an extra link, called a long range link, pointing to some node v, called the long range contact of u. The head v of this link is chosen at random by Pr{u → v} = φu(v). In augmented graphs, greedy routing is the oblivious routing process in which every intermediate node chooses among all its neighbors (including its long range contact) the one that is closest to the target according to the distance measured in the underlying graph G, and forwards to it. Roughly, augmented graphs aim at modeling the structure of social networks, while greedy routing aims at modeling the searching procedure applied in Milgram's experiment. Our objective is to design efficient universal augmentation schemes, i.e., augmentation schemes that give to any graph G a collection of probability distributions φ such that greedy routing in (G,φ) is fast. It is known that the uniform scheme φunif is a universal scheme ensuring that, for any n-node graph G, greedy routing in (G,φunif) performs in O(√n) expected number of steps. Our main result is the design of a universal augmentation scheme φ such that greedy routing in (G,φ) performs in Õ(n1/3) expected number of steps for any n-node graph G. We also show that under some more restricted model, the √n-barrier cannot be overcome.

We use the recently introduced advising scheme framework for measuring the difficulty of locally distributively computing a Minimum Spanning Tree (MST). An (m,t)-advising scheme for a distributed problem P is a way, for every possible input I of P, to provide an "advice" (i.e., a bit string) about I to each node so that: (1) the maximum size of the advices is at most m bits, and (2) the problem P can be solved distributively in at most t rounds using the advices as inputs. In case of MST, the output returned by each node of a weighted graph G is the edge leading to its parent in some rooted MST T of G. Clearly, there is a trivial (log n,0)-advising scheme for MST (each node is given the local port number of the edge leading to the root of some MST T), and it is known that any (0,t)-advising scheme satisfies t ≥ Ω (√n). Our main result is the construction of an (O(1),O(log n))-advising scheme for MST. That is, by only giving a constant number of bits of advice to each node, one can decrease exponentially the distributed computation time of MST in arbitrary graph, compared to algorithms dealing with the problem in absence of any a priori information. We also consider the average size of the advices. On the one hand, we show that any (m,0)-advising scheme for MST gives advices of average size Ω(log n). On the other hand we design an (m,1)-advising scheme for MST with advices of constant average size, that is one round is enough to decrease the average size of the advices from log(n) to constant.

We study the problem of the amount of knowledge about a communication network that must be given to its nodes in order to efficiently disseminate information. While previous results about communication in networks used particular partial information available to nodes, such as the knowledge of the neighborhood or the knowledge of the network topology within some radius, our approach is quantitative: we investigate the minimum total number of bits of information (minimum oracle size) that has to be available to nodes in order to perform efficient communication.It turns out that the minimum oracle size for which a distributed task can be accomplished efficiently, can serve as a measure of the difficulty of this task. We use this measure to make a quantitative distinction between the difficulty of two apparently similar fundamental communication primitives: the broadcast and the wakeup. In both of them a distinguished node, called the source, has a message, which has to be transmitted to all other nodes of the network. In the wakeup, only nodes that already got the source message (i.e., are awake) can send messages to their neighbors, thus waking them up. In the broadcast, all nodes can send control messages even before getting the source message, thus potentially facilitating its future dissemination. In both cases we are interested in accomplishing the communication task with optimal message complexity, i.e., using a number of messages linear in the number of nodes.We show that the minimum oracle size permitting the wakeup with a linear number of messages in a n-node network, is Θ (n log n), while the broadcast with a linear number of messages can be achieved with an oracle of size O(n). We also show that the latter oracle size is almost optimal: no oracle of size o(n) can permit to broadcast with a linear number of messages. Thus an efficient wakeup requires strictly more information about the network than an efficient broadcast.

We consider small world graphs as defined by Kleinberg (2000), i.e., graphs obtained from a d-dimensional mesh by adding links chosen at random according to the d-harmonic distribution. This model aims at giving formal support to the "six degrees of separation" between individuals experienced by Milgram (1967),and verified recently by Dodds, Muhamad, and Watts (2003). In particular, Kleinberg shows that greedy routing performs in O(log2n) expected number of steps in d-dimensional augmented meshes, with O(log2n) bits of topological awareness per node, for any constant d ≥ 1. We show that giving O(log2n) bits of topological awareness per node decreases the expected number of steps of greedy routing to O(log1+1/dn) in d-dimensional augmented meshes. We also show that, independently of the amount of topological awareness given to the nodes, greedy routing performs in Ω(log1+1/dn) expected number of steps. In particular, augmenting the topological awareness above this optimum of O(log2n) bits would drastically decrease the performances of greedy routing. Moreover, our model demonstrates that the efficiency of greedy routing is sensible to the "world's dimension", in the sense that high dimensional worlds enjoy faster greedy routing than low dimensional ones. This could not be observed in Kleinberg's model. In addition to bringing new light to Milgram's experiment, our protocol presents several desirable properties. In particular, it is totally oblivious i.e., there is no header modification along the path from the source to the target, and the routing decision depends only on the target, and on information stored locally at each node. Finally, our protocol can obviously be used for the design of DHTs, in the same spirit as Symphony (2003).

This paper describes the new multicast protocol M/spl lambda/T, supporting QoS requirements. M/spl lambda/T is dedicated to any QoS parameter /spl lambda/ that is either additive (e.g., delay), or convex (e.g., available bandwidth). M/spl lambda/T constructs a multicast tree connecting a group of users such that, for any user x, the QoS /spl lambda/ supported by the path from the root of the tree to x is optimized under some constraints of bounded control traffic. Simulations on the UUNET network topology, as well as simulations on network topologies obtained by INET-3.0, show that M/spl lambda/T performs in average significantly better than QoSMIC, RSP strategies (e.g., CBT and PIM-SM), and greedy strategies.

In this brief announcement, we overview the structure and performances of the distributed hash table D2B described in [2] (a preliminary version appeared in [3]).

The aim of this paper is to study the computational power of the qualitative model, where entities are given distinct labels which are however mutually incomparable; this model is opposed to the quantitative model, where labels are integers. The qualitative model captures, for example,the case when the labels are written in different alphabets (e.g., Cyrillic, Latin) and there is no a priori agreement on a common encoding. We investigate the qualitative model through the problem of leader election in a distributed mobile environment. All known leader election protocols assume that the initial input values are distinct and pairwise comparable. While distinctness of the input values is clearly required, the comparability assumption is questionable. Our concern is whether it is possible to remove this comparability assumption. To focus solely on this concern, we consider theproblem in its weakest setting: anonymous highly symmetric networks (i.e.,Cayley graphs). In this way, to break the symmetry (and thus elect a leader) among the incomparable mobile agents, we can not rely on the existence of distinguished node labels nor on any topological asymmetry of the network. We describe a generic election protocol which is effective for all anonymous Cayley graphs; i.e., it solves the election problem if the problem is solvable, otherwise it determines that the problem is not solvable. For arbitrary networks, our protocol is conditionally effective; that is, it performs election of one agent among any set of agents in any network, under some weak conditions on the network and on the initial positions of the agents. Our work is a first step toward a better understanding of the inherent differences between "quantitative computing" where parameters are taken from a total order, and "qualitative computing" where parameters are taken from a partial order.

Abstract Several papers considered the problem of routing inad hocwireless networks using the positions of the mobile hosts. Perimeter routing 1 , 2 gives an algorithm that guarantees delivery of messages in such networks without the use of flooding of control packets. However, this protocol is likely to fail if the transmission ranges of the mobile hosts vary because of natural or man‐made obstacles. It may fail because either some connections are not considered, which effectively results in a disconnection of the network, or because some crossing connections are used, which could misdirect the message. In this paper, we describe a robust routing protocol, a variant of perimeter routing, which tolerates up to 40% of variation in the transmission ranges of the mobile hosts. More precisely, our protocol guarantees message delivery in a connected ad hoc wireless network without the use of message flooding whenever the ratio of the maximum transmission range to the minimum transmission range is at most √2. Copyright © 2003 John Wiley & Sons, Ltd.

Consider a team of mobile software agents deployed to capture a (possibly hostile) intruder in a network. All agents, including the intruder move along the network links; the intruder could be arbitrarily fast, and aware of the positions of all the agents. The problem is to design the agents' strategy for capturing the intruder. The main efficiency parameter is the size of the team. This is an instance of the well known graph-searching problem whose many variants have been extensively studied in the literature. In all existing solutions, and in all the variants of the problem, it is assumed that agents can be removed from their current location and placed in another network site arbitrarily and at any time. As a consequence, the existing optimal strategies cannot be employed in situations for which agents cannot access the network at any point, or cannot "jump" across the network, or cannot reach an arbitrary point of the network via an internal travel through insecure zones. This motivates the contiguous search problem in which agents cannot be removed from the network, and clear links must form a connected sub-network at any time, providing safety of movements. This new problem is NP-complete in general. We study it for tree networks, and we consider its more general version, the weighted case, which arises naturally when considering networks whose nodes and links are of different nature and thus require a different number of agents to be explored. We give a linear-time algorithm that computes, for any tree $T$, the minimum number of agents to capture the intruder, and the corresponding search strategy. Beside its optimality in time, our algorithm is naturally distributed: if $T$ is a processor-network, then the minimal search strategy for $T$ can be computed by $T$ in a decentralized manner, using a linear number of messages.

Abstract In this paper, we show how to give an orientation to the edges of an hypercube so that the inducedorientedhypercube offers approximately the same communication performance as that of the original nonoriented hypercube (routing, broadcasting, connectivity, etc.), that is, we show that it is possible to construct anN‐node oriented hypercube with the same communication and computational power as that of anN‐node hypercube, although with approximately the same pin‐complexity as that of a$\sqrt{N}$ ‐node hypercube. © 2002 Wiley Periodicals, Inc.

A parameterized model of hyperclusters of processors-clusters of clusters of... of clusters of processors-is formulated under which a hypercluster enjoys generality along three orthogonal axes: (1) Its processors are heterogeneous: they may have different computational powers (speed of computation and memory access). (2) Its constituent clusters are interconnected via a hierarchy of networks of possibly differing bandwidths and speeds. (3) Its clusters at each level of the hierarchy are heterogeneous: they may differ in size. The model accounts for architectural details such as the bandwidths and transit costs of both networks and their ports. The algorithmic tractability of the model is demonstrated via broadcast and reduction algorithms, which are predictably efficient in general and actually optimal in special circumstances.

Abstract Gossiping is an information dissemination problem in which each node of a communication network has a unique piece of information that must be transmitted to all other nodes using two‐way communications between pairs of nodes along the communication links of the network. In this paper, we study gossiping using a linear‐cost model of communication which includes a start‐up time and a propagation time which is proportional to the amount of information transmitted. A minimum linear gossip graph is a graph (modeling a network), with the minimum possible number of links, in which gossiping can be completed in minimum time under the linear‐cost model. For networks with an even number of nodes, we prove that the structure of minimum linear gossip graphs is independent of the relative values of the start‐up and unit propagation times. We prove that this is not true when the number of nodes is odd. We present four infinite families of minimum linear gossip graphs. We also present minimum linear gossip graphs for all even numbers of nodes n ≤ 32 except n = 22. A linear (Δ, k)‐gossip graph is a graph with maximum degree Δ in which gossiping can be completed in k rounds with minimum propagation time. We present three infinite families of maximal linear (Δ, k)‐gossip graphs, that is, linear (Δ, k)‐gossip graphs with a maximum number of nodes. We show that not all minimum broadcast graphs are maximal linear (Δ, k)‐gossip graphs. © 2001 John Wiley & Sons, Inc.

This paper is concerned with all-optical networks using deflection routing and time division multiplexing. Slotted networks make use of the synchronous arrival of the packets to the routers to minimize locally the number of deflections. We show that the difference in performance between slotted and unslotted networks is mainly due to the fact that unslotted networks cannot easily perform such local optimization. We also show that minimizing locally the number of deflections in unslotted networks gives rise to an NP-complete problem. To overcome this problem, we have designed a heuristic whose aim is to limit locally the number of deflections. We experimentally demonstrate that this heuristic enhances unslotted routing almost at the same performance level as slotted routing. As a consequence, we have shown that unslotted deflection routing can be implemented is a way which makes it a competitive alternative to slotted deflection routing for optical time division multiplexing deflection networks.

The purpose of compact routing is to provide a labeling of the nodes of a network, and a way to encode the routing tables so that routing can be performed efficiently (e.g., on shortest paths) while keeping the memory-space required to store the routing tables as small as possible. In this paper, we answer a long-standing conjecture by showing that compact routing can also help to perform distributed computations. In particular, we show that a network supporting a shortest path interval routing scheme allows to broadcast with an O(n) message-complexity, where n is the number of nodes of the network. As a consequence, we prove that O(n) messages suffice to solve leader-election for any graph labeled by a shortest path interval routing scheme, improving therefore the O(m + n) previous known bound.

We consider the task of distributedly assigning distinct labels to nodes of an unknown anonymous network. A priori, nodes do not have any identities (anonymous network) and do not know the topology or the size of the network (unknown network). They execute identical algorithms, apart from a distinguished node, called the source, which starts the labeling process. Our goal is to assign short labels, as fast as possible. The quality of a labeling algorithm is measured by the range from which the algorithm picks the labels, or alternatively, the length of the assigned labels. Natural efficiency measures are the time, i.e., the number of rounds required for the label assignment, and the message and bit complexities of the label assignment protocol, i.e., the total number of messages (resp., bits) circulating in the network. We present label assignment algorithms whose time and message complexity are asymptotically optimal and which assign short labels. On the other hand, we establish inherent trade-offs between quality and efficiency for labeling algorithms.

This paper addresses the one-to-all broadcasting problem and the one-to-many broadcasting problem, usually simply called broadcasting and multicasting, respectively. Broadcasting is the information dissemination problem in which a node of a network sends the same piece of information to all the other nodes. Multicasting is a partial broadcasting in the sense that only a subset of nodes forms the destination set. Both operations have many applications in parallel and distributed computing. In this paper, we study these problems in both line model, and cut-through model. The former assumes long distance calls between nonneighboring processors. The latter strengthens the line model by taking into account the use of a routing function. Long distance calls are possible in circuit-switched and wormhole-routed networks, and also in many networks supporting optical facilities. In the line model, it is well known that one can compute in polynomial time a [log/sub 2/n]-round broadcast or multicast protocol for any arbitrary network. Unfortunately such a protocol is often inefficient from a practical point of view because it does not use the resources of the network in a balanced way. In this paper, we present a new algorithm to compute broadcast or multicast protocols. This algorithm applies under both line and cut-through models. Moreover, it returns protocols that efficiently use the bandwidth of the network. From a complexity point of view, we also show that most of the optimization problems relative to the maximization of the efficiency of broadcast or multicast protocols in terms of switching time or vertex load are NP-complete. We have, however, derived polynomial efficient solutions for tree-networks.

Most machines of the last generation of distributed memory parallel computers possess specific routers which are used to exchange messages between nonneighboring nodes in the network. Among the several technologies, wormhole routing is usually preferred because it allows low channel-setup time and reduces the dependency between latency and internode distance. However, wormhole routing is very susceptible to deadlock because messages are allowed to hold many resources while requesting others. Therefore, designing deadlock-free routing algorithms using few hardware facilities is a major problem for wormhole-routed networks. In this paper, we describe a general theoretical framework for the study of deadlock-free routing functions. We give a general definition of what can be a routing function. This definition captures many specific definitions of the literature (e.g., vertex dependent, input-dependent, source-dependent, path-dependent etc.). Using our definition, we give a necessary and sufficient condition which characterizes deadlock-free routing functions. Our theory embraces, at a high level, most of the theories related to deadlock avoidance in wormhole-routed networks previously derived in the literature. In particular, it applies not only to one-to-one routing, but also to one-to-many routing. The latter paradigm is used to solve the multicast problem with the path-based or tree-based facility.

In this paper, we have experimentally compared synchronized versus asynchronous all-optical deflection networks. We have compared four routing modes: synchronous mode, partially synchronous mode, and asynchronous mode with fixed or bound packet sizes. Our experiments mainly show that the natural decrease of the performances of the asynchronous mode, compared to the synchronous mode, can be balanced in a significant way by the use of a sophisticated routing algorithm. Moreover, we have also shown that asynchronous routing is not very sensitive to bursty traffic. These results, and the fact that asynchronous networks are easier to design, and cheaper to build than synchronous networks, show the practical interest of asynchronous deflection routing.

Given a network of processors, a structured communication problem consists to route a communication pattern known in advance. Structured communication problems appear frequently in parallel computing. Hence, communication libraries (e.g, PVM or MPI) generally include a specific access to procedures solving the most common problems of this type. A standard communication model assumes that information proceeds by a sequence of calls between neighboring nodes of the network, and that each node is allowed to call at most one neighbor at a time. In this context, most of the decision problems corresponding to the usual structured communication problems have been shown to be NP-complete. Therefore, several approximation algorithms have been proposed to solve specific problems. Each of these algorithms is dedicated to a particular problem. In this paper, we present a high level method which can be used to derive approximation algorithms for many different structured communication problems on ...

Article Local memory requirement of universal routing schemes Share on Authors: Pierre Fraigniaud Laboratoire de l'Informatique du Parallélisme - CNRS École Normale Supérieure de Lyon, 69364 Lyon cedex 07, France Laboratoire de l'Informatique du Parallélisme - CNRS École Normale Supérieure de Lyon, 69364 Lyon cedex 07, FranceView Profile , Cyril Gavoille Laboratoire de l'Informatique du Parallélisme - CNRS École Normale Supérieure de Lyon, 69364 Lyon cedex 07, France Laboratoire de l'Informatique du Parallélisme - CNRS École Normale Supérieure de Lyon, 69364 Lyon cedex 07, FranceView Profile Authors Info & Claims SPAA '96: Proceedings of the eighth annual ACM symposium on Parallel Algorithms and ArchitecturesJune 1996 Pages 183–188https://doi.org/10.1145/237502.237541Published:24 June 1996 9citation144DownloadsMetricsTotal Citations9Total Downloads144Last 12 Months0Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Gossiping is an information dissemination problem in which each node of a communication network has a unique piece of information that must be transmitted to all the other nodes. A bus network is a network of processing elements that communicate by sending messages along buses in a sequence of calls. We assume that (i) each node can participate in at most one call at a time, (ii) a node can either send or receive on/ from a bus (exclusively), (iii) no more than one node can send a message on a given bus at a given time, and (iv) communicating a message on a bus takes a unit of time. This model extends the telegraph model in allowing the number of nodes connected to each bus to be as large as needed, instead of being bounded by 2. In this paper, we are interested in minimizing the “hardware” of a bus network in keeping optimal the communication performances for solving the gossiping problem. More precisely, we compute the minimum number of buses required for gossiping to be optimal. Similarly, we give upper bounds on the minimum length of buses required for gossiping to be optimal. Finally, we combine the two approaches in trying to minimize both parameters: length and number of buses. © 1996 John Wiley & Sons, Inc.

In this paper, we deal with the compact routing problem, that is implementing routing schemes that use a minimum memory size on each router. In [20], Peleg and Upfal showed that there is no hope to do that with less than a total \\Omega\\Gamma n 1+1=(2s+4) ) memory bits for any stretch factor s 1. We improve this bound for stretch factors s ! 2 by proving that any near-shortest path routing scheme uses a total of \\Omega\\Gamma n 2 ) memory bits.

Abstract Broadcasting is an information dissemination problem in which information originating at one node of a communication network (modeled as a graph) must be transmitted to all other nodes as quickly as possible. A broadcast graph is a graph which permits broadcasting from any originator in minimum time. in this paper, we present new methods for constructing sparse broadcast graphs. Our constructions are based on graph compounding operations which are relative to vertex sets with certain properties that depend on the broadcast protocols of the graphs. We show that many previous methods for constructing sparse broadcast graphs are special cases of our methods. We demonstrate our constructions by producing new sparse broadcast graphs and by showing how many previously constructed graphs can be obtained in a systematic way.

This article presents new multicasting algorithms for the mesh under the wormhole routing mode and using the read-and-route facility. These new algorithms perform generally faster than the algorithms previously described in the literature under the same model. We take, as criteria to compare the algorithms, the off-line computation time necessary to prepare the multicast, and the communication time to complete the multicast in absence of traffic. Moreover, since it is often not possible to derive useful expression for the communication time, we also simulate the algorithms.

Compact routing tables are useful to implement routing algorithms on a distributed memory parallel computer. Interval routing is a popular way of building such compact tables. It was already known that any network can support an interval routing function with only one interval per output port as soon as one allows intervals to be "cyclic" [13]. However, it might be interesting for practical reasons to allow only the use of "linear" intervals (see [2]). This notion is particularly useful to derive results on networks built by cartesian products (as hypercubes and torus) [4]. In this paper, we characterize the networks that admit a linear interval routing function with at most one interval per output port. We also characterize the networks that admit a strict linear interval routing function with at most one interval per output port.

Communication schemes based on store and forward routing, in which a processor can communicate simultaneously with all its neighbors (in parallel) are considered. Moreover, the authors assume that sending a message of length L from a node to a neighbor takes time $\beta + L\tau $. The authors give efficient broadcasting and gossiping protocols for the de Bruijn networks. To do this, arc-disjoint spanning trees of small depth rooted at a given vertex in de Bruijn digraphs are constructed.

We have studied various implementations of iterative polynomial root finding methods on a distributed memory multicomputer. These methods are based on the construction of a sequence of approximations that converge to the set of zeros. The synchronous version consists in sharing the computation of the next iterate among the processors and updating their data through a total exchange of their results. In order to decrease the communication cost, we introduce asynchronous versions. The computation of the next iterate is still shared among the processor, but the updating is done by using only nearest neighbor communications. We prove that under weak conditions, these asynchronous versions are still locally convergent, even if their convergence orders are reduced. We analyze the behavior of the asynchronous methods in function of their delay, the topology of the interconnection network, and the elementary computation and communication times. We have implemented and compared these methods on a hypercube multicomputer.>

Various algorithms for reliable broadcasting (one-to-all) and gossiping (all-to-all) in faulty n-dimensional hypercube multicomputers are described and analyzed. For a broadcast (resp., a gossiping algorithm), the goal is that each processor receives complete information from the source (resp., from all the other processors) even in the presence of faults. One of the main characteristics of the proposed algorithms is that no information on the identity of the faulty nodes/links is required. Exchanges between processors are realized such that multiple copies of the same message move through disjoint paths. Solutions are proposed for systems which use a store-and-forward model of communication, the cost of the message transfer between two neighboring processors being modeled by the sum of a startup time plus a propagation time. Two cases are studied: (1) when processors can simultaneously communicate with all their neighbors at any time, and (2) when communications can take place with only one neighbor at a given time. The algorithms are asymptotically optimal. Optimal solutions for very short messages are also proposed. The speedup of these broadcasting algorithms over those designed for unitary length messages is about a factor of n. The gossiping algorithms require the minimum possible number of time steps and packet transmissions.>