Transcript Johari|Gossip

Fluid Limits for Gossip Processes
Vahideh Manshadi and Ramesh Johari
DARPA ITMANET Meeting
March 5-6, 2009
Fluid limits for gossip processes
V. Manshadi and R. Johari
…
…
IMPACT
MAIN RESULT:
…
STATUS QUO
ACHIEVEMENT DESCRIPTION
Gossip is a simple model for
communication between nodes:
at random times, each node contacts a
neighbor and relays its information.
Prior work has studied the time until all
nodes acquire the information.
Two versions of this model: a “micro”
model and a “macro” model.
We consider a random graph model where each node
has d neighbors, and we consider a limit where the
number of nodes N approaches infinity.
We prove that the (random) sample path of the
micro model converges to the (deterministic) path
of the corresponding macro model.
Micro and macro models of gossip
processes have been
available for several decades.
Unifying these will allow us to
translate macro-level control
insights to micro-level system
designs.
HOW IT WORKS:
I(t)
“Micro”
Time t
Time t
The micro model tracks exactly which
nodes have the information.
The macro model is a mean field limit:
what fraction of nodes have learned
the information?
We connect these two models.
Nodes that
currently do not
have the info
We approximately characterize how
information flows in the micro model between
the sets of informed and uninformed nodes.
This approximation is exact as N ! infinity.
ASSUMPTIONS AND LIMITATIONS:
Our results currently only apply under specific
topological assumptions.
NEXT-PHASE GOALS
NEW INSIGHTS
I(t)
“Macro”
Nodes that
currently have
the info
Several goals:
(1) Extend fluid analysis to
include heterogeneous
random graphs.
(2) Get finer understanding of
behavior when initial number
of informed nodes is
constant as N ! infinity.
(3)
Extend the model to include
link failures.
The simplicity of macroscopic models for information gossip
can be combined with the accuracy of microscopic stochastic models
Problem Definition

N sensors form a network G

Initially, set I0 of nodes receive a piece of information.

At the timepoints of a Poisson process of rate ,
each informed sensor contacts a neighbor selected
uniformly at random
If uninformed, that neighbor switches to informed with prob. p

Key questions:
How long does it take to inform all the sensors?
How does the network structure and connectivity affect the time
until all nodes (or a fraction of nodes) acquire the information?
How does the size of I0 change the required time?
Related Work
 Application of gossip protocols in sensor networks
 GCP (Gossip-based Code Propagation) for mobile wireless sensor networks
[Yann, Bertier, Fleury & Kermarrec 07].
 Geographic Gossip: Efficient Averaging for Sensor Networks [Dimakis,
Sarwate & Wainright 08].
 Microscopic model: preserve the combinatorial and probabilistic
nature of the process.
 It takes O(log(n)) to make O(n) (all) nodes informed [R. Karp, C.
Schindelhauer, S. Shenker, & B. Vocking 00].
 The constant factor depends on the network structure [Mosk-Aoyama &
Shah 06].
 Macroscopic model: treat the process as continuous and
deterministic
 A first order differential equation reasonably models the evolution [Bass 69].
 S-shaped curve for the diffusion has been observed in several experiments
 Model also studied extensively in epidemiology (SI model)
Our Work
Our work rigorously connects the microscopic and macroscopic models
using fluid limits.
Main result: We show that as number of nodes N ! 1,
the microscopic model approaches the macroscopic model.
“Micro”
I(t)
I(t)
“Macro”
Time t
We prove this result in the case of a complete graph
(including error terms) and random K-regular graphs.
Time t
Heuristic Argument
 For simplicity: assume a fully connected network
 Let I(t) = # of informed sensors at time t
 In a small period dt, approximately I(t) dt of informed nodes
contact a random neighbor.
This neighbor is uninformed with probability (N - I(t))/N. So:
 The solution is the logistic function.
We formally justify this heuristic argument
(and an analog in the case of random regular graphs).
Basic Approach
 Directly studying the sample paths of the discrete stochastic model is
not straightforward.
 Instead we consider T(x, y):
total time until y nodes are informed, given |I0| = x.
 Convenient simplification:
T(x, y) is a sum of independent exponential random variables.
 We employ laws of large numbers to study the behavior of
T(x, y) as N grows large.
y
x
Time t
T(x,y)
Results: Complete graph
Theorem 1: For complete graph with n nodes and 0 < ®1,®2<1/2,
This result can be inverted to show that the sample path of the fraction
of nodes that are informed converges to the discrete continuous model.
We can also provide a more refined analysis of TN,
to reveal that if the initial set I0 stays constant of size x as N ! 1, then:
Results: Random Regular Graph
We now assume the network is a (uniformly) random K-regular graph.
Theorem 2: For Gk and 0 < ®1,®2<1/2,
This result matches the result for the complete graph.
Key insight in the proof:
We are able to precisely analyze the number of edges present from
nodes that are interested to nodes that are uninterested.
Future Work
 Our goal: a stronger connection between macroscopic and
microscopic models (for control, for analysis, etc.)
 What about infinite graphs with specific degree distributions?
 xi fraction of sensors have di links; Nodes with high degrees are more
probable to be informed earlier.
 Idea: analyze the degree distributions in the set of informed (uninformed)
nodes and compute information flow (the size of the cut) between two sets.
 What about other classes of random graphs?
 Sensors are scattered uniformly at random, the probability that any two nodes
share a link is p; this is the Random Geometric Graph model
 Site (bond) percolated graphs model the scenarios where some of the nodes
(links) in the network fail
Idea: Couple the link failure process to an equivalent contact failure in the original
graph.