We study Plurality Consensus in the Model over a network of n anonymous agents. Each agent supports an initial opinion or color. We assume that at the onset, the number of agents supporting the plurality color exceeds that of the agents supporting any other color by a sufficiently-large bias, though the initial plurality itself might be very far from absolute majority. The goal is to provide a protocol that, with high probability, brings the system into the configuration in which all agents support the (initial) plurality color. We consider the Undecided-State Dynamics, a well-known protocol which uses just one more state (the undecided one) than those necessary to store colors. We show that the speed of convergence of this protocol depends on the initial color configuration as a whole, not just on the gap between the plurality and the second largest color community. This dependence is best captured by a novel notion we introduce, namely, the monochromatic distance md which measures the distance of the initial color configuration from the closest monochromatic one. In the complete graph, we prove that, for a wide range of the input parameters, this dynamics converges within O(md log n) rounds. We prove that this upper bound is almost tight in the strong sense: Starting from any color configuration , the convergence time is Ω(md). Finally, we adapt the Undecided-State Dynamics to obtain a fast, random walk-based protocol for plurality consensus on regular expanders. This protocol converges in O(md polylog(n)) rounds using only polylog(n) local memory. A key-ingredient to achieve the above bounds is a new analysis of the maximum node congestion that results from performing n parallel random walks on regular expanders. All our bounds hold with high probability.

We study a Plurality Consensus process in which each of n anonymous agents of a communication network supports an initial opinion (a colorchosen from a finite set [k]) and, at every time step, he can revise his color according to a random sample of neighbors.

Performance bounds for opportunistic networks have been derived in a number of recent papers for several key quantities, such as the expected delivery time of a unicast message, or the flooding time (a measure of how fast information spreads). However, to the best of our knowledge, none of the existing results is derived under a mobility model which is able to reproduce the power law+exponential tail dichotomy of the pairwise node intercontact time distribution which has been observed in traces of several real opportunistic networks. The contributions of this paper are two-fold: first, we present a simple pairwise contact model—called the Home-MEG model—for opportunistic networks based on the observation made in previous work that pairs of nodes in the network tend to meet in very few, selected locations (home locations); this contact model is shown to be able to faithfully reproduce the power law+exponential tail dichotomy of intercontact time. Second, we use the Home-MEG model to analyze flooding time in opportunistic networks, presenting asymptotic bounds on flooding time that assume different initial conditions for the existence of opportunistic links. By comparing asymptotic bounds with the results of simulations performed using a realistic human mobility model, we demonstrate the capability of the proposed Home-MEG model to faithfully predict the speed of information spreading in large-scale opportunistic networks. Finally, our bounds provide some analytical evidences that the speed of information spreading in opportunistic networks can be much faster than that predicted by simple geometric mobility models.

Opportunistic mobile ad hoc networks (MANETs) are a special class of sparse and disconnected MANETs where data communication exploits sporadic contact opportunities among nodes. We consider opportunistic MANETs where nodes move independently at random over a square of the plane. Nodes exchange data if they are at a distance at mostrwithin each other, wherer> 0 is the node transmission radius. The flooding time is the number of time-steps required to broadcast a message from a source node to every node of the network. Flooding time is an important measure of how fast information can spread in dynamic networks. We derive the first upper bound on the flooding time, which is a decreasing function of the maximal speed of the nodes. The bound holds with high probability, and it is nearly tight. Our bound shows that, thanks to node mobility, even when the network is sparse and disconnected, information spreading can be fast.

We present a general approach to study the flooding time (a measure of how fast information spreads) in dynamic graphs (graphs whose topology changes with time according to a random process). We consider arbitrary ergodic Markovian dynamic graph process, that is, processes in which the topology of the graph at time t depends only on its topology at time t-1 and which have a unique stationary distribution. The most well studied models of dynamic graphs are all Markovian and ergodic.

Abstract We study deterministic fault‐tolerant gossiping protocols in geometric radio networks. Node and link faults may happen during every time‐slot of the protocol's execution. We first consider the model where every node can send at most one message per time‐slot. We provide a protocol that completes gossiping inO(nΔ) time (wherenis the number of nodes and Δ is the maximal in‐degree) and has message complexityO(n2). Both bounds are then shown to be optimal. Second, we consider the model where messages can be arbitrarily combined and sent in one time‐slot. We give a protocol working in optimal completion timeO(DΔ) (whereDis the maximal source eccentricity) and message complexityO(Dn). © 2012 Wiley Periodicals, Inc. NETWORKS, Vol. 2012

We consider static ad hoc wireless networks whose nodes, equipped with the same initial battery charge, may dynamically change their transmission range. When a node v transmits with range r(v), its battery charge is decreased by β r(v)2, where β > 0 is a fixed constant. The goal is to provide a range assignment schedule that maximizes the number of broadcast operations from a given source (this number is denoted by the length of the schedule). This maximization problem, denoted by Max LifeTime, is known to be NP-hard and the best algorithm yields worst-case approximation ratio Θ (log n), where n is the number of nodes of the network. We consider random geometric instances formed by selecting n points independently and uniformly at random from a square of side length √n in the euclidean plane. We present an efficient algorithm that constructs a range assignment schedule having length not smaller than 1/12 of the optimum with high probability. Then we design an efficient distributed version of the above algorithm, where nodes initially know n and their own position only. The resulting schedule guarantees the same approximation ratio achieved by the centralized version, thus, obtaining the first distributed algorithm having provably good performance for this problem.

Markovian evolving graphs are dynamic-graph models where the links among a fixed set of nodes change during time according to an arbitrary Markovian rule. They are extremely general and they can well describe important dynamic-network scenarios. We study the speed of information spreading in the stationary phase by analyzing the completion time of the flooding mechanism. We prove a general theorem that establishes an upper bound on flooding time in any stationary Markovian evolving graph in terms of its node-expansion properties. We apply our theorem in two natural and relevant cases of such dynamic graphs. Geometric Markovian evolving graphs where the Markovian behaviour is yielded by n mobile radio stations, with fixed transmission radius, that perform independent random walks over a square region of the plane. Edge-Markovian evolving graphs where the probability of existence of any edge at time t depends on the existence (or not) of the same edge at time t-1. In both cases, the obtained upper bounds hold with high probability and they are nearly tight. In fact, they turn out to be tight for a large range of the values of the input parameters. As for geometric Markovian evolving graphs, our result represents the first analytical upper bound for flooding time on a class of concrete mobile networks.

We consider a Mobile Ad-hoc NETwork (MANET) formed by n agents that move at speed V according to the Manhattan Random-Way Point model over a square region of side length L. The resulting stationary (agent) spatial probability distribution is far to be uniform: the average density over the "central zone" is asymptotically higher than that over the "suburb". Agents exchange data iff they are at distance at most R within each other.

=1We introduce stochastic time-dependency in evolving graphs: starting from an initial graph, at every time step, every edge changes its state (existing or not) according to a two-state Markovian process with probabilities p (edge birth-rate) and q (edge death-rate). If an edge exists at time t, then, at time $t+1$, it dies with probability q. If instead the edge does not exist at time t, then it will come into existence at time $t+1$ with probability p. Such an evolving graph model is a wide generalization of time-independent dynamic random graphs [A. E. F. Clementi, A. Monti, F. Pasquale, and R. Silvestri, J. Comput. System Sci., 75 (2009), pp. 213–220] and will be called edge-Markovian evolving graphs. We investigate the speed of information spreading in such evolving graphs. We provide nearly tight bounds (which in fact turn out to be tight for a wide range of probabilities p and q) on the completion time of the flooding mechanism aiming to broadcast a piece of information from a source node to all nodes. In particular, we provide i) a tight characterization of the class of edge-Markovian evolving graphs where flooding time is constant and, thus, it does not asymptotically depend on the initial graph; ii) a tight characterization of the class of edge-Markovian evolving graphs where flooding time does not asymptotically depend on the edge death-rate q. An interesting consequence of our results is that information spreading can be fast even if the graph, at every time step, is very sparse and disconnected. Furthermore, our bounds imply that the flooding time can be exponentially shorter than the mixing time of the edge-Markovian graph.

Markovian evolving graphs are dynamic-graph models where the links among a fixed set of nodes change during time according to an arbitrary Markovian rule. They are extremely general and they can well describe important dynamic-network scenarios. We study the speed of information spreading in the stationary phase by analyzing the completion time of the flooding mechanism. We prove a general theorem that establishes an upper bound on flooding time in any stationary Markovian evolving graph in terms of its node-expansion properties. We apply our theorem in two natural and relevant cases of such dynamic graphs: edge-Markovian evolving graphs where the probability of existence of any edge at time t depends on the existence (or not) of the same edge at time t-1; geometric Markovian evolving graphs where the Markovian behaviour is yielded by n mobile radio stations, with fixed transmission radius, that perform n independent random walks over a square region of the plane. In both cases, the obtained upper bounds are shown to be nearly tight and, in fact, they turn out to be tight for a large range of the values of the input parameters.

The Min Energy Broadcast problem consists in assigning transmission ranges to the nodes of an ad-hoc network in order to guarantee a directed spanning tree from a given source node and, at the same time, to minimize the energy consumption (i.e. the energy cost) yielded by the range assignment. Min Energy Broadcast is known to be NP-hard. We consider random-grid networks where nodes are chosen independently at random from the n points of a √n x √n square grid in the plane. The probability of the existence of a node at a given point of the grid does depend on that point, that is, the probability distribution can be non-uniform.

We introduce stochastic time-dependency in evolving graphs: starting from an arbitrary initial edge probability distribution, at every time step, every edge changes its state (existing or not) according to a two-state Markovian process with probabilities p (edge birth-rate) and q (edge death-rate). If an edge exists at time t then, at time t+1, it dies with probability q. If instead the edge does not exist at time t, then it will come into existence at time t+1 with probability p.

We study the completion time of distributed broadcast protocols in dynamic radio networks. The dynamic network is modelled by means of adversaries: we consider two of them that somewhat are the extremal cases.

Summary form only given. We introduce the weighted version of the range assignment problem in which the cost a station s pays to transmit to another station depends on the distance between the stations and on the energy cost of station s. Most of the algorithm results for the unweighted range assignment problem can not be applied to the weighted version. We thus provide a set of algorithmic results for this version and discuss some interesting related open questions.

One of the most frequent tasks in multi-hop synchronous radio networks is the multi-broadcast operation: it consists in performing r independent message broadcasts through a network of n nodes. We investigate the case in which messages have logarithmic bounded size and the nodes have no knowledge of the topology (i.e. unknown networks).

The study of the approximability properties of NP-hard optimization problems has recently made great advances mainly due to the results obtained in the field of proof checking. The last important breakthrough proves the APX-completeness of several important optimization problems and thus reconciles "two distinct views of approximation classes: syntactic and computational" [S. Khanna et al., in Proc. 35th IEEE Symp. on Foundations of Computer Science, IEEE Computer Society Press, Los Alamitos, CA, 1994, pp. 819--830]. In this paper we obtain new results on the structure of several computationally-defined approximation classes. In particular, after defining a new approximation preserving reducibility to be used for asmany approximation classes as possible, we give the first examples of natural NPO-complete problems and the first examples of natural APX-intermediate problems. Moreover, we state new connections between the approximability properties and the query complexity of NPO problems.

Well-known examples of dot-operators are the existential, the counting, and the BP-operator. We will generalize this notion of a dot-operator so that every language A will determine an operator A/spl middot/. In fact we will introduce the more general notion of promise dot-operators for which the BP-operator is an example. Dot-operators are a refinement of the leaf language concept because the class determined by a leaf language A equals A/spl middot/P. Moreover we are able to represent not only classes but reducibilities, in fact most of the known polynomial-time reducibilities can be represented by dot-operators. We show that two languages determine the same dot-operator if and only if they are reducible to each other by polylog-time uniform monotone projections.

The study of the approximability properties of NP-hard optimization problems has recently made great advances mainly due to the results obtained in the field of proof checking. The last important breakthrough proves the APX-completeness of several important optimization problems and thus reconciles "two distinct views of approximation classes: syntactic and computational" [S. Khanna et al., in Proc. 35th IEEE Symp. on Foundations of Computer Science, IEEE Computer Society Press, Los Alamitos, CA, 1994, pp. 819--830]. In this paper we obtain new results on the structure of several computationally-defined approximation classes. In particular, after defining a new approximation preserving reducibility to be used for asmany approximation classes as possible, we give the first examples of natural NPO-complete problems and the first examples of natural APX-intermediate problems. Moreover, we state new connections between the approximability properties and the query complexity of NPO problems.

This paper explores two generalizations within NP of self-reducibility: Arvind and Biswas’s kernel constructibility and Khadilkar and Biswas’s committability. Informally stated, kernel constructible sets have (generalized) self reductions that are easy to check, though perhaps hard to compute, and committable sets are those sets for which the potential correctness of a partial proof of set membership can be checked via a query to the same set (that is, via a self-reduction). We study these two notions of generalized self reducibility on nondense sets. We show that sparse kernel constructible sets are of low complexity, extend previous results showing that sparse committable sets are of low complexity, and provide structural evidence of interest in its own right—namely, that if all sparse disjunctively self-reducible sets are in P then ${\text{FewP}} \cap {\text{FewP}}$ is not P-bi-immune—that our extension is unlikely to be extended further. We obtain density-based sufficient conditions for kernel-constructibility: sets whose complements are captured by nondense sets are perforce kernel constructible. Using sparse languages and Kolmogorov complexity theory as tools, we argue that kernel constructibility is orthogonal to standard notions of complexity.