Structural Information and Communication Complexity

Inspired by the increasing interest in self-organizing social opportunistic networks, we investigate the problem of distributed detection of unknown communities in dynamic random graphs. As a formal framework, we consider the dynamic version of the well-studied Planted Bisection Model \(\mbox{dyn-}\mathcal{G}(n,p,q)\) where the node set [n] of the network is partitioned into two unknown communities and, at every time step, each possible edge (u,v) is active with probability p if both nodes belong to the same community, while it is active with probability q (with q < < p) otherwise. We also consider a time-Markovian generalization of this model.

We propose a distributed protocol based on the popular Label Propagation Algorithm and prove that, when the ratio p/q is larger than n ^b (for an arbitrarily small constant b > 0), the protocol finds the right “planted” partition in O(logn) time even when the snapshots of the dynamic graph are sparse and disconnected (i.e. in the case p = Θ(1/n)).

In this paper, we study the T-interval-connected dynamic graphs from the point of view of the time necessary and sufficient for their exploration by a mobile entity (agent). A dynamic graph (more precisely, an evolving graph) is T-interval-connected (T ≥ 1) if, for every window of T consecutive time steps, there exists a connected spanning subgraph that is stable (always present) during this period. This property of connection stability over time was introduced by Kuhn, Lynch and Oshman [6] (STOC 2010). We focus on the case when the underlying graph is a ring of size n, and we show that the worst-case time complexity for the exploration problem is 2n − T − Θ(1) time units if the agent knows the dynamics of the graph, and \(n+ \frac{n}{\max\{1, T-1\} } (\delta-1) \pm \Theta(\delta)\) time units otherwise, where δ is the maximum time between two successive appearances of an edge.

We consider the Consensus problem in arbitrary dynamic networks. A dynamic network is a communication network whose topology evolves from round to round. We make no assumptions on the possible topologies. We give the first complete necessary and sufficient condition for dynamic networks where it is possible to solve Consensus.

We show that we can complement the necessary condition for solvability of Consensus given, in the context of omission faults, in [GP11] in the context of dynamic networks. We prove that this condition is actually sufficient by presenting a new Consensus algorithm. This algorithm is based upon reconstructing a partial, but significant, view of the actual communications that occurred during the execution.

We consider the k-Server problem under the advice model of computation when the underlying metric space is sparse. On one side, we introduce Θ(1)-competitive algorithms for a wide range of sparse graphs, which require advice of (almost) linear size. Namely, we show that for graphs of size N and treewidth α, there is an online algorithm which receives O(n(log α + log log N)) bits of advice and optimally serves a sequence of length n. With a different argument, we show that if a graph admits a system of μ collective tree (q,r)- spanners, then there is a (q + r)-competitive algorithm which receives O(n(log μ + log log N)) bits of advice. Among other results, this gives a 3-competitive algorithm for planar graphs, provided with O(n log log N) bits of advice. On the other side, we show that an advice of size Ω(n) is required to obtain a 1-competitive algorithm for sequences of size n even for the 2-server problem on a path metric of size N ≥ 5. Through another lower bound argument, we show that at least \(\frac{n}{2}({\rm log} \alpha- 1.22)\) bits of advice is required to obtain an optimal solution for metric spaces of treewidth α, where 4 ≤ α < 2k.

The surveillance game [Fomin et al., 2012] models the problem of web-page prefetching as a pursuit evasion game played on a graph. This two-player game is played turn-by-turn. The first player, called the observer, can mark a fixed amount of vertices at each turn. The second one controls a surfer that stands at vertices of the graph and can slide along edges. The surfer starts at some initially marked vertex of the graph, her objective is to reach an unmarked node The surveillance number sn(G) of a graph G is the minimum amount of nodes that the observer has to mark at each turn ensuring it wins against any surfer in G. Fomin et al. also defined the connected surveillance game where the marked nodes must always induce a connected subgraph. They ask if there is a constant c > 0 such that \(\frac{{\rm csn}(G)}{{\rm sn}(G)} \leq c\) for any graph G. It has been shown that there are graphs G for which csn(G) = sn(G) + 1. In this paper, we investigate this question.

We present a family of graphs G such that csn(G) > sn(G) + 1. Moreover, we prove that \({\rm csn}(G) \leq{\rm sn}(G) \sqrt{n}\) for any n-node graph G. While the gap between these bounds remains huge, it seems difficult to reduce it. We then define the online surveillance game where the observer has no a priori knowledge of the graph topology and discovers it little-by-little. Unfortunately, we show that no algorithm for solving the online surveillance game has competitive ratio better than Ω(Δ).

We consider a generalization of the classical problem of ski rental. There is a game that ends at an unknown time, and the algorithm needs to decide how to pay for the time until the game ends. There are two “payment plans” or “options,” such that the cost of t time units under option i (for i = 1,2) is given by a _i t + b _i , where b _i is a one-time cost to start using option i, and a _i is the ongoing cost per time unit. We assume w.l.o.g. that a ₁ > a ₂ and b ₁ < b ₂. (The classical version is b ₁ = 0 and a ₂ = 0, so that option 1 is “pure rent” and option 2 is “pure buy.”) We give deterministic and randomized algorithms for the general setting and prove matching lower bounds on the competitive ratios for the problem. This is the first non-trivial result for the non-additive model of ski rental, which models non-refundable one-time costs.

We address the question of whether the primal-dual approach for the design and analysis of online algorithms can be applied to nonmonotone problems. We provide a positive answer by presenting a primal-dual analysis to the online algorithm of Awerbuch et al. [1] for routing virtual circuits with unknown durations.

Social networks offer users new means of accessing information, essentially relying on “social filtering”, i.e. propagation and filtering of information by social contacts. The sheer amount of data flowing in these networks, combined with the limited budget of attention of each user, makes it difficult to ensure that social filtering brings relevant content to interested users. Our motivation in this paper is to measure to what extent self-organization of a social network results in efficient social filtering.

Nevertheless the situation differs when user interests exhibit a particular structure, captured by a metric space with low doubling dimension. In that case, natural autonomous dynamics converge to a stable configuration. Moreover, users obtain all the information of interest to them in the corresponding dissemination, provided their budget of attention is logarithmic in the size of their interest set.

Content-based routing is widely used in large-scale distribu-ted systems as it provides a loosely-coupled yet expressive form of communication: consumers of information register their interests by the means of subscriptions, which are subsequently used to determine the set of recipients of every message published in the system. A major challenge of content-based routing is security. Although some techniques have been proposed to perform matching of encrypted subscriptions against encrypted messages, their computational cost is very high. To speed up that process, it was recently proposed to embed Bloom filters in both subscriptions and messages to reduce the space of subscriptions that need to be tested. In this article, we provide a comprehensive analysis of the information leaked by Bloom filters when implementing such a “prefiltering” strategy. The main result is that although there is a fundamental trade-off between prefiltering efficiency and information leakage, it is practically possible to obtain good prefiltering while securing the scheme against leakages with some simple randomization techniques.

We study a combinatorial model of the spread of influence in networks that generalizes existing schemata recently proposed in the literature. In our model agents change behaviors/opinions on the basis of information collected from their neighbors in a time interval of bounded size whereas agents are assumed to have unbounded memory in previously studied scenarios. In our mathematical framework, one is given a network G = (V,E), an integer value t(v) for each node v ∈ V, and a time window size λ. The goal is to determine a small set of nodes (target set) that influences the whole graph. The spread of influence proceeds in rounds as follows: initially all nodes in the target set are influenced; subsequently, in each round, any uninfluenced node v becomes influenced if the number of its neighbors that have been influenced in the previous λ rounds is greater than or equal to t(v). We prove that the problem of finding a minimum cardinality target set that influences the whole network G is hard to approximate within a polylogarithmic factor. On the positive side, we design exact polynomial time algorithms for paths, rings, trees, and complete graphs.

This paper proposes and analyses two fully distributed probabilistic splitting and naming procedures which assign a label to each vertex of a given anonymous graph G without any initial knowledge. We prove, in particular, that with probability 1 − o(n ^− 1) (resp. with probability 1 − o(n ^− c ) for any c ≥ 1) there is a unique vertex with the maximal label in the graph G having n vertices. In the first case, the size of labels is O(logn) with probability 1 − o(n ^− 1) and the expected value of the size of labels is also O(logn). In the second case, the size of labels is \(O\left((\log n)(\log^* n)^2 \right)\) with probability 1 − o(n ^− c ) for any c ≥ 1; their expected size is \(O\left((\log n)(\log^* n) \right)\).

We analyse a basic simple maximum broadcasting algorithm and prove that if vertices of a graph G use the same probabilistic distribution to choose a label then, for broadcasting the maximal label over the labelled graph, each vertex sends O(logn) messages with probability 1 − o(n ^− 1).

From these probabilistic procedures we deduce Monte Carlo algorithms for electing or computing a spanning tree in anonymous graphs without any initial knowledge and for counting vertices of an anonymous ring; these algorithms are correct with probability 1 − o(n ^− 1) or with probability 1 − o(n ^− c ) for any c ≥ 1. The size of messages has the same value as the size of labels. The number of messages is O(mlogn) for electing and computing a spanning tree; it is O(nlogn) for counting the vertices of a ring.

We illustrate the power of the splitting procedure by giving a probabilistic election algorithm for rings having n vertices with identities which is correct and always terminates; its message complexity is equal to O(nlogn) with probability 1 − o(n ^− 1). (Proofs are omitted for lack of space).

We consider the problem of resource discovery in distributed systems. In particular we give an algorithm, such that each node in a network discovers the address of any other node in the network. We model the knowledge of the nodes as a virtual overlay network given by a directed graph such that complete knowledge of all nodes corresponds to a complete graph in the overlay network. Although there are several solutions for resource discovery, our solution is the first that achieves worst-case optimal work for each node, i.e. the number of addresses (\(\mathcal O(n)\)) or bits (\(\mathcal O(n\log n)\)) a node receives or sends coincides with the lower bound, while ensuring only a linear runtime (\(\mathcal O(n)\)) on the number of rounds.

In this paper, we propose and analyze a simple localized algorithm to balance a tree. The motivation comes from live distributed streaming systems in which a source diffuses a content to peers via a tree, a node forwarding the data to its children. Such systems are subject to a high churn, peers frequently joining and leaving the system. It is thus crucial to be able to repair the diffusion tree to allow an efficient data distribution. In particular, due to bandwidth limitations, an efficient diffusion tree must ensure that node degrees are bounded. Moreover, to minimize the delay of the streaming, the depth of the diffusion tree must also be controlled. We propose here a simple distributed repair algorithm in which each node carries out local operations based on its degree and on the subtree sizes of its children. In a synchronous setting, we first prove that starting from any n-node tree our process converges to a balanced tree in O(n ²) turns. We then describe a more restrictive model, adding a small extra information to each node, under which we adopt our algorithm to converge in \(\Theta(\emph{n}log\emph{n})\) turns. We then exhibit by simulation that the convergence is much faster (logarithmic number of turns in average) for a random tree.

We study the impact that persistent memory has on the classical rendezvous problem of two mobile computational entities, called robots, in the plane. It is well known that, without additional assumptions, rendezvous is impossible if the entities have no persistent memory, even if the system is semi-synchronous and movements are rigid. It has been recently shown that if each entity is endowed with O(1) bits of persistent visible memory (called lights), they can rendezvous even if the system is asynchronous.

In this paper we investigate the rendezvous problem in two weaker settings in systems of robots endowed with visible lights: in FState, a robot can only see its own light, while in FComm a robot can only see the other robot’s light. Among other things, we prove that, with rigid movements, finite-state robots can rendezvous in semi-synchronous settings, and finite-communication robots are able to rendezvous even in asynchronous ones. All proofs are constructive: in each setting, we present a protocol that allows the two robots to rendezvous in finite time.

We investigate the pattern formation problem by mobile robots with limited visibility that can observe the positions of robots within limited distance. For robots with unlimited visibility, Fujinaga et al. (DISC 2012) showed that asynchronous oblivious robots have the same formation power as fully-synchronous non-oblivious robots, that is, starting from any initial configuration I, target pattern F is formable if and only if ρ(I) divides ρ(F) where ρ(·) is the geometric symmetricity. We first show that fully-synchronous oblivious robots with limited visibility cannot form F even when ρ(I) divides ρ(F). Hence, limited visibility substantially weakens the formation power of oblivious robots. Secondly, we show that despite limited visibility, semi-synchronous robots with rigid moves, and fully-synchronous robots with non-rigid moves have the same formation power as robots with unlimited visibility. Consequently, local memory is necessary and sufficient for these robots.

The paper presents general results about the gathering problem on graphs. A team of robots placed at the vertices of a graph, have to meet at some vertex and remain there. Robots operate in Look-Compute-Move cycles; in one cycle, a robot perceives the current configuration in terms of robots disposal (Look), decides whether to move towards one of its neighbors (Compute), and in the positive case makes the computed move (Move). Cycles are performed asynchronously for each robot.

So far, the goal has been to provide feasible resolution algorithms with respect to different assumptions about the capabilities of the robots as well as the topology of the underlying graph. In this paper, we are interested in studying the quality of the resolution algorithms in terms of the minimum number of asynchronous moves performed by the robots.We provide results for general graphs that suggest resolution techniques and provide feasibility properties. Then, we apply the obtained theory on specific topologies like trees and rings. The resulting algorithms for trees and rings are then compared with the existing ones, hence showing how the old solutions can be far apart from the optimum.

We prove basic and fundamental results about this (reformulated) problem. We show that when the number of network nodes is big enough, the required \(\check{\alpha}\) approaches zero. Specifically, on the unit disk it holds with high probability that the threshold for connectivity is \(\check{\alpha}=\Theta(\sqrt[4]{\frac{\log n}{n}})\). This is shown by the use of Poisson approximation and geometrical considerations. Moreover, when the model is relaxed to allow orientation towards the center of the area, we demonstrate that \(\check{\alpha}=\Theta(\frac{\log n}{n})\) is a necessary and sufficient condition.

We study dynamic broadcasting in multiple access channels in adversarial settings. There is an unbounded supply of anonymous stations attached to the channel. There is an adversary who injects packets into stations to be broadcast on the channel. The adversary is restricted by the injection rate, burstiness, and by how many passive stations can be simultaneously activated by injecting packets into their empty queues. We consider deterministic distributed broadcast algorithms, which are further categorized by their properties. We investigate for which injection rates can algorithms attain bounded packet latency, when adversaries are restricted to be able to activate at most one station per round. The rates of algorithms we present make the increasing sequence \(\frac{1}{3}\), \(\frac{3}{8}\) and \(\frac{1}{2}\), reflecting the additional features of algorithms. We show that no injection rate greater than \(\frac{3}{4}\) can be handled with bounded packet latency.

Abstract. All-optical networks have been largely investigated due to their high data transmission rates. The key to the high speeds in alloptical networks is to maintain the signal in optical form, to avoid the overhead of conversion to and from electrical form at the intermediate nodes. In the traditional WDM technology the spectrum of light that can be transmitted through the optical fiber has been divided into frequency intervals of fixed width with a gap of unused frequencies between them. In this context the term wavelength refers to each of these predefined frequency intervals.

An alternative architecture emerging in very recent studies is to move towards a flexible model in which the usable frequency intervals are of variable width. Every lightpath is assigned a frequency interval which remains fixed through all the links it traverses. Two different lightpaths using the same link have to be assigned disjoint sub-spectra. This technology is termed flex-grid or flex-spectrum.

The introduction of this technology requires the generalization of many optimization problems that have been studied for the fixed-grid technology. Moreover it implies new problems that are irrelevant or trivial in the current technology. In this work we focus on bandwidth utilization in path toplogy and consider two wavelength assignment, or in graph theoretic terms coloring, problems where the goal is to maximize the total profit. We obtain bandwidth maximization as a special case.

In this paper we explore the problem of achieving efficient packet transmission over unreliable links with worst case occurrence of errors. In such a setup, even an omniscient offline scheduling strategy cannot achieve stability of the packet queue, nor is it able to use up all the available bandwidth. Hence, an important first step is to identify an appropriate metric for measuring the efficiency of scheduling strategies in such a setting. To this end, we propose a relative throughput metric which corresponds to the long term competitive ratio of the algorithm with respect to the optimal. We then explore the impact of the error detection mechanism and feedback delay on our measure. We compare instantaneous error feedback with deferred error feedback, that requires a faulty packet to be fully received in order to detect the error. We propose algorithms for worst-case adversarial and stochastic packet arrival models, and formally analyze their performance. The relative throughput achieved by these algorithms is shown to be close to optimal by deriving lower bounds on the relative throughput of the algorithms and almost matching upper bounds for any algorithm in the considered settings. Our collection of results demonstrate the potential of using instantaneous feedback to improve the performance of communication systems in adverse environments.

We consider a variant of the online buffer management problem in network switches, called the k-frame throughput maximization problem (k-FTM). Large data, called frames, carried on the Internet are split into small k packets by a sender, and the receiver can reconstruct each frame only if he/she accepts all the k constituent packets of the frame. Packets pass through network switches on the Internet, and each switch is equipped with a FIFO buffer to temporarily store arriving packets. Since the size of the buffer is bounded, some packets must be discarded if it is full. It is impossible to reconstruct frames including discarded packets any more. Our goal is to maximize the number of reconstructed frames. Kesselman et al. proposed this problem, and showed that any online algorithm has an unbounded competitive ratio even when k = 2. Hence, they considered the “order-respecting” variant of k-FTM. They showed that the competitive ratio of their algorithm is at most \((\frac{2kB}{\lfloor B/k \rfloor} + k)\) for any B ≥ k, where B is the size of the buffer. Also, they gave a lower bound of \(\frac{B}{\lfloor 2B/k \rfloor}\) on the competitive ratio when 2B ≥ k and k is a power of 2. Furthermore, they proved that the competitive ratio of a greedy algorithm is at most \((11+\frac{8}{B-1})\) for any B( ≥ 2) and k = 2.

We analyze a greedy algorithm for k = 2, and show that its competitive ratio is at most 3 for any B, improving the previous upper bound of \(\frac{4B}{ \lfloor B/2 \rfloor } + 2 (\geq 10)\). Moreover, we show that the competitive ratio of any deterministic algorithm is at least 3 for any B in k = 2, which matches our upper bound.

In this paper we focus on dynamic batch algorithms for single source shortest paths in graphs with positive real edge weights. A dynamic algorithm is called batch if it is able to handle graph changes that consist of multiple edge updates at a time, i.e. a batch. We propose a new algorithm to process a decremental batch (containing only delete and weight increase operations), a new algorithm to process an incremental batch (containing only insert and weight decrease operations), and a combination of these algorithms to process arbitrary sequences of incremental and decremental batches. These algorithms are update-sensitive, namely they are efficient w.r.t. to the number of nodes in the shortest paths tree that change the parent and/or the distance from the source as a consequence of the changes.

This paper investigates the relation linking the s-simultaneous consensus problem and the k-set agreement problem in wait-free message-passing systems. To this end, it first defines the (s,k)-SSA problem which captures jointly both problems: each process proposes a value, executes s simultaneous instances of a k-set agreement algorithm, and has to decide a value so that no more than sk different values are decided. The paper introduces then a new failure detector class denoted Z _s,k , which is made up of two components, one focused on the “shared memory object” that allows the processes to cooperate, and the other focused on the liveness of (s,k)-SSA algorithms. A novelty of this failure detector lies in the fact that the definition of its two components are intimately related. Then, the paper presents a Z _s,k -based algorithm that solves the (s,k)-SSA problem, and shows that the “shared memory”-oriented part of Z _s,k is necessary to solve the (s,k)-SSA problem (this generalizes and refines a previous result that showed that the generalized quorum failure detector Σ _k is necessary to solve k-set agreement). Finally, the paper investigates the structure of the family of (s,k)-SSA problems and introduces generalized (asymmetric) simultaneous set agreement problems in which the parameter k can differ in each underlying k-set agreement instance. Among other points, it shows that, for s,k > 1, (a) the (sk,1)-SSA problem is strictly stronger that the (s,k)-SSA problem which is itself strictly stronger than the (1,ks)-SSA problem, and (b) there are pairs (s ₁,k ₁) and (s ₂,k ₂) such that s ₁ k ₁ = s ₂ k ₂ and (s ₁,k ₁)-SSA and (s ₂,k ₂)-SSA are incomparable.

Given an undirected weighted graph G with n nodes, the k-Undirected Steiner Tree problem is to find a minimum cost tree spanning a specified set of k nodes. If this problem and its directed version have several applications in multicast routing in packet switching networks, the modeling is not adapted anymore in networks based upon the circuit switching principle in which not all nodes are able to duplicate packets. In such networks, the number of branching nodes (with outdegree > 1) in the multicast tree must be limited.

We introduce the (k,p) −Steiner Tree with Limited Number of Branching nodes problems where the goal is to find an optimal Steiner tree with at most p branching nodes. We study, when p is fixed, its complexity depending on two criteria: the graph topology and the parameter k. In particular, we propose a polynomial algorithm when the input graph is acyclic and an other algorithm when k is fixed in an input graph of bounded treewidth. Moreover, in directed graphs where p ≤ k − 2, or in planar graphs, we provide an n ^ε -inapproximability proof, for any ε < 1.

We present a maximum-separable-distance (MDS) code suitable for computing erasure resilient codes for large word lengths. Given n data blocks (words) of any even bit length w the Circulant Cauchy Codes compute m ≤ w + 1 code blocks of bit length w using XOR-operations, such that every combination of n data words and code words can reconstruct all data words. The number of XOR bit operations is at most 3nmw for encoding all check blocks. The main contribution is the small bit complexity for the reconstruction of u ≤ m missing data blocks with at most 9nuw XOR operations.

We show the correctness for word lengths of form w = p − 1 where p is a prime number for which two is a primitive root. We call such primes Artin numbers. We use efficiently invertible Cauchy matrices in a finite field GF[2 ^p ] for computing the code blocks To generalize these codes for all even word lengths w we use ℓ independent encodings by partitioning each block into sub-blocks of size p _i  − 1, i.e. \(w= \sum_{i=1}^{\ell} p_i -\ell\) for Artin numbers p _i . While it is not known whether infinitely many Artin numbers exist we enumerate all Circulant Cauchy Codes for w ≤ 10⁵ yielding MDS codes for all \(m+n \leq \frac{10}{62} w \).

Erratum to: T. Moscibroda and A.A. Rescigno (Eds.) Structural Information and Communication Complexity DOI: 10.​1007/​978-3-319-03578-9

The book was inadvertently published with an incorrect name of the copyright holder. The name of the copyright holder for this book is: © Springer-Verlag Berlin Heidelberg. The book has been updated with the changes.