Structural Information and Communication Complexity

In this article, we study the Leader Election Problem in the Signal-to-Interference-plus-Noise-Ratio (SINR) model where nodes can adjust their transmission power. We show that in this setting it is possible to solve the leader election problem in two communication rounds, with high probability. Previously, it was known that \(\varOmega (\log n)\) rounds were sufficient and necessary when using uniform power, where n is the number of nodes in the network.

We then examine how much power control is needed to achieve fast leader election. We show that any 2-round leader election algorithm in the SINR model running correctly w.h.p. requires a power range \(2^{\varOmega (n)}\) even when n is known. We match this with an algorithm that uses power range \(2^{\tilde{O}(n)}\), when n is known and \(2^{\tilde{O}(n^{1.5})}\), when n is not known. We also explore tradeoffs between time and power used, and show that to elect a leader in t rounds, a power range \(exp(n^{1/\varTheta (t)})\) is sufficient and necessary.

Communication problems in ad hoc wireless networks have been already widely studied under the SINR model, but a vast majority of results concern networks with constraints on connectivity, so called strongly-connected networks. What happens if the network is not strongly-connected, e.g., it contains some long but still viable “shortcut links” connecting transmission boundaries? Even a single broadcast in such ad hoc weakly-connected networks with uniform transmission powers requires \(\varOmega (n)\) communication rounds, where n is the number of nodes in the network. The best up-to-date (randomized) distributed algorithm, designed by Daum et al. [10], accomplishes broadcast task in \(O(n\log ^2n)\). In this work we show a novel deterministic distributed implementation of token traversal in the SINR model with uniform transmission powers and no restriction on connectivity. We show that it is efficient even in a very harsh model of weakly-connected networks without GPS, carrier sensing and other helping features. We apply this method to span a traversal tree and accomplish broadcast in \(O(n\log N)\) communication rounds, deterministically, provided nodes are equipped with unique IDs in the range [1, N] for \(N\ge n\). This result implies an \(O(n\log n)\)-round randomized solution that does not require IDs, which improves the result from [10]. The lower bound \(\varOmega (n\log N)\) for deterministic algorithms proved in our work shows that our result is tight without randomization. Our implementation of token traversal routine is based on a novel implicit algorithmic carrier sensing method and a new type of selectors, which might be of independent interest.

We consider the problem of topology recognition in wireless (radio) networks modeled as undirected graphs. Topology recognition is a fundamental task in which every node of the network has to output a map of the underlying graph i.e., an isomorphic copy of it, and situate itself in this map. In wireless networks, nodes communicate in synchronous rounds. In each round a node can either transmit a message to all its neighbors, or stay silent and listen. At the receiving end, a node v hears a message from a neighbor w in a given round, if v listens in this round, and if w is its only neighbor that transmits in this round. Nodes have labels which are (not necessarily different) binary strings. The length of a labeling scheme is the largest length of a label. We concentrate on wireless networks modeled by trees, and we investigate two problems.

We are interested in deterministic topology recognition algorithms. For the first problem, we show that the minimum length of a labeling scheme allowing topology recognition in all trees of maximum degree \(\varDelta \ge 3\) is \(\varTheta (\log \log \varDelta )\). For such short schemes, used by an algorithm working for the class of trees of diameter \(D\ge 4\) and maximum degree \(\varDelta \ge 3\), we show almost matching bounds on the time of topology recognition: an upper bound \(O(D\varDelta )\), and a lower bound \(\varOmega (D\varDelta ^{\epsilon })\), for any constant \(\epsilon <1\).

Our upper bounds are proven by constructing a topology recognition algorithm using a labeling scheme of length \(O(\log \log \varDelta )\) and using time \(O(D\varDelta )\). Our lower bounds are proven by constructing a class of trees for which any topology recognition algorithm must use a labeling scheme of length at least \(\varOmega (\log \log \varDelta )\), and a class of trees for which any topology recognition algorithm using a labeling scheme of length \(O(\log \log \varDelta )\) must use time at least \(\varOmega (D\varDelta ^{\epsilon })\), on some tree of this class.

Verifying that a network configuration satisfies a given boolean predicate is a fundamental problem in distributed computing. Many variations of this problem have been studied, for example, in the context of proof labeling schemes (\(\mathrm {PLS}\)), locally checkable proofs (\(\mathrm {LCP}\)), and non-deterministic local decision (\(\mathrm {NLD}\)). In all of these contexts, verification time is assumed to be constant. Korman et al. [16] presented a proof-labeling scheme for MST, with poly-logarithmic verification time, and logarithmic memory at each vertex.

In this paper we introduce the notion of a \(t\text {-}\mathrm {PLS}\), which allows the verification procedure to run for super-constant time. Our work analyzes the tradeoffs of \(t\text {-}\mathrm {PLS}\) between time, label size, message length, and computation space. We construct a universal \(t\text {-}\mathrm {PLS}\) and prove that it uses the same amount of total communication as a known one-round universal \(\mathrm {PLS}\), and t factor smaller labels. In addition, we provide a general technique to prove lower bounds for space-time tradeoffs of \(t\text {-}\mathrm {PLS}\). We use this technique to show an optimal tradeoff for testing that a network is acyclic (cycle free). Our optimal \(t\text {-}\mathrm {PLS}\) for acyclicity uses label size and computation space \(O((\log n)/t)\). We further describe a recursive \(O(\log ^* n)\) space verifier for acyclicity which does not assume previous knowledge of the run-time t.

In this work, we extend this model by defining the approximate proof-labeling scheme (APLS) model. In this new model, the predicates for verification are of the form \(\psi \le \varphi \), where \(\psi , \varphi : \mathcal{F}\rightarrow \mathbb {N}\) for a family of configurations \(\mathcal{F}\). Informally, the predicates considered in this model are a comparison between two values of the configuration. As in the PLS model, nodes exchange labels in order to locally verify the predicate, and all must accept if the network satisfies the predicate. The soundness condition is relaxed with an approximation ration \(\alpha \), so that only if \(\psi > \alpha \varphi \) some node must reject.

We show that in the APLS model, the proof size can be much smaller than the proof size of the same predicate in the PLS model. Moreover, we prove that there is a tradeoff between the approximation ratio and the proof size.

This paper studies what can be computed by using probabilistic local interactions with agents with a very restricted power in polylogarithmic parallel time.

If identifiers are added (corresponding to the Community Protocol model by Guerraoui and Ruppert), then more global predicates over the input multiset can be computed. Local predicates over the input sorted according to the identifiers can also be computed, as long as the identifiers are ordered. The time of some of those predicates might require exponential parallel time.

In this paper, we consider what can be computed with Community Protocol in a polylogarithmic number of parallel interactions. We introduce the class CPPL corresponding to protocols that use \(O(n\log ^kn)\), for some k, expected interactions to compute their predicates, or equivalently a polylogarithmic number of parallel expected interactions.

We provide some computable protocols, some boundaries of the class, using the fact that the population can compute its size. We also prove two impossibility results providing some arguments showing that local computations are no longer easy: the population does not have the time to compare a linear number of consecutive identifiers. The Linearly Local languages, such that the rational language \((ab)^*\), are not computable.

We study the fundamental enumeration problem in asynchronous message-passing networks. Anonymous processes have to eventually decide on pairwise distinct identifiers, despite all starting in the same initial state. It is known since Angluin’s seminal result [2] that some grain of salt is required for distributed algorithms to solve the problem, e.g., the system needs to have a non-symmetrical topology or unbiased independent random bits.

The starting point of this paper is the observation that these approaches demand too strong assumptions. In short, by adding time to the picture, we show that the enumeration problem can be solved with far less. The idea is to consider a schedule of events in a distributed system as a space-time structure that is gradually learnt by the processes. We introduce the notion of divergence time which essentially measures the time by which the causal order induced by the system schedule has differentiated all the processes.

We prove lower bounds on the running time of any algorithm solving enumeration in terms of divergence time. In particular, we show that any adversary scheduler against which the enumeration problem can be solved necessarily selects schedules with finite divergence time.

We prove that this last condition is sufficient: we present the Torche algorithm which solves enumeration for all schedules with finite divergence time. In this sense, having finite divergence time is the smallest grain of salt required to solve the enumeration problem.

We consider collaborative graph exploration with a set of k agents. All agents start at a common vertex of an initially unknown graph with n vertices and need to collectively visit all other vertices. We assume agents are deterministic, moves are simultaneous, and we allow agents to communicate globally. For this setting, we give the first non-trivial lower bounds that bridge the gap between small (\(k \le \sqrt{n}\)) and large (\(k \ge n\)) teams of agents. Remarkably, our bounds tightly connect to existing results in both domains.

First, we significantly extend a lower bound of \(\varOmega (\log k / \log \log k)\) by Dynia et al. on the competitive ratio of a collaborative tree exploration strategy to the range \(k \le n \log ^c n\) for any \(c \in \mathbb {N}\). Second, we provide a tight lower bound on the number of agents needed for any competitive exploration algorithm. In particular, we show that any collaborative tree exploration algorithm with \(k=Dn^{1+o(1)}\) agents has a competitive ratio of \(\omega (1)\), while Dereniowski et al. gave an algorithm with \(k=Dn^{1+\varepsilon }\) agents and competitive ratio \(\mathcal {O}(1)\), for any \(\varepsilon > 0\) and with D denoting the diameter of the graph. Lastly, we show that, for any exploration algorithm using \(k=n\) agents, there exist trees of arbitrarily large height D that require \(\varOmega (D^2)\) rounds, and we provide a simple algorithm that matches this bound for all trees.

We study the online problem of evacuating k robots on m concurrent rays to a single unknown exit. All k robots start on the same point \(s\), not necessarily on the junction \(j\) of the m rays, move at unit speed, and can communicate wirelessly. The goal is to minimize the competitive ratio, i.e., the ratio between the time it takes to evacuate all robots to the exit and the time it would take if the location of the exit was known in advance, on a worst-case instance.

When \(k=m\), we show that a simple waiting strategy yields a competitive ratio of 4 and present a lower bound of \(2+\sqrt{7/3} \approx 3.52753\) for all \(k=m\ge 3\). For \(k=3\) robots on \(m=3\) rays, we give a class of parametrized algorithms with a nearly matching competitive ratio of \(2+\sqrt{3} \approx 3.73205\). We also present an algorithm for \(1<k<m\), achieving a competitive ratio of \(1 + 2 \cdot \frac{m - 1}{k} \cdot \left( 1 + \frac{k}{m - 1} \right) ^{1 + \frac{m-1}{k}}\), obtained by parameter optimization on a geometric search strategy. Interestingly, the robots can be initially oblivious to the value of \(m > 2\).

Lastly, by using a simple but fundamental argument, we show that for \(k<m\) robots, no algorithm can reach a competitive ratio better than \(3+2\left\lfloor (m-1)/k \right\rfloor \), for every k, m with \(k<m\).

We consider the evacuation problem on a circle for three robots, at most one of which is faulty. The three robots starting from the center of a unit circle search for an exit placed at an unknown location on the perimeter (of the circle). During the search, robots can communicate wirelessly at any distance. The goal is to minimize the time that the latest non-faulty robot reaches the exit.

Our main contributions are two intuitive evacuation protocols for the non-faulty robots to reach the exit in two well-studied fault-models, Crash and Byzantine. Moreover, we complement our positive results by lower bounds in both models. A summary of our results reads as follows:

For comparison, it is known (see [11]) that in the case of three non-faulty robots with wireless communication we have a lower bound of 4.159, and an upper bound of 4.219 for evacuation, while for two non-faulty robots \(1 + 2\pi /3 + \sqrt{3} \approx 4.779\) is a tight upper and lower bound for evacuation.

We consider a parallel version of a classical Bayesian search problem. k agents are looking for a treasure that is placed in one of the boxes indexed by \(\mathbb {N}^+\) according to a known distribution p. The aim is to minimize the expected time until the first agent finds it. Searchers run in parallel where at each time step each searcher can “peek” into a box. A basic family of algorithms which are inherently robust is non-coordinating algorithms. Such algorithms act independently at each searcher, differing only by their probabilistic choices. We are interested in the price incurred by employing such algorithms when compared with the case of full coordination.

We first show that there exists a non-coordination algorithm, that knowing only the relative likelihood of boxes according to p, has expected running time of at most \(10+4(1+\frac{1}{k})^2 T\), where T is the expected running time of the best fully coordinated algorithm. This result is obtained by applying a refined version of the main algorithm suggested by Fraigniaud, Korman and Rodeh in STOC’16, which was designed for the context of linear parallel search.

We then describe an optimal non-coordinating algorithm for the case where the distribution p is known. The running time of this algorithm is difficult to analyse in general, but we calculate it for several examples. In the case where p is uniform over a finite set of boxes, then the algorithm just checks boxes uniformly at random among all non-checked boxes and is essentially 2 times worse than the coordinating algorithm. We also show simple algorithms for Pareto distributions over M boxes. That is, in the case where \(p(x) \sim 1/x^b\) for \(0< b < 1\), we suggest the following algorithm: at step t choose uniformly from the boxes unchecked in \(\left\{ 1, \ldots , \min (M, {\left\lfloor {t/\sigma } \right\rfloor }) \right\} \), where \(\sigma = b/(b + k - 1)\). It turns out this algorithm is asymptotically optimal, and runs about \(2+b\) times worse than the case of full coordination.

Consider a network in which n distributed nodes are connected to a single server. Each node continuously observes a data stream consisting of one value per discrete time step. The server has to continuously monitor a given parameter defined over all information available at the distributed nodes. That is, in any time step t, it has to compute an output based on all values currently observed across all streams. To do so, nodes can send messages to the server and the server can broadcast messages to the nodes. The objective is the minimisation of communication while allowing the server to compute the desired output.

We consider monitoring problems related to the domain \(D_t\) defined to be the set of values observed by at least one node at time t. We provide randomised algorithms for monitoring \(D_t\), (approximations of) the size \(|D_t|\) and the frequencies of all members of \(D_t\). Besides worst-case bounds, we also obtain improved results when inputs are parameterised according to the similarity of observations between consecutive time steps. This parameterisation allows to exclude inputs with rapid and heavy changes, which usually lead to the worst-case bounds but might be rather artificial in certain scenarios.

The spread of a virus and the containment of such spread have been widely studied in the literature. These two problems can be abstracted as a two-players stochastic game in which one side tries to spread the infection to the entire system, while the other side aims to contain the infection to a finite area. Three parameters play a particularly important role: (1) the probability p of successful infection, (2) the topology of the network, and (3) the probability \(\alpha \) that a strategy message has priority over the infection.

This paper studies the effect of killing strategies, where a node sacrifices itself and possibly some of its neighbors, to contain the spread of a virus in an infinite grid. Our contribution is threefold: (1) We prove that the simplest killing strategy is equivalent to the problem of site percolation; (2) when killing messages have priority, we prove that there always exists a killing strategy that contains a virus, for any probability \(0\le p<1\); in contrast, (3) when killing message do not have priority, there is not always a successful killing strategy, and we study the virus propagation for various \({0\le \alpha <1}\).

We give a distributed \((1+\epsilon )\)-approximation algorithm for the minimum vertex coloring problem on interval graphs, which runs in the \(\mathcal {LOCAL}\) model and operates in \(\mathrm {O}(\frac{1}{\epsilon } \log ^* n)\) rounds. If nodes are aware of their interval representations, then the algorithm can be adapted to the \(\mathcal {CONGEST}\) model using the same number of rounds. Prior to this work, only constant factor approximations using \(\mathrm {O}(\log ^* n)\) rounds were known [12]. Linial’s ring coloring lower bound implies that the dependency on \(\log ^* n\) cannot be improved. We further prove that the dependency on \(\frac{1}{\epsilon }\) is also optimal.

To obtain our \(\mathcal {CONGEST}\) model algorithm, we develop a color rotation technique that may be of independent interest. We demonstrate that color rotations can also be applied to obtain a \((1+\epsilon )\)-approximate multicoloring of directed trees in \(\mathrm {O}( \frac{1}{\epsilon } \log ^* n)\) rounds.

In the context of distributed synchronous computing, processors perform in rounds, and the time complexity of a distributed algorithm is classically defined as the number of rounds before all computing nodes have output. Hence, this complexity measure captures the running time of the slowest node(s). In this paper, we are interested in the running time of the ordinary nodes, to be compared with the running time of the slowest nodes. The node-averaged time-complexity of a distributed algorithm on a given instance is defined as the average, taken over every node of the instance, of the number of rounds before that node output. We compare the node-averaged time-complexity with the classical one in the standard \(\mathsf {LOCAL}\) model for distributed network computing. We show that there can be an exponential gap between the node-averaged time-complexity and the classical time-complexity, as witnessed by, e.g., leader election. Our first main result is a positive one, stating that, in fact, the two time-complexities behave the same for a large class of problems on very sparse graphs. In particular, we show that, for \(\mathsf {LCL}\) problems on cycles, the node-averaged time complexity is of the same order of magnitude as the “slowest node” time-complexity. In addition, in the \(\mathsf {LOCAL}\) model, the time-complexity is computed as a worst case over all possible identity assignments to the nodes of the network. In this paper, we also investigate the ID-averaged time-complexity, when the number of rounds is averaged over all possible identity assignments of size \(O(\log n)\). Our second main result is that the ID-averaged time-complexity is essentially the same as the expected time-complexity of randomized algorithms (where the expectation is taken over all possible random bits used by the nodes, and the number of rounds is measured for the worst-case identity assignment). Finally, we study the node-averaged ID-averaged time-complexity. We show that 3-colouring the n-node ring requires \(\varTheta (\log ^*n)\) rounds if the number of rounds is averaged over the nodes, or if the number of rounds is averaged over the identity assignments. In contrast, we show that 3-colouring the ring requires only O(1) rounds if the number of rounds is averaged over the nodes, and over the identity assignments.

Alice wants to join a new social network, and influence its members to adopt a new product or idea. Each person v in the network has a certain threshold t(v) for activation, i.e. adoption of the product or idea. If v has at least t(v) activated neighbors, then v will also become activated. If Alice wants to make k new friends in the network, and thereby activate the most number of people, how should she choose these friends? We study the problem of choosing the k people in the network to befriend, who will in turn activate the maximum number of people. This Maximum Influence with Links Problem has applications in viral marketing and the study of epidemics. We show that the solution can be quite different from the related and widely studied influence maximization problem where the objective is to choose a seed or target set with maximum influence. We prove that the Maximum Influence with Links problem is NP-complete even for bipartite graphs in which all nodes have threshold 1 or 2. In contrast, we give polynomial time algorithms that find optimal solutions for the problem for trees, paths, cycles, and cliques.

Computing all best swap edges (ABSE) of a spanning tree T of a given n-vertex and m-edge undirected and weighted graph G means to select, for each edge e of T, a corresponding non-tree edge f, in such a way that the tree obtained by replacing e with f enjoys some optimality criterion (which is naturally defined according to some objective function originally addressed by T). Solving efficiently an ABSE problem is by now a classic algorithmic issue, since it conveys a very successful way of coping with a (transient) edge failure in tree-based communication networks: just replace the failing edge with its respective swap edge, so as that the connectivity is promptly reestablished by minimizing the rerouting and set-up costs. In this paper, we solve the ABSE problem for the case in which T is a single-source shortest-path tree of G, and our two selected swap criteria aim to minimize either the maximum or the average stretch in the swap tree of all the paths emanating from the source. Having these criteria in mind, the obtained structures can then be reviewed as edge-fault-tolerant single-source spanners. For them, we propose two efficient algorithms running in \(O(m n +n^2 \log n)\) and \(O(m n \log \alpha (m,n))\) time, respectively, and we show that the guaranteed (either maximum or average, respectively) stretch factor is equal to 3, and this is tight. Moreover, for the maximum stretch, we also propose an almost linear \(O(m \log \alpha (m,n))\) time algorithm computing a set of good swap edges, each of which will guarantee a relative approximation factor on the maximum stretch of 3 / 2 (tight) as opposed to that provided by the corresponding BSE. Surprisingly, no previous results were known for these two very natural swap problems.

We presented in [12] an algorithm for computing a parameter called T -interval connectivity of dynamic graphs which are given as a sequence of static graphs. This algorithm operates at a high level, manipulating the graphs in the sequence as atomic elements with two types of operations: a composition operation and a test operation. The algorithm is optimal in the sense that it uses only \(O(\delta )\) composition and test operations, where \(\delta \) is the length of the sequence. In this paper, we generalize this framework to use various composition and test operations, which allows us to compute other parameters using the same high-level strategy that we used for T-interval connectivity. We illustrate the framework through the study of three minimization problems which refer to various properties of dynamic graphs, namely Bounded-Realization-of-the-Footprint, Temporal-Connectivity, and Round-Trip-Temporal-Diameter.

The gathering (or multi-agent rendezvous) problem requires a set of mobile agents, arbitrarily positioned at different nodes of a network to group within finite time at the same location, not fixed in advanced.

We study the feasibility of gathering mobile agents, identical and without explicit communication capabilities, in a dynamic ring of anonymous nodes; the class of dynamics we consider is the classic 1-interval-connectivity. We focus on the impact that factors such as chirality (i.e., a common sense of orientation) and cross detection (i.e., the ability to detect, when traversing an edge, whether some agent is traversing it in the other direction), have on the solvability of the problem; and we establish several results.

We provide a complete characterization of the classes of initial configurations from which the gathering problem is solvable in presence and in absence of cross detection and of chirality. The feasibility results of the characterization are all constructive: we provide distributed algorithms that allow the agents to gather within low polynomial time. In particular, the protocols for gathering with cross detection are time optimal.

We also show that cross detection is a powerful computational element. We prove that, without chirality, knowledge of the ring size is strictly more powerful than knowledge of the number of agents; on the other hand, with chirality, knowledge of n can be substituted by knowledge of k, yielding the same classes of feasible initial configurations.

From our investigation it follows that, for the gathering problem, the computational obstacles created by the dynamic nature of the ring can be overcome by the presence of chirality or of cross-detection.

Dynamic distributed storage algorithms such as DynaStore, Reconfigurable Paxos, RAMBO, and RDS, do not ensure liveness (wait-freedom) in asynchronous runs with infinitely many reconfigurations. We prove that this is inherent for asynchronous dynamic storage algorithms. Our result holds even if only one process may fail, provided that machines that were successfully removed from the system’s configuration can be switched off by a system administrator. To circumvent this result, we define a dynamic eventually perfect failure detector, and present an algorithm that uses it to emulate wait-free dynamic atomic storage. Though some of the previous algorithms have been designed for eventually synchronous models, to the best of our knowledge, our algorithm is the first to ensure liveness for all operations without restricting the reconfiguration rate.