
The \emph{UndecidedState Dynamics} is a wellknown protocol for distributed
consensus. We analyze it in the parallel \pull\ communication model on the
complete graph for the \emph{binary} case (every node can either support one of
\emph{two} possible colors, or be in the undecided state).
An interesting open question is whether this dynamics \emph{always} (i.e.,
starting from an arbitrary initial configuration) reaches consensus
\emph{quickly} (i.e., within a polylogarithmic number of rounds) in a complete
graph with $n$ nodes. Previous work in this setting only considers initial
color configurations with no undecided nodes and a large \emph{bias} (i.e.,
$\Theta(n)$) towards the majority color.
In this paper we present an \textit{unconditional} analysis of the
UndecidedState Dynamics that answers to the above question in the affirmative.
We prove that, starting from \textit{any} initial configuration, the process
reaches a monochromatic configuration within $O(\log n)$ rounds, with high
probability. This bound turns out to be tight. Our analysis also shows that, if
the initial configuration has bias $\Omega(\sqrt{n\log n})$, then the dynamics
converges toward the initial majority color, with high probability.

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 twocommunity 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 firstmoment analysis showing that, for a
large class of almostregular 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 secondmoment 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.

Logit Dynamics [Blume, Games and Economic Behavior, 1993] are randomized best
response dynamics for strategic games: at every time step a player is selected
uniformly at random and she chooses a new strategy according to a probability
distribution biased toward strategies promising higher payoffs. This process
defines an ergodic Markov chain, over the set of strategy profiles of the game,
whose unique stationary distribution is the longterm equilibrium concept for
the game. However, when the mixing time of the chain is large (e.g.,
exponential in the number of players), the stationary distribution loses its
appeal as equilibrium concept, and the transient phase of the Markov chain
becomes important. It can happen that the chain is "metastable", i.e., on a
timescale shorter than the mixing time, it stays close to some probability
distribution over the state space, while in a timescale multiple of the mixing
time it jumps from one distribution to another.
In this paper we give a quantitative definition of "metastable probability
distributions" for a Markov chain and we study the metastability of the logit
dynamics for some classes of coordination games. We first consider a pure
$n$player coordination game that highlights the distinctive features of our
metastability notion based on distributions. Then, we study coordination games
on the clique without a riskdominant strategy (which are equivalent to the
wellknown Glauber dynamics for the CurieWeiss model) and coordination games
on a ring (both with and without riskdominant strategy).

Given an underlying graph, we consider the following \emph{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 nontrivial even in a centralized setting.

We study the following synchronous process that we call "repeated
ballsintobins". The process is started by assigning $n$ balls to $n$ bins in
an arbitrary way. In every subsequent round, from each nonempty bin one ball
is chosen according to some fixed strategy (random, FIFO, etc), and reassigned
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 will converge to a legitimate configuration in linear time and then it
will only take 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 selfstabilizing and that every ball traverses all bins in
$\mathcal{O}(n \log^2 n)$ rounds, w.h.p.

We consider the following distributed consensus problem: Each node in a
complete communication network of size $n$ initially holds an \emph{opinion},
which is chosen arbitrarily from a finite set $\Sigma$. The system must
converge toward a consensus state in which all, or almost all nodes, hold the
same opinion. Moreover, this opinion should be \emph{valid}, i.e., it should be
one among those initially present in the system. This condition should be met
even in the presence of an adaptive, malicious adversary who can modify the
opinions of a bounded number of nodes in every round.
We consider the \emph{3majority 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 \leqslant n^{\alpha}$, where $\alpha$ is a
suitable positive constant, the 3majority 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 $o(\sqrt{n})$ nodes at each round.
Previously, the convergence of the 3majority protocol was known for
$\Sigma = 2$ only, with an argument that is robust to adversarial errors. On
the other hand, no anonymous, uniformgossip protocol that is robust to
adversarial errors was known for $\Sigma > 2$.

We study a \emph{PluralityConsensus} process in which each of $n$ anonymous
agents of a communication network initially supports an opinion (a color chosen
from a finite set $[k]$). Then, in every (synchronous) round, each agent can
revise his color according to the opinions currently held by a random sample of
his neighbors. It is assumed that the initial color configuration exhibits a
sufficiently large \emph{bias} $s$ towards a fixed plurality color, that is,
the number of nodes supporting the plurality color exceeds the number of nodes
supporting any other color by $s$ additional nodes. The goal is having the
process to converge to the \emph{stable} configuration in which all nodes
support the initial plurality. We consider a basic model in which the network
is a clique and the update rule (called here the \emph{3majority dynamics}) of
the process is the following: each agent looks at the colors of three random
neighbors and then applies the majority rule (breaking ties uniformly).
We prove that the process converges in time $\mathcal{O}( \min\{ k, (n/\log
n)^{1/3} \} \, \log n )$ with high probability, provided that $s \geqslant c
\sqrt{ \min\{ 2k, (n/\log n)^{1/3} \}\, n \log n}$.
We then prove that our upper bound above is tight as long as $k \leqslant
(n/\log n)^{1/4}$. This fact implies an exponential timegap between the
pluralityconsensus process and the \emph{median} process studied by Doerr et
al. in [ACM SPAA'11].
A natural question is whether looking at more (than three) random neighbors
can significantly speed up the process. We provide a negative answer to this
question: In particular, we show that samples of polylogarithmic size can speed
up the process by a polylogarithmic factor only.

By using concrete scenarios, we present and discuss a new concept of
probabilistic SelfStabilization in Distributed Systems.

Logit choice dynamics are a family of randomized best response dynamics based
on the logit choice function [McFadden, 1974], used for modeling players with
limited rationality and knowledge. In this paper we study the alllogit
dynamics, where at each time step all players concurrently update their
strategies according to the logit choice function. In the well studied
onelogit dynamics [Blume, 1993] instead at each step only one randomly chosen
player is allowed to update.
We study properties of the alllogit dynamics in the context of local
interaction games, a class of games that has been used to model complex social
phenomena and physical systems. In a local interaction game, players are the
vertices of a social graph whose edges are twoplayer potential games. Each
player picks one strategy to be played for all the games she is involved in and
the payoff of the player is the sum of the payoffs from each of the games. We
prove that local interaction games characterize the class of games for which
the alllogit dynamics is reversible.
We then compare the stationary behavior of onelogit and alllogit dynamics.
Specifically, we look at the expected value of a notable class of observables,
that we call decomposable observables. We prove that the difference between the
expected values of the observables at stationarity for the two dynamics depends
only on the rationality level beta and on the distance of the social graph from
a bipartite graph. In particular, if the social graph is bipartite then
decomposable observables have the same expected value. Finally, we show that
the mixing time of the alllogit dynamics has the same twofold behavior that
has been highlighted in the case of the onelogit: for some games it
exponentially depends on the rationality level beta, whereas for other games it
can be upper bounded by a function independent from beta.

Randomized gossip is one of the most popular way of disseminating information
in large scale networks. This method is appreciated for its simplicity,
robustness, and efficiency. In the "push" protocol, every informed node
selects, at every time step (a.k.a. round), one of its neighboring node
uniformly at random and forwards the information to this node. This protocol is
known to complete information spreading in $O(\log n)$ time steps with high
probability (w.h.p.) in several families of $n$node "static" networks. The
Push protocol has also been empirically shown to perform well in practice, and,
specifically, to be robust against dynamic topological changes.
In this paper, we aim at analyzing the Push protocol in "dynamic" networks.
We consider the "edgeMarkovian" evolving graph model which captures natural
temporal dependencies between the structure of the network at time $t$, and the
one at time $t+1$. Precisely, a nonedge appears with probability $p$, while an
existing edge dies with probability $q$. In order to fit with realworld
traces, we mostly concentrate our study on the case where $p=\Omega(1/n)$ and
$q$ is constant. We prove that, in this realistic scenario, the Push protocol
does perform well, completing information spreading in $O(\log n)$ time steps
w.h.p. Note that this performance holds even when the network is, w.h.p.,
disconnected at every time step (e.g., when $p << (\log n) / n$). Our result
provides the first formal argument demonstrating the robustness of the Push
protocol against network changes. We also address other ranges of parameters
$p$ and $q$ (e.g., $p+q=1$ with arbitrary $p$ and $q$, and $p=1/n$ with
arbitrary $q$). Although they do not precisely fit with the measures performed
on realworld traces, they can be of independent interest for other settings.
The results in these cases confirm the positive impact of dynamism.

We present the first general bounds on the mixing time of the Markov chain
associated to the logit dynamics for wide classes of strategic games. The logit
dynamics with inverse noise beta describes the behavior of a complex system
whose individual components act selfishly and keep responding according to some
partial ("noisy") knowledge of the system, where the capacity of the agent to
know the system and compute her best move is measured by the inverse of the
parameter beta.
In particular, we prove nearly tight bounds for potential games and games
with dominant strategies. Our results show that, for potential games, the
mixing time is upper and lower bounded by an exponential in the inverse of the
noise and in the maximum potential difference. Instead, for games with dominant
strategies, the mixing time cannot grow arbitrarily with the inverse of the
noise.
Finally, we refine our analysis for a subclass of potential games called
graphical coordination games, a class of games that have been previously
studied in Physics and, more recently, in Computer Science in the context of
diffusion of new technologies. We give evidence that the mixing time of the
logit dynamics for these games strongly depends on the structure of the
underlying graph. We prove that the mixing time of the logit dynamics for these
games can be upper bounded by a function that is exponential in the cutwidth of
the underlying graph and in the inverse of noise. Moreover, we consider two
specific and popular network topologies, the clique and the ring. For games
played on a clique we prove an almost matching lower bound on the mixing time
of the logit dynamics that is exponential in the inverse of the noise and in
the maximum potential difference, while for games played on a ring we prove
that the time of convergence of the logit dynamics to its stationary
distribution is significantly shorter.

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 twofold: first, we present a simple
pairwise contact model  called the HomeMEG 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
HomeMEG 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.
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.

We study "logit dynamics" [Blume, Games and Economic Behavior, 1993] for
strategic games. This dynamics works as follows: at every stage of the game a
player is selected uniformly at random and she plays according to a "noisy"
bestresponse where the noise level is tuned by a parameter $\beta$. Such a
dynamics defines a family of ergodic Markov chains, indexed by $\beta$, over
the set of strategy profiles. We believe that the stationary distribution of
these Markov chains gives a meaningful description of the longterm behavior
for systems whose agents are not completely rational.
Our aim is twofold: On the one hand, we are interested in evaluating the
performance of the game at equilibrium, i.e. the expected social welfare when
the strategy profiles are random according to the stationary distribution. On
the other hand, we want to estimate how long it takes, for a system starting at
an arbitrary profile and running the logit dynamics, to get close to its
stationary distribution; i.e., the "mixing time" of the chain.
In this paper we study the stationary expected social welfare for the
3player CK game, for 2player coordination games, and for two simple
$n$player games. For all these games, we also give almost tight upper and
lower bounds on the mixing time of logit dynamics. Our results show two
different behaviors: in some games the mixing time depends exponentially on
$\beta$, while for other games it can be upper bounded by a function
independent of $\beta$.

Markovian evolving graphs are dynamicgraph 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 dynamicnetwork
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 nodeexpansion 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.
"EdgeMarkovian 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 "t1".
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.

In this paper we study the connectivity problem for wireless networks under
the Signal to Interference plus Noise Ratio (SINR) model. Given a set of radio
transmitters distributed in some area, we seek to build a directed strongly
connected communication graph, and compute an edge coloring of this graph such
that the transmitterreceiver pairs in each color class can communicate
simultaneously. Depending on the interference model, more or less colors,
corresponding to the number of frequencies or time slots, are necessary. We
consider the SINR model that compares the received power of a signal at a
receiver to the sum of the strength of other signals plus ambient noise . The
strength of a signal is assumed to fade polynomially with the distance from the
sender, depending on the socalled pathloss exponent $\alpha$.
We show that, when all transmitters use the same power, the number of colors
needed is constant in onedimensional grids if $\alpha>1$ as well as in
twodimensional grids if $\alpha>2$. For smaller pathloss exponents and
twodimensional grids we prove upper and lower bounds in the order of
$\mathcal{O}(\log n)$ and $\Omega(\log n/\log\log n)$ for $\alpha=2$ and
$\Theta(n^{2/\alpha1})$ for $\alpha<2$ respectively. If nodes are distributed
uniformly at random on the interval $[0,1]$, a \emph{regular} coloring of
$\mathcal{O}(\log n)$ colors guarantees connectivity, while $\Omega(\log \log
n)$ colors are required for any coloring.

We consider a Mobile Adhoc NETworks (MANET) formed by "n" nodes that move
independently at random over a finite square region of the plane. Nodes
exchange data if they are at distance at most "r" within each other, where r>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 the speed of information
spreading in dynamic networks.
We derive a nearlytight upper bound on the flooding time which is a
decreasing function of the maximal "velocity" of the nodes. It turns out that,
when the node velocity is sufficiently high, even if the node transmission
radius "r" is far below the "connectivity threshold", the flooding time does
not asymptotically depend on "r". This implies that flooding can be very fast
even though every "snapshot" (i.e. the static random geometric graph at any
fixed time) of the MANET is fully disconnected. Data reach all nodes quickly
despite these ones use very low transmission power.
Our result is the first analytical evidence of the fact that high, random
node mobility strongly speedup information spreading and, at the same time,
let nodes save energy.