A randomized distributed algorithm called RAES was introduced in [Becchetti et al., 2020] to extract a bounded-degree expander from a dense n-vertex expander graph G = (V, E). The algorithm relies on a simple threshold-based procedure. A key assumption in [Becchetti et al., 2020] is that the input graph G is static - i.e., both its vertex set V and edge set E remain unchanged throughout the process - while the analysis of raes in dynamic models is left as a major open question. In this work, we investigate the behavior of RAES under a dynamic graph model induced by a streaming node-churn process (also known as the sliding window model), where, at each discrete round, a new node joins the graph and the oldest node departs. This process yields a bounded-degree dynamic graph 𝒢 = {G_t = (V_t, E_t) : t ∈ ℕ} that captures essential characteristics of peer-to-peer networks - specifically, node churn and threshold on the number of connections each node can manage. We prove that every snapshot G_t in the dynamic graph sequence has good expansion properties with high probability. Furthermore, we leverage this property to establish a logarithmic upper bound on the completion time of the well-known PUSH and PULL rumor spreading protocols over the dynamic graph 𝒢.

We consider the task of performing Jaccard similarity queries over a large collection of items that are dynamically updated according to a streaming input model. An item here is a subset of a large universe U of elements. A well-studied approach to address this important problem in data mining is to design fast-similarity data sketches. In this paper, we focus on global solutions for this problem, i.e., a single data structure which is able to answer both Similarity Estimation and All-Candidate Pairs queries, while also dynamically managing an arbitrary, online sequence of element insertions and deletions received in input.

In this work, we propose, analyze and empirically validate a lazy-update approach to maintain accurate approximations of the 2-hop neighborhoods of dynamic graphs resulting from sequences of edge insertions. We first show that under random input sequences, our algorithm exhibits an optimal trade-off between accuracy and insertion cost: it only performs [EQUATION] (amortized) updates per edge insertion, while the estimated size of any vertex's 2-hop neighborhood is at most a factor ε away from its true value in most cases, regardless of the underlying graph topology and for any ε > 0. As a further theoretical contribution, we explore adversarial scenarios that can force our approach into a worst-case behavior at any given time t of interest. We show that while worst-case input sequences do exist, a necessary condition for them to occur is that the girth of the graph released up to time t be at most 4. Finally, we conduct extensive experiments on a collection of real, incremental social networks of different sizes, which typically have low girth. Empirical results are consistent with and typically better than our theoretical analysis anticipates. This further supports the robustness of our theoretical findings: forcing our algorithm into a worst-case behavior not only requires topologies characterized by a low girth, but also carefully crafted input sequences that are unlikely to occur in practice. Combined with standard sketching techniques, our lazy approach proves an effective and efficient tool to support key neighborhood queries on large, incremental graphs, including neighborhood size, Jaccard similarity between neighborhoods and, in general, functions of the union and/or intersection of 2-hop neighborhoods.

We study the minority-opinion dynamics over a fully-connected network of n nodes with binary opinions. Upon activation, a node receives a sample of opinions from a limited number of neighbors chosen uniformly at random. Each activated node then adopts the opinion that is least common within the received sample.

We investigate opinion dynamics in a fully-connected system, consisting of n agents, where one of the opinions, called correct, represents a piece of information to disseminate. One source agent initially holds the correct opinion and remains with this opinion throughout the execution. The goal of the remaining agents is to quickly agree on this correct opinion. At each round, one agent chosen uniformly at random is activated: unless it is the source, the agent pulls the opinions of l random agents and then updates its opinion according to some rule. We consider a restricted setting, in which agents have no memory and they only revise their opinions on the basis of those of the agents they currently sample. This setting encompasses very popular opinion dynamics, such as the voter model and best-of-k majority rules. Qualitatively speaking, we show that lack of memory prevents efficient convergence. Specifically, we prove that any dynamics requires Omega(n^2) expected time, even under a strong version of the model in which activated agents have complete access to the current configuration of the entire system, i.e., the case l=n. Conversely, we prove that the simple voter model (in which l=1) correctly solves the problem, while almost matching the aforementioned lower bound. These results suggest that, in contrast to symmetric consensus problems (that do not involve a notion of correct opinion), fast convergence on the correct opinion using stochastic opinion dynamics may require the use of memory.

We study expansion and information diffusion properties of dynamic networks, i.e., networks whose topologies evolve over time as nodes enter or leave the system and edges are continuously created or destroyed. In this scenario, we investigate flooding as a basic information diffusion mechanism. We are interested in models that are likely to result in sparse networks, i.e., in networks containing$O(n)$edges, with$n$the number of nodes that are present at any given time of interest, with a focus on models in which edges are created randomly according to simple probabilistic mechanisms, rather than according to carefully designed distributed algorithms. In this perspective, in all models we consider, upon joining the network, a node connects to$d=O(1)$random nodes currently in the system. On the other hand, an edge remains alive as long as both its endpoints are. For the case in which edges that fail (because one endpoint left the network) are not replaced, we show that, although the network is likely to contain$\Omega_{d}(n)$isolated nodes, flooding still informs a fraction$1-\exp(-\Omega(d))$of the nodes in time$\mathrm{O}(\log n)$with large, constant probability. Moreover, we are able to show, that at any given time, the graph exhibits a “large-set expansion” property. We further investigate models that exhibit edge regeneration, meaning that, whenever an edge$(v, w)$established by$v$fails because$w$leaves the network, it is replaced by a new random edge$(v, z)$. We show that models with edge regeneration result in evolving networks that, at any given time, are vertex expanders with high probability, so that flooding takes$\mathrm{O}(\log n)$time. The above results hold both for a simplfied streaming model of node churn and in a more realistic, continuous-time setting, in which the interval between two consecutive node arrivals follows a Poisson distribution, while nodes' lifetimes follow an exponential distribution. Previous work considered models in which either the vertex set is fixed or edges are established according to more or less sophisticated algorithms. Our motivation for studying models with simple and random edge creation mechanisms is to move one step further towards models that may eventually capture key aspects of the formation of social or peer-to-peer networks.

Motivated by the Lévy foraging hypothesis -- the premise that various animal species have adapted to follow Lévy walks to optimize their search efficiency -- we study the parallel hitting time of Lévy walks on the infinite two-dimensional grid. We consider k independent discrete-time Lévy walks, with the same exponent α ∈(1,∞), that start from the same node, and analyze the number of steps until the first walk visits a given target at distance ℓ. % We show that for any choice of k and ℓ from a large range, there is a unique optimal exponent α_k,∈ (2,3), for which the hitting time is Õ(ℓ2/k) w.h.p., while modifying the exponent by any constant term ε>0 increases the hitting time by a factor polynomial in ℓ, or the walks fail to hit the target almost surely. % Based on that, we propose a surprisingly simple and effective parallel search strategy, for the setting where k and ℓ are unknown: The exponent of each Lévy walk is just chosen independently and uniformly at random from the interval (2,3). This strategy achieves optimal search time (modulo polylogarithmic factors) among all possible algorithms (even centralized ones that know k). % Our results should be contrasted with a line of previous work showing that the exponent α = 2 is optimal for various search problems. In our setting of k parallel walks, we show that the optimal exponent depends on k and ℓ, and that randomizing the choice of the exponents works simultaneously for all k and ℓ.

Consensus and Broadcast are two fundamental problems in distributed computing, whose solutions have several applications. Intuitively, Consensus should be no harder than Broadcast, and this can be rigorously established in several models. Can Consensus be easier than Broadcast? In models that allow noiseless communication, we prove a reduction of (a suitable variant of) Broadcast to binary Consensus, that preserves the communication model and all complexity parameters such as randomness, number of rounds, communication per round, etc., while there is a loss in the success probability of the protocol. Using this reduction, we get, among other applications, the first logarithmic lower bound on the number of rounds needed to achieve Consensus in the uniform GOSSIP model on the complete graph. The lower bound is tight and, in this model, Consensus and Broadcast are equivalent. We then turn to distributed models with noisy communication channels that have been studied in the context of some bio-inspired systems. In such models, only one noisy bit is exchanged when a communication channel is established between two nodes, and so one cannot easily simulate a noiseless protocol by using error-correcting codes. An Ω(ε^{-2} n) lower bound is proved by Boczkowski et al. [PLOS Comp. Bio. 2018] on the convergence time of binary Broadcast in one such model (noisy uniform PULL), where ε is a parameter that measures the amount of noise). We prove an O(ε^{-2} log n) upper bound on the convergence time of binary Consensus in such model, thus establishing an exponential complexity gap between Consensus versus Broadcast. We also prove our upper bound above is tight and this implies, for binary Consensus, a further strong complexity gap between noisy uniform PULL and noisy uniform PUSH. Finally, we show a Θ(ε^{-2} n log n) bound for Broadcast in the noisy uniform PULL.

It follows from the Marcus-Spielman-Srivastava proof of the Kadison-Singer conjecture that if G = (V, E) is a Δ-regular dense expander then there is an edge-induced subgraph H = (V, Eh) of G of constant maximum degree which is also an expander. As with other consequences of the MSS theorem, it is not clear how one would explicitly construct such a subgraph. We show that such a subgraph (although with quantitatively weaker expansion and near-regularity properties than those predicted by MSS) can be constructed with high probability in linear time, via a simple algorithm. Our algorithm allows a distributed implementation that runs in O(log n) rounds and does O(n) total work with high probability. The analysis of the algorithm is complicated by the complex dependencies that arise between edges and between choices made in different rounds. We sidestep these difficulties by following the combinatorial approach of counting the number of possible random choices of the algorithm which lead to failure. We do so by a compression argument showing that such random choices can be encoded with a non-trivial compression. Our algorithm bears some similarity to the way agents construct a communication graph in a peer-to-peer network, and, in the bipartite case, to the way agents select servers in blockchain protocols.

We study parallel Load Balancing protocols for a client-server distributed model defined as follows. There is a set C of n clients and a set S of n servers where each client has (at most) a constant number d ≥ 1 of requests that must be assigned to some server. The client set and the server one are connected to each other via a fixed bipartite graph: the requests of client v can only be sent to the servers in its neighborhood N(v). The goal is to assign every client request so as to minimize the maximum load of the servers.

Given an underlying graph, we consider the following dynamics: Initially, each node locally chooses a value in $\{-1,1\}$, uniformly at random and independently of other nodes. Then, in each consecutive round, every node updates its local value to the average of the values held by its neighbors, at the same time applying an elementary, local clustering rule that only depends on the current and the previous values held by the node. We prove that the process resulting from this dynamics produces a clustering that exactly or approximately (depending on the graph) reflects the underlying cut in logarithmic time, under various graph models that exhibit a sparse balanced cut, including the stochastic block model. We also prove that a natural extension of this dynamics performs community detection on a regularized version of the stochastic block model with multiple communities. Rather surprisingly, our results provide rigorous evidence for the ability of an extremely simple and natural dynamics to perform community detection, a computational problem which is nontrivial even in a centralized setting.

We study the following synchronous process that we call repeated balls-into-bins. The process is started by assigning n balls to n bins in an arbitrary fashion. In every subsequent round, one ball is extracted from each non-empty bin according to some fixed strategy (random, FIFO, etc), and re-assigned to one of the n bins uniformly at random. We define a configuration legitimate if its maximum load is $$\mathcal {O}(\log n)$$ . We prove that, starting from any configuration, the process converges to a legitimate configuration in linear time and then only takes on legitimate configurations over a period of length bounded by any polynomial in n, with high probability (w.h.p.). This implies that the process is self-stabilizing and that every ball traverses all bins within $$\mathcal {O}(n\log ^2 n)$$ rounds, w.h.p.

Consider the following asynchronous, opportunistic communication model over a graph $G$: in each round, one edge is activated uniformly and independently at random and (only) its two endpoints can exchange messages and perform local computations. Under this model, we study the following random process: The first time a vertex is an endpoint of an active edge, it chooses a random number, say $\pm 1$ with probability $1/2$; then, in each round, the two endpoints of the currently active edge update their values to their average. We show that, if $G$ exhibits a two-community structure (for example, two expanders connected by a sparse cut), the values held by the nodes will collectively reflect the underlying community structure over a suitable phase of the above process, allowing efficient and effective recovery in important cases. In more detail, we first provide a first-moment analysis showing that, for a large class of almost-regular clustered graphs that includes the stochastic block model, the expected values held by all but a negligible fraction of the nodes eventually reflect the underlying cut signal. We prove this property emerges after a mixing period of length $\mathcal O(n\log n)$. We further provide a second-moment analysis for a more restricted class of regular clustered graphs that includes the regular stochastic block model. For this case, we are able to show that most nodes can efficiently and locally identify their community of reference over a suitable time window. This results in the first opportunistic protocols that approximately recover community structure using only polylogarithmic work per node. Even for the above class of regular graphs, our second moment analysis requires new concentration bounds on the product of certain random matrices that are technically challenging and possibly of independent interest.

The rational fair consensus problem can be informally defined as follows. Consider a network of n (selfish) rational agents, each of them initially supporting a color chosen from a finite set Σ. The goal is to design a protocol that leads the network to a stable monochromatic configuration (i.e. a consensus) such that the probability that the winning color is c is equal to the fraction of the agents that initially support c, for any c ∈ Σ. Furthermore, this fairness property must be guaranteed (with high probability) even in presence of any fixed coalition of rational agents that may deviate from the protocol in order to increase the winning probability of their supported colors. A protocol having this property, in presence of coalitions of size at most t, is said to be a whp - t-strong equilibrium. We investigate, for the first time, the rational fair consensus problem in the GOSSIP communication model where, at every round, every agent can actively contact at most one neighbor via a push/pull operation. We provide a randomized GOSSIP protocol that, starting from any initial color configuration of the complete graph, achieves rational fair consensus within O(log n) rounds using messages of O(log2n) size, w.h.p. More in details, we prove that our protocol is a whp t-strong equilibrium for any t = o(n/ log n) and, moreover, it tolerates worst-case permanent faults provided that the number of non-faulty agents is Ω(n). As far as we know, our protocol is the first solution which avoids any all-to-all communication, thus resulting in o(n2) message complexity.

We study consensus processes on the complete graph of n nodes. Initially, each node supports one up to n different opinions. Nodes randomly and in parallel sample the opinions of constantly many nodes. Based on these samples, they use an update rule to change their own opinion. The goal is to reach consensus, a configuration where all nodes support the same opinion.

Given an underlying graph, we consider the following dynamics: Initially, each node locally chooses a value in {-1,1}, uniformly at random and independently of other nodes. Then, in each consecutive round, every node updates its local value to the average of the values held by its neighbors, at the same time applying an elementary, local clustering rule that only depends on the current and the previous values held by the node. We prove that the process resulting from this dynamics produces a clustering that exactly or approximately (depending on the graph) reflects the underlying cut in logarithmic time, under various graph models that exhibit a sparse balanced cut, including the stochastic block model. We also prove that a natural extension of this dynamics performs community detection on a regularized version of the stochastic block model with multiple communities. Rather surprisingly, our results provide rigorous evidence for the ability of an extremely simple and natural dynamics to address a computational problem that is non-trivial even in a centralized setting. Distributed Algorithms, Averaging Dynamics, Community Detection, Spectral Analysis, Stochastic Block Models.

The Undecided-State Dynamics is a well-known protocol that achieves Consensus in distributed systems formed by a set of n anonymous nodes interacting via a communication network. We consider this dynamics in the parallel PULL communication model on the complete graph for the binary case, i.e., when every node can either support one of two possible colors or stay in the undecided state. Previous work in this setting only considers initial color configurations with no undecided nodes and a large bias (i.e., Theta(n)) towards the majority color. A interesting open question here is whether this dynamics reaches consensus quickly, i.e. within a polylogarithmic number of rounds. In this paper we present an unconditional analysis of the Undecided-State Dynamics which answers to the above question in the affirmative. Our analysis shows that, starting from any initial configuration, the Undecided-State Dynamics reaches a monochromatic configuration within O(log^2 n) rounds, with high probability (w.h.p.). Moreover, we prove that if the initial configuration has bias Omega(sqrt(n log n)), then the dynamics converges toward the initial majority color within O(log n) round, w.h.p. At the heart of our approach there is a new analysis of the symmetry-breaking phase that the process must perform in order to escape from (almost-)unbiased configurations. Previous symmetry-breaking analysis of consensus dynamics essentially concern sequential communication models (such as Population Protocols) and/or symmetric updated rules (such as majority rules).

We consider the following distributed consensus problem: Each node in a complete communication network of size n initially holds an opinion, which is chosen arbitrarily from a finite set Σ. The system must converge toward a consensus state in which all, or almost all nodes, hold the same opinion. Moreover, this opinion should be valid, i.e., it should be one among those initially present in the system. This condition should be met even in the presence of a malicious adversary who can modify the opinions of a bounded subset of nodes, adaptively chosen in every round. We consider the 3-majority dynamics: At every round, every node pulls the opinion from three random neighbors and sets his new opinion to the majority one (ties are broken arbitrarily). Let k be the number of valid opinions. We show that, if k ≤ nα, where α is a suitable positive constant, the 3-majority dynamics converges in time polynomial in k and log n with high probability even in the presence of an adversary who can affect up to nodes at each round. Previously, the convergence of the 3-majority protocol was known for |Σ| = 2 only, with an argument that is robust to adversarial errors. On the other hand, no anonymous, uniform-gossip protocol that is robust to adversarial errors was known for |Σ| > 2.

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 the following synchronous process that we call repeated balls-into-bins. The process is started by assigning n balls to n bins in an arbitrary way. Then, in every subsequent round, one ball is chosen according to some fixed strategy (random, FIFO, etc) from each non-empty bin, and re-assigned to one of the n bins uniformly at random. This process corresponds to a non-reversible Markov chain and our aim is to study its self-stabilization properties with respect to the maximum(bin) load and some related performance measures. We define a configuration (i.e., a state) legitimate if its maximum load is O(log n). We first prove that, starting from any legitimate configuration, the process will only take on legitimate configurations over a period of length bounded by any polynomial in n, with high probability (w.h.p.). Further we prove that, starting from any configuration, the process converges to a legitimate configuration in linear time, w.h.p. This implies that the process is self-stabilizing w.h.p. and, moreover, that every ball traverses all bins in O(n log2 n) rounds, w.h.p. The latter result can also be interpreted as an almost tight bound on the cover time for the problem of parallel resource assignment in the complete graph.

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).

We show how to simulate any BPP algorithm in polynomial time by using a weak random source of r bits and min-entropy $r^{\gamma}$ for any $\gamma >0$. This follows from a more general result about sampling with weak random sources. Our result matches an information-theoretic lower bound and solves a question that has been open for some years. The previous best results were a polynomial time simulation of RP [M. Saks, A. Srinivasan, and S. Zhou, Proc. 27th ACM Symp. on Theory of Computing, 1995, pp. 479--488] and a quasi-polynomial time simulation of BPP [A. Ta-Shma, Proc. 28th ACM Symp. on Theory of Computing, 1996, pp. 276--285]. Departing significantly from previous related works, we do not use extractors; instead, we use the OR-disperser of Saks, Srinivasan, and Zhou in combination with a tricky use of hitting sets borrowed from [Andreev, Clementi, and Rolim, J. ACM, 45 (1998), pp. 179--213].

We show that quick hitting set generators can replace quick pseudorandom generators to derandomize any probabilistic two-sided error algorithms. Up to now quick hitting set generators have been known as the general and uniform derandomization method for probabilistic one-sided error algorithms, while quick pseudorandom generators as the generators as the general and uniform method to derandomize probabilistic two-sided error algorithms. Our method is based on a deterministic algorithm that, given a Boolean circuit C and given access to a hitting set generator, constructs a discrepancy set for C . The main novelty is that the discrepancy set depends on C , so the new derandomization method is not uniform (i.e., not oblivious ). The algorithm works in time exponential in k(p(n)) where k (*) is the price of the hitting set generator and p (*) is a polynomial function in the size of C . We thus prove that if a logarithmic price quick hitting set generator exists then BPP = P.

We show how to simulate any BPP algorithm in polynomial time using a weak random source of min-entropy r/sup /spl gamma// for any /spl gamma/>0. This follows from a more general result about sampling with weak random sources. Our result matches an information-theoretic lower bound and solves a question that has been open for some years. The previous best results were a polynomial time simulation of RP (Saks et al., 1995) and a n(log/sup (k)/n)-time simulation of BPP for fixed k (Ta-Shma, 1996). Departing significantly from previous related works, we do not use extractors; instead we use the OR-disperser of (Saks et al., 1995) in combination with a tricky use of hitting sets borrowed from Andreev et al. (1996). Of independent interest is our new (simplified) proof of the main result of Andreev et al., (1996). Our proof also gives some new hardness/randomness trade-offs for parallel classes.

Problems related to message communication and traffic control have been assuming more and more importance due the massive use of computer networks. Scheduling a set of messages in a store and forward network means assigning to them network resources in order to deliver each message to its respective destination. The goal of typical scheduling problems is to devise strategies of assignments that minimize the delivery time of all messages or, alternatively, their total end-to-end delay. Both problems have been proven to be network performance (NP)-hard even under very restrictive hypothesis. We study the computational complexity of approximating the minimum end-to-end delay. Unfortunately, it turns out that finding an approximated solution with approximation ratio smaller than k/sup 1/10/ is as difficult as finding the optimal solution (where k is the number of messages in the network). More precisely, approximating the optimum delay is NP-hard even when a nonconstant approximation ratio is allowed. This result holds also in the case of layered networks. We then prove that if we consider a particular class of local schedules (i.e., distributed strategies that can only use information about limited regions of the network) then the approximation error cannot be bounded by any sublinear function in k. Such results also provide a lower bound on the approximation of the minimum delivery time problem. Thus, if the attention is restricted to polynomial-time algorithms, the only possibility is designing heuristics that behave well on average. As a first step to this aim, we evaluate the expected approximation error of some simple heuristics using several experimental tests.

Store and forward networks are a convenient model to represent problems in the areas of message communication and traffic control. The goal of a typical scheduling problem is to devise an optimal strategy to send messages from their source sites into their sink ones following paths in the network. In this paper the computational complexity of such a problem is analyzed in the cases of fixed and dynamically variable paths. Unfortunately, it turns out that both of the versions of the considered problem are NP-complete even under very restrictive hypothesis. Moreover, they are not approximable, that is, they can be solved only by polynomial-time heuristic algorithms such that the distance between the exact and the approximate solution is not bounded by any fixed value.>