Structural Information and Communication Complexity

We consider the multiparty communication complexity model, where k players holding inputs x ₁,...,x _k communicate to compute the value f(x ₁,...,x _k ) of a function f known to all of them.

In the second part of the talk, we consider the case where there are at least three parties (k ≥ 3). The main lower bound technique for the communication complexity of such multiparty problems is that of partition arguments: partition the k players into two disjoint sets of players and find a lower bound for the induced two-party communication complexity problem. We discuss the power of partition arguments for both deterministic and randomized protocols. (This part is based on a joint work with Jan Draisma and Enav Weinreb [1].)

Given a collection \(\mathcal{C}\) of weighted subsets of a ground set \(\mathcal{E}\), the set cover problem is to find a minimum weight subset of \(\mathcal{C}\) which covers all elements of \(\mathcal{E}\). We study a strategic game defined upon this classical optimization problem. Every element of \(\mathcal{E}\) is a player which chooses one set of \(\mathcal{C}\) where it appears. Following a public tax function, every player is charged a fraction of the weight of the set that it has selected. Our motivation is to design a tax function having the following features: it can be implemented in a distributed manner, existence of an equilibrium is guaranteed and the social cost for these equilibria is minimized.

Many distributed systems can be modeled as network games: a collection of selfish players that communicate in order to maximize their individual utilities. The performance of such games can be evaluated through the costs of the system equilibria: the system states in which no player can increase her utility by unilaterally changing her behavior. However, assuming that all players are selfish and in particular that all players have the same utility function may not always be appropriate. Hence, several extensions to incorporate also altruistic and malicious behavior in addition to selfishness have been proposed over the last years. In this paper, we seek to go one step further and study arbitrary relationships between participants. In particular, we introduce the notion of the social range matrix and explore the effects of the social range matrix on the equilibria in a network game. In order to derive concrete results, we propose a simplistic network creation game that captures the effect of social relationships among players.

The Stable Matching problem was introduced by Gale and Shapley in 1962. The input for the stable matching problem is a complete bipartite K _n,n graph together with a ranking for each node. Its output is a matching that does not contain a blocking pair, where a blocking pair is a pair of elements that are not matched together but rank each other higher than they rank their current mates. In this work we study the Distributed Weighted Stable Matching problem. The input to the Weighted Stable Matching problem is a complete bipartite K _n,n graph and a weight function W. The ranking of each node is determined by W, i.e. node v prefers node u ₁ over node u ₂ if W((v,u ₁)) > W((v, u ₂)). Using this ranking we can solve the original Stable Matching problem. We consider two different communication models: the billboard model and the full distributed model. In the billboard model, we assume that there is a public billboard and each participant can write one message on it in each time step. In the distributed model, we assume that each node can send O(logn) bits on each edge of the K _n,n . In the billboard model we prove a somewhat surprising tight bound: any algorithm that solves the Stable Matching problem requires at least n − 1 rounds. We provide an algorithm that meets this bound. In the distributed communication model we provide an algorithm named intermediation agencies algorithm, in short (IAA), that solves the Distributed Weighted Stable Marriage problem in \(O(\sqrt{n})\) rounds. This is the first sub-linear distributed algorithm that solves some subcase of the general Stable Marriage problem.

The problem of grooming is central in studies of optical networks. In graph-theoretic terms, it can be viewed as assigning colors to given paths in a graph, so that at most g (the grooming factor) paths of the same color can share an edge. Each path uses an ADM at each of its endpoints, and paths of the same color can share an ADM in a common endpoint. There are two sub-models, depending on whether or not paths that have the same color can use more than two edges incident with the same node (bifurcation allowed and bifurcation not allowed, resp.). The goal is to find a coloring that minimizes the total number of ADMs. In a previous work it was shown that the problem is NP-complete when bifurcation is allowed, even for a star network. In this paper we study the problem for a star network when bifurcation is not allowed. For the case of simple requests - in which only the case of g = 2 is of interest - we present a polynomial-time algorithm, and we study the structure of optimal solutions. We also present results for the case of multiple requests and g = 2, though the exact complexity of this case remains open. We provide two techniques, which lead to \(\frac{4}{3}\)-approximation algorithms. Our algorithms reduce the problem of traffic grooming in star networks to several variants of maximum matching problems.

This paper studies local-control strategies to estimate the size of a certain event affecting an arbitrary connected subset of nodes in a network. For example, our algorithms allow nodes in a peer-to-peer system to explore the remaining connected components after a Denial-of-Service attack, or nodes in a sensor network to assess the magnitude of a certain environmental event. In our model, each node can keep some extra information about its neighborhood computed during the deployment phase of the network. On the arrival of the event, the goal of the active nodes is to learn the network topology induced by the event, without the help of the remaining nodes. This paper studies the tradeoffs between message and time complexity of possible distributed solutions.

Two mobile agents (robots) have to meet in an a priori unknown bounded terrain modeled as a polygon, possibly with polygonal obstacles. Robots are modeled as points, and each of them is equipped with a compass. Compasses of robots may be incoherent. Robots construct their routes, but the actual walk of each robot is decided by the adversary that may, e.g., speed up or slow down the robot. We consider several scenarios, depending on three factors: (1) obstacles in the terrain are present, or not, (2) compasses of both robots agree, or not, (3) robots have or do not have a map of the terrain with their positions marked. The cost of a rendezvous algorithm is the worst-case sum of lengths of the robots’ trajectories until their meeting. For each scenario we design a deterministic rendezvous algorithm and analyze its cost. We also prove lower bounds on the cost of any deterministic rendezvous algorithm in each case. For all scenarios these bounds are tight.

We investigate the relation between the time complexity and the space complexity for the rendezvous problem with k agents in asynchronous tree networks. The rendezvous problem requires that all the agents in the system have to meet at a single node within finite time. First, we consider asymptotically time-optimal algorithms and investigate the minimum memory requirement per agent for asymptotically time-optimal algorithms. We show that there exists a tree with n nodes in which Ω(n) bits of memory per agent is required to solve the rendezvous problem in O(n) time (asymptotically time-optimal). Then, we present an asymptotically time-optimal rendezvous algorithm. This algorithm can be executed if each agent has O(n) bits of memory. From this lower/upper bound, this algorithm is asymptotically space-optimal on the condition that the time complexity is asymptotically optimal. Finally, we consider asymptotically space-optimal algorithms while allowing slowdown in time required to achieve rendezvous. We present an asymptotically space-optimal algorithm that each agent uses only O(logn) bits of memory. This algorithm terminates in O(Δn ⁸) time where Δ is the maximum degree of the tree.

The gathering problem of anonymous and oblivious mobile robots is one of fundamental problems in the theoretical mobile robotics. We consider the gathering problem in unoriented and anonymous rings, which requires that all robots gather at a non-predefined node. Since the gathering problem cannot be solved without any additional capability to robots, all the previous works assume some capability of robots, such as accessing the memory on node. In this paper, we focus on the multiplicity capability. This paper presents a deterministic gathering algorithm with local-weak multiplicity, which provides the robot with the information about whether its current node has more than one robot or not. This assumption is strictly weaker than that by previous works. Moreover, we show that our algorithm is asymptotically time-optimal one, that is, the time complexity of our algorithm is O(n), where n is the number of nodes. Interestingly, in spite of assuming the weaker assumption, it achieves significant improvement compared to the previous algorithm, which takes O(kn) time for k robots.

We consider asynchronous message-passing systems in which some links are timely and processes may crash. Each run defines a timeliness graph among correct processes: (p,q) is an edge of the timeliness graph if the link from p to q is timely (that is, there is a bound on communication delays from p to q). The main goal of this paper is to approximate this timeliness graph by graphs having some properties (such as being trees, rings, ...). Given a family S of graphs, for runs such that the timeliness graph contains at least one graph in S then using an extraction algorithm, each correct process has to converge to the same graph in S that is, in a precise sense, an approximation of the timeliness graph of the run. For example, if the timeliness graph contains a ring, then using an extraction algorithm, all correct processes eventually converge to the same ring and in this ring all nodes will be correct processes and all links will be timely.

We consider the task of comparing two rooted trees with port labelings. Roots of the trees are joined by an edge and the comparison has to be carried out distributedly, by exchanging messages among nodes. If the two trees are isomorphic, all nodes must finish in a state YES, otherwise they have to finish in a state NO and break symmetry, nodes of one tree getting label 0 and of the other – label 1. Nodes are modeled as identical automata, and our goal is to establish trade-offs between the memory size of such an automaton and the efficiency of distributed tree comparison, measured either by the time or by the number of messages used for communication between nodes. We consider both the synchronous and the asynchronous communication and establish exact trade-offs in both scenarios. For the synchronous scenario we are concerned with memory vs. time trade-offs. We show that if the automaton has x bits of memory, where x ≥ clogn, for a small constant c, then the optimal time to accomplish the comparison task in the class of trees of size at most n and of height at most h > 1 is Θ( max (h,n/x)). For the asynchronous scenario we study memory vs. number of messages trade-offs. We show that if the automaton has x bits of memory, where n ≥ x ≥ clogΔ, then the optimal number of messages to accomplish the comparison task in the class of trees of size at most n and of maximum degree at most Δ is Θ(n ²/x).

In the problems of exploration of faulty graphs, a team of cooperating agents is considered moving in a network containing one or more nodes that can harm the agents. A most notable among these problems is the problem of black hole location, where the network contains one node that destroys any incoming agent, and the task of the agents is to determine the location of this node. The main complexity measure is the number of agents needed to solve the problem. In this paper we begin with a study of malicious hosts with more varied behavior. We study the problem of periodic data retrieval which is equivalent to periodic exploration in fault-free networks, and to black hole location in networks with one black hole. The main result of the paper states that, in case of rings, it is sufficient to protect the internal state of the agent (i.e. the malicious host cannot change or create the content of agent’s memory), and the periodic data retrieval problem is solvable by a constant number of agents.

We are given an arbitrarily shaped chain of n robots with fixed end points in the plane. We assume that each robot can only see its two neighbors in the chain, which have to be within its viewing range. The goal is to move the robots to the straight line between the end points. Each robot has to base the decision where to move on the relative positions of its neighbors only. Such local strategies considered until now are based on discrete rounds, where a round consists of a movement of each robot. In this paper, we initiate the study of continuous local strategies: The robots may perpetually observe the relative positions of their neighbors, and may perpetually adjust their speed and direction in response to these observations. We assume a speed limit for the robots, that we normalize to one, which corresponds to the viewing range. Our contribution is a continuous, local strategy that needs time \({\mathcal O}(min\{n, (OPT+d) \log(n)\})\). Here d is the distance between the two stationary end points, and OPT is the time needed by an optimal global strategy. Our strategy has the property that the robot which reaches its destination last always moves with maximum speed. Thus, the same bound as above also holds for the distance travelled.

We consider the problem of exploring an anonymous unoriented ring of size n by k identical, oblivious, asynchronous mobile robots, that are unable to communicate, yet have the ability to sense their environment and take decisions based on their local view. Previous works in this weak scenario prove that k must not divide n for a deterministic solution to exist. Also, it is known that the minimum number of robots (either deterministic or probabilistic) to explore a ring of size n is 4. An upper bound of 17 robots holds in the deterministic case while 4 probabilistic robots are sufficient. In this paper, we close the complexity gap in the deterministic setting, by proving that no deterministic exploration is feasible with less than five robots, and that five robots are sufficient for any n that is coprime with five. Our protocol completes exploration in O(n) robot moves, which is also optimal.

Consider n sensors whose positions are represented by n uniform, independent and identically distributed random variables assuming values in the open unit interval (0,1). A natural way to guarantee connectivity in the resulting sensor network is to assign to each sensor as range the maximum of the two possible distances to its two neighbors. The interference at a given sensor is defined as the number of sensors that have this sensor within their range. In this paper we prove that the expected maximum interference is Ω(ln ln n), and that for any ε> 0, it is O((ln n)^1/2 + ε ).

This paper concerns graph spanners that approximate multipaths between pair of vertices of an undirected graphs with n vertices. Classically, a spanner H of stretch s for a graph G is a spanning subgraph such that the distance in H between any two vertices is at most s times the distance in G. We study in this paper spanners that approximate short cycles, and more generally p edge-disjoint paths with p > 1, between any pair of vertices.

For every unweighted graph G, we construct a 2-multipath 3-spanner of O(n ^3/2) edges. In other words, for any two vertices u,v of G, the length of the shortest cycle (with no edge replication) traversing u,v in the spanner is at most thrice the length of the shortest one in G. This construction is shown to be optimal in term of stretch and of size. In a second construction, we produce a 2-multipath (2,8)-spanner of O(n ^3/2) edges, i.e., the length of the shortest cycle traversing any two vertices have length at most twice the shortest length in G plus eight. For arbitrary p, we observe that, for each integer k ≥ 1, every weighted graph has a p-multipath p(2k − 1)-spanner with O(p n ^1 + 1/k ) edges, leaving open the question whether, with similar size, the stretch of the spanner can be reduced to 2k − 1 for all p > 1.

We study the problem of orienting some edges of given planar graph such that the resulting subdigraph is strongly connected and spans all vertices of the graph. We are interested in orientations with minimum number of arcs and such that they produce a digraph with bounded stretch factor. Such orientations have applications into the problem of establishing strongly connected sensor network when sensors are equipped with directional antennae.

We present three constructions for such orientations. Let G = (V, E) be a connected planar graph without cut edges and let Φ(G) be the degree of largest face in G. Our constructions are based on a face coloring, say with λ colors. First construction gives a strong orientation with at most \(\left( 2 - \frac{4 \lambda - 6}{\lambda (\lambda - 1)} \right) |E|\) arcs and stretch factor at most Φ(G) − 1. The second construction gives a strong orientation with at most |E| arcs and stretch factor at most \((\Phi (G) - 1)^{\lceil \frac{\lambda + 1}{2} \rceil}\). The third construction can be applied to planar graphs which are 3-edge connected. It uses a particular 6-face coloring and for any integer k ≥ 1 produces a strong orientation with at most \(\left(1 - \frac{k}{10 (k + 1)}\right) |E|\) arcs and stretch factor at most Φ² (G) (Φ(G) − 1)^{2 k + 4}. These are worst-case upper bounds. In fact the stretch factors depend on the faces being traversed by a path.

We consider the Minimum Spanning Caterpillar Problem (MSCP) in a graph where each edge has two costs, spine (path) cost and leaf cost, depending on whether it is used as a spine or a leaf edge. The goal is to find a spanning caterpillar in which the sum of its edge costs is the minimum. We show that the problem has a linear time algorithm when a tree decomposition of the graph is given as part of the input. Despite the fast growing constant factor of the time complexity of our algorithm, it is still practical and efficient for some classes of graphs, such as outerplanar, series-parallel (K ₄ minor-free), and Halin graphs. We also briefly explain how one can modify our algorithm to solve the Minimum Spanning Ring Star and the Dual Cost Minimum Spanning Tree Problems.

We first devise a branching algorithm that computes a minimum independent dominating set with running time O ^*(2^0.424n ) and polynomial space. This improves the O ^*(2^0.441n ) result by (S. Gaspers and M. Liedloff, A branch-and-reduce algorithm for finding a minimum independent dominating set in graphs, Proc. WG’06). We then study approximation of the problem by moderately exponential algorithms and show that it can be approximated within ratio 1 + ε, for any ε> 0, in a time smaller than the one of exact computation and exponentially decreasing with ε. We also propose approximation algorithms with better running times for ratios greater than 3.