Spatial gossip and resource location protocols.
The dynamic behavior of a network in which information is changing continuously over time requires robust and efficient mechanisms for keeping nodes updated about new information. Gossip protocols are mechanisms for this task in which nodes communicate with one another according to some underlying deterministic or randomized algorithm, exchanging information in each communication step. In a variety of contexts, the use of randomization to propagate information has been found to provide better reliability and scalability than more regimented deterministic approaches.In many settings, such as a cluster of distributed computing hosts, new information is generated at individual nodes, and is most "interesting" to nodes that are nearby. Thus, we propose distance-based propagation bounds as a performance measure for gossip mechanisms: a node at distance d from the origin of a new piece of information should be able to learn about this information with a delay that grows slowly with d, and is independent of the size of the network.For nodes arranged with uniform density in Euclidean space, we present natural gossip mechanisms, called spatial gossip, that satisfy such a guarantee: new information is spread to nodes at distance d, with high probability, in O(log1 steps. Such a bound combines the desirable qualitative features of uniform gossip, in which information is spread with a delay that is logarithmic in the full network size, and deterministic flooding, in which information is spread with a delay that is linear in the distance and independent of the network size. Our mechanisms and their analysis resolve a conjecture of Demers et al. [1987].We further show an application of our gossip mechanisms to a basic resource location problem, in which nodes seek to rapidly learn the location of the nearest copy of a resource in a network. This problem, which is of considerable practical importance, can be solved by a very simple protocol using Spatial Gossip, whereas we can show that no protocol built on top of uniform gossip can inform nodes of their approximately nearest resource within poly-logarithmic time. The analysis relies on an additional useful property of spatial gossip, namely that information travels from its source to sinks along short paths not visiting points of the network far from the two nodes.
Introduction
Gossip algorithms
The dynamic behavior of a network in which information is changing continuously over time
requires robust and e#cient mechanisms for keeping nodes updated about new information.
For example, we may have a network of sensors measuring properties of the physical world,
and performing computations on the collective set of measurements in a distributed fashion
(see e.g. [4, 6, 8, 9]). As measured values change, we would like for them to be propagated
through the network rapidly. Or we may have a distributed network of computing hosts that
need to be informed about significant changes in the load on machines, or the appearance
of new resources in the network [15]; again, we would like such information to be spread
quickly through the network.
For reasons of reliability and scalability, we do not want central control for updates to
reside with a small set of nodes. Rather, we seek mechanisms by which nodes communicate
in a relatively homogeneous fashion with one another, so as to spread information updates.
Gossip protocols [3, 7] are mechanisms of this type in which nodes communicate with one
another according to some underlying deterministic or randomized algorithm, exchanging information
in each communication step. In a variety of contexts, the use of randomization for
such tasks has been found to provide better reliability and scalability than more regimented
deterministic approaches (see e.g. [1, 2, 3, 6, 13, 15, 16]).
It is useful to consider some of the issues that arise in a very simple version of our first
example. Suppose we have a network of N sensors positioned at the lattice points of a
region of the plane, monitoring conditions about the underlying environment.
We assume that there is an underlying mechanism that supports an abstraction of point-to-
point communication: in a single virtual "step," any node can send a message to any other
node, regardless of the distance separating them in the plane. All the algorithms we develop
here are built on top of such a point-to-point communication mechanism; for our purposes,
the fact that this point-to-point communication may actually be implemented by multi-hop
transmission of packets is abstracted away.
Here is a basic problem we may wish to solve in such an environment: If a sensor node x
detects abnormal conditions, it will generate an alarm message m that needs to be propagated
to all other nodes in the network. Consider the following two di#erent approaches to this
problem.
Uniform gossip. In each step, each node u chooses a node v uniformly at random, and
forwards to v all the alarm messages it knows about. A well-known result states
that with high probability, all nodes will receive a copy of a given message m within
O(log N) steps of its initial appearance [7, 10, 14].
Neighbor flooding. In each step, each node u chooses one of its closest neighbors v in the
plane, according to a round-robin ordering, and forwards to v all the alarm messages it
knows about. Clearly, any node v that is at distance d from the origin of a message m
will receive a forwarded copy of m within O(d) steps of its initial appearance. However,
the time it takes for all nodes to obtain a given message under this scheme is # N ).
Both of these algorithms follow the gossip paradigm: in each time step u picks some other
node v (either deterministically or at random) and communicates with v. We will refer to
this as u calling v. Moreover, both algorithms are very simple, since each node is essentially
following the same local rule in each time step, independently of message contents. In the
protocols we consider, the analysis will use only information that u passes to the node v it
calls, ignoring any information that u may obtain from v. In other words, all our protocols
work in the push model of communication.
In this discussion, it is crucial to distinguish between two conceptual "layers" of protocol
design: (i) a basic gossip algorithm, by which nodes choose other nodes for (point-to-point)
communication; and (ii) a gossip-based protocol built on top of a gossip algorithm, which
determines the contents of the messages that are sent, and the way in which these messages
cause nodes to update their internal states. We can view a gossip algorithm as generating
a labeled graph H on the N nodes of the network; if u communicates with v at time t,
we insert an edge (u, v) with label t into H. When we consider more complex gossip-based
protocols below, it is useful to think of a run of the underlying gossip algorithm as simply
generating a labeled graph H on which the protocol then operates.
The propagation time
The two algorithms discussed above have quite di#erent performance bounds, with uniform
gossip "filling in" the set of points exponentially faster than neighbor flooding. The neighbor
flooding algorithm, however, exhibits a desirable feature that uniform gossip is lacking:
messages are propagated to nodes with a delay that depends only on their distance from the
origin of the message, not on the total number of nodes in the system. In the examples above,
and in applications exhibiting any kind of spatial locality, this can be very important: when
an alarm is triggered, we may well want to alert nearby nodes earlier than nodes further
similarly, as resources appear in a network, we may want nodes to learn more quickly
of the resources that are closer to them. With uniform gossip, it is likely that a node adjacent
to the source of an alarm will only be alerted after news of the alarm has traveled extensively
through the network.
Our work was initially motivated by the following question: Is there a gossip algorithm -
preferably a simple one - that exhibits the best qualitative features of both uniform gossip
and neighbor flooding, by guaranteeing that a message can be propagated to any node at
distance d from its originator, with high probability, in time bounded by a polynomial in
log d? The crucial point is that such a bound would be poly-logarithmic, yet independent
of N . To make this question precise, we introduce the following definition. We will say that
a function fA (-) is a propagation time for a given gossip algorithm A if it has the following
property: Whenever a new piece of information is introduced at u, there is a high probability 1
that some sequence of communications will be able to forward it to v within O(fA (d)) steps.
Our question can now be phrased as follows: Is there a gossip algorithm with a propagation
time that is polynomial in log d?
1 When we write "with high probability" here, we mean with probability at least 1-(log(d+1)) -# , where
may appear in the constant of the expression O(fA (d)).
A gossip algorithm with good propagation time
Our first result is an a#rmative answer to this question. Rather than the lattice points of
the plane, we consider a more general setting - that of a point set with uniform density in
R D . We will make this notion precise in the next section; essentially, it is a point set in R D
with the property that every unit ball contains #(1) points.
Theorem 1.1 Let P be a set of points with uniform density in R D . For every # > 0, there is
a randomized gossip algorithm on the points in P with a propagation time that is O(log 1+# d).
In this Theorem, the O(-) includes terms depending on # and the dimension D. However,
the propagation bound is independent of the number of points in P , and in fact holds even
for infinite P .
The algorithm achieving this bound is equivalent to one proposed by Demers et al. [3],
who considered it in the context of concerns di#erent from ours. We fix an exponent #
strictly between 1 and 2. In each round, each node u chooses to communicate with a node
v with probability proportional to d -D# u,v , where d u,v denotes the distance between u and v.
Demers et al. had conjectured that this algorithm would propagate a single message to all
nodes in a D-dimensional grid of side length N with high probability in time polynomial in
log N ; a special case of Theorem 1.1 (obtained by choosing a finite grid of side length N for
our metric space) yields a proof of this conjecture.
We also show how our algorithms and their analysis can be used to provide a partial
resolution to open questions about the behavior of Astrolabe, a network resource location
service developed by van Renesse [15]. Astrolabe relies on an underlying gossip mechanism,
and by generalizing the setting in which we cast our algorithms, we are able to give bounds
on the rate at which messages spread through this system.
Alarm-spreading and resource location
Following our discussion above, the inverse-polynomial gossip algorithm provides a "trans-
port mechanism" on which to run a variety of protocols. Perhaps the most basic application
is a simple version of the alarm-spreading example we discussed at the outset. Suppose that
at each point in time, each node u can be in one of two possible states: safe or alarm.
In each time step, u calls another node v according to an underlying gossip algorithm, and
transmits its current state. If u is in the alarm state, then v will also enter the alarm state
when it is called by u. All nodes remain in the alarm state once they enter it. By using the
inverse-polynomial gossip algorithm from Theorem 1.1, we obtain the following guarantee for
this protocol: if x is a node in P , and some node at distance d from x undergoes a transition
to the alarm state at time t, then with high probability x will enter the alarm state by time
A more interesting problem than the simple spreading of an alarm is that of resource
location. As before, we have a set of points P with uniform density. As time passes, nodes
may acquire a copy of a resource. (For example, certain nodes in a sensor network may be
receiving data from an external source; or certain nodes in a cluster of computers may be
running the server component of a client-server application.) At any given time, each node
should know the identity of a resource-holder (approximately) closest to it; we wish to
establish performance guarantees asserting that u will rapidly learn of such a resource.
If at every time step, all nodes forward the names of all resource holders they know about,
then the propagation bounds from Theorem 1.1 immediately imply that nodes will learn of
their closest resource within time O(log 1+# d), where d is the distance to the closest resource.
The disadvantage of this protocol is that the message sizes grow arbitrarily large as more
resources appear in the network.
Resource location: Bounding the message size
Naturally, protocols that require the exchange of very large messages are not of significant
interest for practical purposes. For problems in which there are natural ways of aggregating
information generated at individual nodes, it is reasonable to hope that strong guarantees
can be obtained by protocols that use messages of bounded size (or messages that contain a
bounded number of node names).
We focus on the above resource location problem as a fundamental problem in which to
explore the power of gossip-based protocols that use bounded messages, in conjunction with
the algorithm from Theorem 1.1.
The problem has both a monotone and a non-monotone variant. In the monotone version,
a node never loses its copy of the resource once it becomes a resource-holder. For this version
of the problem, we consider the following simple gossip protocol. Each node u maintains
the identity of the closest resource-holder it knows about. In a given time step, u calls a
node v according to the gossip algorithm from Theorem 1.1 and transmits the identity of
this resource-holder. Finally, the nodes update the closest resource-holders they know about
based on this new information. Note that the protocol only involves transmitting the name
of a single node in each communication step; moreover, u transmits the same value regardless
of the identity of the node it calls.
Despite its simplicity, we can show that this protocol satisfies strong performance guarantees
in the monotone case.
. In one dimension, it has the following property. Let r and u be two nodes at distance
d. If r holds the closest copy of the resource to u during the time interval [t, t # ], and if
then with high probability u will learn about r by time t # .
. In higher dimensions, it has the following approximate guarantee. Again, let r and u be
two nodes at distance d. If r acquires a resources at time t, then with high probability
node u will know of a resource-holder within distance d + o(d) by time t +O(log 1+# d).
In the the non-monotone version of the problem, a node may lose a resource it previously
held. Designing gossip protocols in this case is more di#cult, since they must satisfy both
a positive requirement - that nodes rapidly learn of nearby resources - and a negative
requirement - that nodes rapidly discard names of nodes that no longer hold a resource.
We provide an algorithm for the one-dimensional case, establishing that precise formulations
of the positive and negative requirements can be maintained with a delay that is polynomial
in log d. Weaker versions of the positive and negative requirements, incorporating an
approximation guarantee, can be obtained in higher dimensions.
Definitions
We will present our gossip algorithms and analysis for nodes positioned at points in R D ; for
two such nodes x and y, we define their distance d x,y using any L k metric. Below, we will
discuss how the results can be generalized to other settings.
denote the ball around x of radius d. We say that an (infinite)
set of points P in R D has uniform density, with parameters # 1 and # 2 , if every ball of radius
contains between # 1 d D and # 2 d D points of P . (This includes balls not centered at
points of P .) As stated, our definition only makes sense for infinite point sets. However, we
can easily extend it to finite point sets, and our algorithms and analysis apply to this case
as well with essentially no modifications. For simplicity, however, we will focus on infinite
point sets here.
As we discussed in the introduction, the gossip algorithms we study are designed to
produce "communication histories" with good propagation behavior. A useful model for
stating and proving properties of such communication histories is that of temporal networks
and strictly time-respecting paths in them, proposed in [5, 11] as a means to describe how
information spreads through a network over time. A directed temporal network is a pair
(G, #), where E) is a directed graph (possibly with parallel edges), and
a time-labeling of edges. A strictly time-respecting path from u to v is a path
in G such that #(e i strictly time-respecting u-v paths
are exactly those paths along which information from u can reach v.
For a given run R of a gossip algorithm A, the associated temporal network HR is the
pair ((V, E), #), where V is the set of all nodes in the system, and E contains an edge
labeled only if u called v at time t in R. Note that there
may be an infinite number of parallel copies of the edge (u, v), with di#erent labels -
however, no two parallel copies can have the same label. For a subset V # V of nodes,
and a time interval I, we use HR,V # ,I to denote the temporal network ((V # ,
,I is the communication history of the
run R, restricted to a specific time interval and a specific group of participating nodes.
Throughout, ln denotes the natural logarithm, and ld the base-2 logarithm.
The Gossip Algorithms
We consider gossip algorithms based on inverse-polynomial probability distributions. The
algorithms are parameterized by an exponent # satisfying 1 < # < 2. Let x #= y be two
nodes at distance d = d x,y , and let p (#)
x,y denote the probability that x calls y. Then, we let
x,y := c x (d+1) -D# , i.e. the probability that y is called decreases polynomially in the distance
between x and y. c x is chosen such that
x,y # 1. c x might be the normalizing constant
for the distribution; however, we want to retain the freedom to choose c x smaller, to model
the fact that messages might get lost with constant probability. We make the restriction
that c := inf x c x is strictly greater than 0. We denote the resulting gossip algorithm by A # .
Let us quickly verify that the probability distribution is indeed well-defined at each point
x, i.e. that c x can be chosen strictly greater than 0. Notice that the total probability mass
at point x is at most
z D(1-1 dz < #,
because # > 1 and D > 0.
The main result of this section is a proof of Theorem 1.1, giving poly-logarithmic bounds
on the propagation time of A # when 1 < # < 2. We state the result in the following form.
Theorem 2.1 Fix a # with 1 < # < 2, and define the function fA # ld (d
1))1- ld (#) ld ld (d can be chosen such that for every ball B of diameter d > 1,
every time t, and nodes x, x # B, the temporal network HR,B,[t,t+#f A #(d)) contains a strictly
time-respecting x-x # path with probability at least 1 - ( ld (d
Intuitively, this theorem states that information from any node x can reach any node
x # with high probability within time poly-logarithmic in their distance. Also, it guarantees
that the information stays within a small region containing both x and x # on its way from x
to x # .
The proof is by induction on the distance between the nodes x and x # . We will show that
during a certain time interval I, a node u close to x will call a node u # close to x # , and then
we will use induction to guarantee paths from x to u before I, and from u # to x # after I. The
following definitions formally capture the random events that we are interested in.
For given x and x # , let EH,x,x # denote the event that the temporal network H contains
a strictly time-respecting x-x # path. Let -
E(U, U # , I) be the set of all potentially available
labeled edges from U to U # with labels from the interval I; that is, -
E(U, U # , I) contains one
element for each (u, u # , I is a time. Let # be any total
order on -
E(U, U # , I). Let F H, -
E,e denote the event that e is the smallest edge from -
(with
respect to #) contained in H, and F H, -
E,# the event that H contains no edge from -
that the events F H, -
E,e are disjoint for di#erent e, and F H, -
E,e .
First, we prove a lemma bounding from above the probability
of the event F H, -
E,# .
Lemma 2.2 Let S and S # be sets of size at least #(k
both contained in a ball B k of
radius at most k, and let I be a time interval of length at least 2 D#
E(S, S # , I),
E,# 1/# .
Proof. Any two points u # S and u # S # are at distance at most 2k, so at any time t # I,
with probability at least c u . Hence, for any fixed u # S
and t # I, H contains a u-S # edge labeled t with probability at least c|S # |(2k
As the random choices are independent for all u # S and t # I, the probability Pr[F
that H contains no S-S # edge e with label #(e) # I is at most
The central (inductive) idea explained above is captured in the following Lemma. We
1- ld (#) be the (claimed) exponent in the propagation bound, and define g(k) :=
ld
- 1}. # < 1 is a constant (to be determined only for the proof of
Theorem 2.1), and
ld 1
# .
Lemma 2.3 Let x and x # be at distance k, B k a ball of radius k containing x and x # , and
of length at least #g(k). Let H be the corresponding
temporal network. Then, the probability of the event EH k ,x,x # that there is a strictly time-
respecting x-x # path in H k is at least 1 - #g(k).
Proof. For consists only of one point x, so and as the empty
path is a time-respecting x-x # path, such a path exists with probability
For
- 1# (notice that k # < k), and B and B # balls of radius k # with
E(B,B # , I),
Because s - apply the induction hypothesis to H, and conclude that
B. Using the assumption that t # - t #g(k), we obtain
that
and otherwise,
ld k #/2 ) r
ld
In either case, 2g(k # so we can apply the induction
hypothesis to H # as well, to show that Pr[E H # ,u # ,x # 1 - #g(k # ), for any u # B # .
Whenever there is an edge
E, and strictly time-respecting paths P and P #
from x to u in H and from u # to x # in H # , the concatenated path PeP # is a strictly time-
respecting x-x # path in H k . Because the time-intervals [t, s), [s, s # ) and [s # , t # ) are disjoint,
and all random choices made by A # are independent, the three events EH,x,u , F H k , -
E,e and
are independent for fixed x, x # and Using that the events F H k , -
E,e are
disjoint for distinct e, we obtain that
contain at
least
points. Otherwise, k exactly one
point (x or x # , resp. As #k #/2
we know that k #/2 < 2, so
and
contain at least 1
D#points in either case. Because I has size |I| #
ld 1
# , we can apply Lemma 2.2,
with B,B # , B k , and I, to obtain that Pr[F H k , -
E,#. Using 2g(k (which we
showed above), we now conclude that Pr[E H k ,x,x # 1 - #g(k), completing the proof.
The Theorem now follows quite easily.
Proof of Theorem 2.1. Choose ld
By substituting the definitions of the function g and the constants, we can verify that
#g(d). (In this calculation, we use that which holds because
1.) We can therefore apply the above Lemma 2.3 to x and x # (and thus
with to obtain that with probability at least 1 - #( ld (d ld (d
the temporal network H R, -
contains a strictly time-respecting x-x # path, completing the
proof.
We can get rid of the ld ld (d by increasing the exponent r slightly.
A more general setting
In the proofs of Theorem 2.1 and Lemma 2.3, we only used relatively few properties of
the metric space R D . In fact, we can generalize the results to hold for point sets without
an underlying metric, provided only that we have an appropriate notion of what a "ball"
is. Specifically, let X be a set of points, # and - > 1 two designated constants, and D a
collection of finite subsets of X, called discs, that satisfy the following axioms.
1. For every x # X, there is a disc D # D with x # D.
2. For any two discs D 1 , D 2 , there is a disc D # D 1 # D 2 .
3. If D 1 , D 2 , . are discs with |D i | # b and x # D i for all i, then there exists a disc D
with D i # D for all i, and |D| # - b.
4. If D is a disc with x # D and |D| > 1, then there is a disc D # D with x # D # and
We can think of the collection of discs as serving the role of balls in a metric space with
point set X. With this interpretation, the above axioms are satisfied by point sets of uniform
density in R D , with the constant # chosen to be exponential in D. However, they are also
satisfied by certain other natural metric spaces and set systems, including a version of van
Renesse's Astrolabe system [15] that we discuss below.
For a given disc collection, we can define probabilities p (#) for the inverse polynomial
gossip algorithms A # . For points x, y # X, let b be the minimum cardinality of any disc
containing both x and y. By the first two axioms, such a disc exists, and therefore, b
is well-defined. Now, define p (#)
x,y := c x b -# , where c x is again a normalizing constant at point
x. From the third axiom, we obtain that for any point x, at most #b points y can lie in a disc
D that also contains x and has size |D| # b. Therefore, at most #b points can contribute
b -# or more to the total probability mass at point x.
Hence, the total probability mass
x,y at any point x is at most
#-1 , and in particular finite, so the distribution is well-defined. For
this distribution, we can state the propagation guarantee of A # as follows.
Theorem 2.4 Let 1 < # < 2. Let x, x # X be two points, and D a disc of size b containing
both x and x # . Then, the temporal network HR,D,[t,t+#f A #(b)) contains a strictly time-respecting
x-x # path with probability at least 1 - ( ld (b t.
In other words, x # will learn of information originating at x with a propagation delay
that is poly-logarithmic in the size of the smallest disc containing both of them. The proof
of this Theorem closely follows the proof of Theorem 2.1, and we omit it here.
Other values of the parameter #
It is natural to ask about the behavior of our inverse-polynomial gossip algorithms for different
values of the exponent #. We have found that the set of possible values for # can be
divided into three parts with qualitatively distinct behavior. For # 1, we do not actually
obtain a well-defined probability distribution for infinite point sets; for a finite point set, the
propagation time cannot be bounded as a function of the distance alone (i.e. independent of
the size of the system). For 1 < # < 2, we have the behavior analyzed above; and for # > 2
we prove that the propagation time is at
least# d # ) for an exponent # > 0 depending on #.
This leaves only the "transitional case" turns out to have very interesting
behavior; we are able to prove that for every # > 0, the gossip algorithm A # with
a propagation time that is O(d # ), but do not know whether it has a propagation time that
is polynomial in log d. We note that all these results for varying values of # also hold in
the more general setting of disc collections, with bounds in terms of distances replaced by
bounds in terms of disc sizes.
Astrolabe
Astrolabe is a network resource location service that uses a gossip mechanism for spreading
information [15]; we refer the reader to this paper for more detail than we are able to provide
here. One reasonable model of the structure of an Astrolabe system is as follows: computing
nodes are positioned at the leaves of a uniform-depth rooted tree T of constant internal
node degree; there is an underlying mechanism allowing for point-to-point communication
among these leaf nodes. It is desirable that information originating at a leaf node x should
be propagated more rapidly to leaf nodes that share lower common ancestors with x than
to those that share higher common ancestors.
The gossip mechanism in Astrolabe can be modeled using disc collections as follows: The
underlying point set X is equal to the leaves of the tree T , and there is a disc D corresponding
to the leaves of each rooted subtree of T . It is easy to verify that the four axioms described
above hold for this collection of discs. Hence, if leaf nodes communicate according to the
gossip algorithm in Theorem 2.4, then a piece of information originating at a leaf node x
will spread to all the leaves of a k-node subtree containing x, with high probability, in time
polynomial in log k. For reasons of scalability, the gossip algorithm actually used in the
Astrolabe system is essentially equivalent to A # with so, by the result mentioned
above, information will spread through a k-leaf subtree, with high probability, in time O(k # )
for every # > 0.
3 Resource Location Protocols
In the introduction, we discussed the basic resource location problem. We have nodes in R D
as before; as time passes, nodes may acquire copies of a resource, and we wish for each node
to rapidly learn the identity of a resource-holder (approximately) closest to it. (By abuse of
terminology, we will sometimes interchange the terms "resource-holder" and "resource.")
Our protocols for resource location will rely on an underlying algorithm for gossip on
point sets of uniform density in R D ; we do not make any assumptions about this algorithm
other than versions of the probabilistic propagation guarantee which we proved A # to have
in the previous section. The most basic required guarantee can be expressed as follows:
There is a monotonically non-decreasing time-bound fA (d) such that for any ball
B of diameter d, any two nodes x, x # B, and any time t, the temporal network
HR,B,[t,t+f A (d)) contains a time-respecting path from x to x # with high probability.
This asserts that information from a source x with high probability reaches a destination
"su#ciently fast" via a path not involving any node too far away from either x or x #
(as can be seen by choosing B to be the smallest ball containing both x and x # ). The
nature of the "high probability" guarantee may depend on the algorithm, and will directly
a#ect the guarantees provided by the resource location protocol. In the preceding section,
we established that this guarantee holds for inverse polynomial distributions with exponents
# (1, 2), with fA (d) # O(# log 1+# d), giving us high probability guarantee 1-( ld (d+1)) -# .
Monotone Resource Location
We begin by considering the monotone case, in which any node that is a resource-holder at
time t is a resource-holder for all t # t. Our protocol should guarantee that within "short
time", a node learns of its closest resource (once it becomes available), and subsequently
will never believe any resource further away to be its closest resource. An approximation
guarantee would be to require that a node learns of a resource that is "not too much further"
away from it than its closest resource.
A simple protocol for the line
If resources never disappear, and all points lie on a line (i.e. the dimension is
very simple protocol will ensure that each node learns of its closest resource "quickly" (as
quantified by fA (d)), with high probability.
The protocol is as follows: Each node x locally maintains the node N x (t), the closest
node which x knows to hold a copy of the resource at time t. Initially, at time
is set to a null state #. When a resource appears at a node x at time t, N x
all t # t. In each round t, each node x selects a communication partner according to the
algorithm A, and sends the value N x (t). Let M t be the set of all messages that x received
in a round t. Then, it updates N x to be the closest node in M t # {N x (t)} (ties broken
in favor of N x (t), and otherwise arbitrarily).
For the line, we can prove the following strong guarantee about the performance of this
protocol:
Theorem 3.1 Let x be any node, and xR a resource at distance d = d x,x R . Let t
#fA (d), and assume that xR was the (unique) closest resource to x throughout the interval
Proof. For the proof, let B be the smallest interval containing both xR and x, and consider
the temporal network (G, #) = HR,B,[t,t # ) . The guarantee of the underlying algorithm A states
that with high probability, (G, #) contains a time-respecting path from xR to x. Let
x be the vertices on any such time-respecting path, and e
(v k-1 , v k ) its edges with time labels t be the message that was sent from v i
to v i+1 at time t i .
By induction, we will establish that x this is clearly true. For the
inductive step from i to consider the message x i received by v i+1 at time t i , and the
message x i+1 sent by v i+1 at time t i+1 . Because v i+1 lies in the smallest interval containing
xR and x, v i+1 lies on a shortest path from xR to x. Therefore, xR being the closest resource
to x throughout [t, t # ] implies that it is also the closest resource to v i+1 . By the choices of the
protocol and the induction hypothesis, N v as xR is still the closest resource
to v i+1 at time t i+1 , we obtain x
receives the message x is the
closest resource to x from time t k-1 until t # , so N x
Analysis of the protocol in higher dimensions
In higher dimensions, this simple protocol may not inform nodes of their truly closest resource
as quickly as #fA (d). Intuitively, we want the message about a node xR with a resource to
quickly reach every node x such that xR is the closest resource to x. That is, we are interested
in "filling in" the Voronoi region of the node xR . However, if the Voronoi region is very long
and narrow, most calls made by nodes inside the region will be to nodes outside the region.
Hence, the time depends on the angles of the corners of the Voronoi region.
If we wish to make guarantees avoiding such specific properties of the actual distribution
of resources, we can obtain an approximation guarantee by slightly strengthening the
requirement on the algorithm A. Our stronger requirement will be that not only is there
a strictly time-respecting path, but its total "length" is bounded by some function of the
distance d under consideration. Intuitively, this means that messages with high probability
do not take very long "detours" on their way from a source to a destination.
More formally, for a path P with vertices its path distance be d(P
Then, we can state the requirement as:
There is a time-bound fA (d) and a length function # A (d) such that for any ball B
of diameter d, any two nodes x, x # B, and any time t, HR,B,[t,t+#f A (d)) contains
a time-respecting path P from x to x # of path distance d(P ) # A (d), with high
probability.
Below, we prove that the algorithms A # with # (1, 2) satisfy this property with # A
We can now state the approximation guarantee of the resource location protocol that we
previously analyzed for line:
Theorem 3.2 Let x be any node, and xR a resource at distance d = d x,x R
. Let t
#fA (d), and x # with probability at least 1 - ( ld (d
Hence, for su#ciently large d, the inverse polynomial gossip algorithms A # will guarantee
o(1))-approximation to the closest resource within poly-logarithmic time, with high
probability.
Proof. Let B be any smallest ball containing both xR and x, and consider the temporal
network (G, #) = HR,B,[t,t # ) . With high probability, this network contains a strictly time-
respecting xR -x path P of path distance d(P x be the
vertices of this path, e the message sent
from v i to v i+1 at time t i .
We prove by induction that for all i, d v i ,x i # i-1
. Clearly, this holds for
since x . For the step from i to . The protocol then
ensures d v i+1 ,x i+1
. By the triangle inequality,
applying the induction hypothesis to i yields that
Using the behavior of the protocol at node x we know that
completing the proof.
By taking a closer look at the analysis in the proof of Theorem 2.1, we can show that the
algorithms A # (for 1 < # < 2) have the claimed property of short paths with # A #
Lemma 3.3 Let B be a ball with diameter d, t an arbitrary time, and t
Then, with probability at least 1 - ( ld (d the temporal network (G, #) = HR,B,[t,t # )
contains a strictly time-respecting path -
P from x to x # of path distance at most d + o(d) for
any two nodes x, x # B.
Proof. The path -
constructed in the proof of Theorem 2.1 consists of one "jump" edge
of length at most d, and two subpaths P and P # which lie inside balls B and B # of diameter
at most #d #/2
- 1# d #/2 , and are of the same form. Hence, we obtain the recurrence
Using standard substitution techniques (and writing ld ld d
ld # ),
we find that this recurrence has the solution
We can bound this from above by splitting o# the last term n) of the sum, and bounding
all other terms from above by 2 n+( 2
, obtaining that # A # (d) # d ld d) 1
1- ld (#) ld ld d
ld # - d #/2 ,
which is bounded by d + o(d), as claimed.
There is an alternate way to obtain approximation guarantees for resource location in
higher dimensions, without strengthening the assumptions on the underlying gossip algo-
rithm. This is done by having nodes send larger messages in each time step.
For a scaling parameter # > 1, a node x at time t stores the identity of the closest
resource-holder xR , and a set R x (t) consisting of all resource-holders x # R that x has heard
about whose distance to x is at most # - d x,x R
. In each time step, nodes communicate their
sets R x (t), and then update them based on any new information they receive.
Here is a more precise description of the protocol: The local state of any node x consists
of a set R x (t) of nodes which x knows to hold a copy of the resource at time t. Initially,
R x #, and whenever a resource appears at a node x at time t, x # R x t.
In each round t, each node x selects a communication partner according to the algorithm
A, and sends the entire set R x (t). Let M t be the set of all gossip messages that x received
in a round t, and
m) # R x (t) the set of all resources about which x knows at
time t. Let i.e. to be
the set of all nodes no more than # times as far away from x as the nearest resource.
The sets R x (t) sent and locally stored could potentially be large, but if we believe the
resources to be spaced relatively evenly, the local storage and messages should only contain a
constant number of nodes (for constant #). This protocol yields the following approximation
guarantee:
Theorem 3.4 Let x be any node, and xR a resource at distance d = d x,x R
. Let t
#fA (d), and x # R be a node in R x distance to x (among all nodes in R x
#-1 )d with high probability.
Hence, this Theorem shows how we can smoothly trade o# message size against better
approximation guarantees. Notice that the runtime of the gossip protocol is not directly
a#ected by the desired better guarantees (only via the larger message size).
Proof. Let B be a smallest ball containing both x and xR . Consider the temporal network
(G, high probability, this network contains a strictly time-respecting
path P from xR to x. Let v 1 , . , v k be the vertices of this path, e its edges with
labels the message sent from v i to v i+1 at time t i .
We prove by induction that for all contains a resource at distance at most
#-1 )d from x. With clearly imply the theorem.
The claim holds for d. For the step from i to
let x i be the node in m closest to v i , and consider two cases:
1. If x
then the claim holds for held for i by
hypothesis.
2. If x i /
must contain a node x i+1 such that d v i+1 ,x i
(otherwise, v i+1 would have retained x i ). By the triangle inequality, d v
and using the induction hypothesis to bound the distance between x and x i , we get
)d
d,
so d x,x
Non-Monotone Resource Location
The situation becomes more complex if resources may disappear over time. In that case,
information about the disappearance needs to propagate through the system as well, to
ensure that nodes do not store outdated information. However, we do not want to send
messages for every disappearing resource, since this would again increase the size of messages
too much.
Rather, we use a time-out scheme to ensure that nodes find out about the disappearance
of resources implicitly. That is to say, when a node x has not heard about its closest resource
xR for a su#ciently long time, x concludes that xR is no longer a resource-holder; x stops
sending information about xR , and becomes receptive to learning about new resources even
if they are further away than the one previously considered closest. To implement the timing
mechanism that we referred to above, we will assume that each node has access to the global
time t.
Of course, it is crucial to state what the time-out function h (-) should be. We still want
nodes to find out about their (approximately) closest resources in time depending solely on
their distance from the resource. However, we now also want to require that nodes find out
about the disappearance of their closest resource within similar time bounds, in particular
in time depending only poly-logarithmically on their distance from the resource. That is,
h (-) should be a function of the distance d, but not the size of the underlying node set.
In view of this requirement, the existence of time-respecting paths might not be su#cient
to ensure that information about a resource actually reaches the desired destination. We
have not imposed any bounds on the amount of time that may lie between the labels of two
adjacent edges of the path (i.e. the time information spends at one node), and if this time
is too long, the node may "time out" on the resource, i.e. decide that it does not hold a
resource any more. We therefore want to require the existence of "time-out free" paths.
For a time-respecting path
from node i < k is #(v time-respecting path P is called
respect to a time-out function h (d)) if #(v i
on the path.
We let TH k ,x,x # denote the event that the temporal network H k contains a
path. Now, the requirement on the underlying protocol can be stated as follows (where we
1- ld (#) , as before):
There is a non-decreasing time-out function h (d) such that for any ball B of diameter
d, any two nodes x, x # B and time t, the temporal network HR,B,[t,t+#h(d))
contains a time-out free, strictly time-respecting path from x to x # with probability
at least 1
ld (d
ld (d
Below, we will show that the inverse polynomial gossip algorithms A # satisfy this property
with time-out function h First, however, we will see how we can exploit
this property to build a protocol for the non-monotone resource location problem.
Notice that if h # (d) # h (d) for all d, then a path that is time-out free with respect to
h (-) is also time-out free with respect to h # (-). We can therefore always choose the time-out
function larger, without decreasing the probability. We will use this fact to design a protocol
with high-probability guarantees, even though the above guarantee is only low-probability
in itself.
The local state S x (t) of a node x at time t is either the set {#xR , #} consisting of a single
time-stamped message containing the name of some node xR and the time-stamp # , or the
empty set #. If S x then xR is x's current estimate of the closest resource-
holder; we will say that x believes in xR at time t. We say that a node x times out on xR at
time t if x believes in xR at time t, and x does not believe in xR at time t+1. Using the time-out
function h (-), we define the time-out function h #
ld (d ld ld (d
for the protocol, where # is again a measure of the desired probability guarantee.
Each node executes the following protocol:
. If x holds a copy of the resource at time t, then its local state is set to S x (t) := {#x, t#}.
. Otherwise, let M t be the set of all messages received at time t - 1, plus the previous
state S x (t-1). If M t contains a message #x # with t-# h # (d x,x # ), let -
x be such that
x minimizes d x,x # among all such messages. Then, let - # be maximal such
that #-x, - # M t , and set S x (t) := {#-x, - #}. If M t contains no such message #x #, set
. Send S x (t) to a node y chosen according to A.
We will show that on the line, this protocol ensures that nodes learn quickly about both
appearance and disappearance of their closest resource, in the following sense.
Theorem 3.5 Let t be an arbitrary time, x and xR nodes at distance d = d x,x R
and
(1) If xR did not hold a copy of the resource during any of the interval [t, t # ], then x does
not believe in xR at time t # .
(2) If xR has held the copy of the resource uniquely closest to x throughout the interval
[t, t # ], then x believes in xR at time t # with probability at least 1 - ( ld (d
In terms of the analysis of systems, the negative (first) condition corresponds to safety,
i.e. ensuring that wrong or outdated information will not be held for too long, while the
positive (second) condition corresponds to liveness, i.e. ensuring that information will eventually
reach any node. Notice that the safety guarantee is in fact deterministic, while the
liveness guarantee is probabilistic.
Proof. Property (1) follows directly. If xR was not a resource-holder during any of the
interval [t, t # ], then no messages #xR , # for # [t, t # ] were generated, so no such message can
have reached x.
The remainder of the proof is concerned with Property (2). Let B be the smallest interval
containing x and xR , and t is the original time-out function, and
j ranges from 0 to # - ( 1
ld (d ld ld (d 1). Now, fix one such j, and the associated
interval
By assumption on A, there is a time-out free xR -x path
and in the temporal network HR,B,I with probability at least 1
ld (d
1- ld (#) .
Let us suppose that such a time-out free path does exist. Let e
message sent along e i at time #(e i ). We will show by induction that m
In the base case this is obvious, since xR was assumed to hold a resource at time
I. For the inductive step from i to i + 1, we know by induction hypothesis that
There could be two "obstacles" to v i+1 sending a
message m i+1 of the same form: (1) messages about other resources closer to v i+1 than xR ,
and (2) v i+1 timing out on xR at some time s #(v i ), #(v
For (1), notice that we assumed xR to be the unique closest resource to x throughout I.
As v i+1 lies on a shortest xR -x path (here, it is crucial that the points are on the line), xR is
also closest to v i+1 throughout I. Hence, we can apply the safety property (1) proved above
to obtain that at no time s # I, v i+1 believes in any x # closer to v i+1 than xR .
For (2), recall that P is a time-out free path, and therefore satisfies s
In the protocol, message m i is therefore always available
as a candidate for the next state of v i+1 , and since we argued above that no messages for x #
closer than xR are available, the next state is of the form #xR , # (where # ). Hence,
message m i+1 is actually of the form #xR , # with #(xR ).
Applying this to v we obtain that at time t j+1 , node x believes in xR . The time-out
function h # (-) is so large that for any s # [t # , t # ], node x cannot time out on xR if it ever
received a message from xR with a time-stamp # t # . That is, if there is a time-out free,
strictly time-respecting xR -x path in the temporal network HR,B,[t j ,t j+1 ) for any j, then x
believes in xR at time t # . Because the intervals [t j , t j+1 ) are disjoint for di#erent j, and all
random choices made during the protocol are independent, the probability that none of the
intervals contain a time-out free path is at most
ld (d
ld (d+1)) r ld ld (d+1)
ld (d+1)) -r #( 1
ld (d+1)) r ld ld (d+1)
ld (d
completing the proof.
In higher dimensions, we can obtain similar approximation bounds to the ones in the
monotone case, by requiring that no resources within distance d + o(d) of x disappear in
the time interval under consideration, where d is again the distance of node x to its closest
resource. The proof is a direct combination of the proofs of Theorems 3.5 and 3.2, and
therefore omitted here.
In the remainder of this section, we argue that the inverse polynomial gossip algorithms
A # from the Section 2 actually satisfy the above property of producing time-out free paths,
with time-out function h ld 1+#
1)). Hence, the protocol for non-monotone
resource location presented above will have time-out function and dissemination time bound
O( ld 2+#
As in Section 2, we define the constants
c# 2 . If we
restrict our attention to balls B of diameter at most 64, and make the allowed time interval
su#ciently large, we can ensure that there will be a time-respecting x-x # path within B with
probability at least 1
2 . If nothing else, x calls x # with constant non-zero probability in every
round, and the one edge induced by this call is a time-respecting and time-out free path. By
making enough independent trials, the probability that one will succeed (and x will call x # )
will become at least 1
2 . Let # such that for any x and x # at distance at most 64, x will call x #
within # rounds with probability at least 1. Let g(k) := (4#)( ld ld ld
and define h
# as our time-out function. Notice that h (d) #
O( ld r
ld ld (d
Lemma 3.6 Let x and x # be at distance k, B k a ball of diameter k containing x and x # , and
with probability at least 1
ld the temporal network
contains a time-out free x-x # path (with respect to h (-)), i.e. Pr[TH k ,x,x #2 min{1, ld
Proof. The proof is by induction, and similar to the proof of Lemma 2.3. For the base
case, we consider k # 64. We claim that the temporal network H k contains a time-out free
x-x # path with probability at least 1
ld In the case
follows because x and x # must be identical, and the empty path is a time-out free x-x path
that exists with probability 1. If k # 1, then g(k) #, so there is an edge (x, x # ) with
probability at least 1
.
For the case k > 64, we define k
similar to before - notice that k - 1 # k #
7. We divide the time interval [t, t # ] into three parts [t, s), [s, s # ) and [s # , t # ), by
setting ld ld is a
ball of radius k # containing x # .
In the proof of Lemma 2.3, we argued that there was a node u close to x calling a node u #
close to x # during the interval I. Now, we have to ensure in addition that the time-respecting
path does not time out at u. As we do not know when the call from u to u # happens, we
might have to deal with paths that "wait" at node u for all of I. If u can be arbitrarily close
to x, such a wait would certainly result in a time-out, so we want to make sure that u is
su#ciently far away from x.
We choose k # 1
. as the lower bound on the distance from x to u. With
denoting a ball of radius k # containing x, we set
that
as was shown in the proof of Lemma 2.3. Finally, we define, as before, -
E(B,B # , I), and
Because s - apply the induction hypothesis to H, and find that
ld
ld
ld
ld
for any u # B.
We want to concatenate P with a time-respecting path P # from u # B # to x # . This path
need not be time-out free in itself, because all of its nodes will be su#ciently far away
from x, and hence not time out during the interval [s # , t # ). That is, we can simply invoke
Theorem 2.1 for the existence of the path once we have ensured that the interval [s # , t # ) is long
enough. To bound from below the length of the time interval [s # , t # ), we use the definitions
of t # , s # , k # and g, to obtain that
ld ld
ld ld
ld ld ld
ld ld ld
ld ld ld
In the second and fifth step, we used ld ld ld ld ld ld
ld ld
2 . In the third step, we simply dropped the #
in the fourth step, we used that ( ld
ld just showed that
ld ld ld so by Theorem 2.1, we obtain that with probability
at least 1 - ld there is a strictly time-respecting (but not necessarily time-out
path P # in H # for any u # . By substituting y = 3, and verifying that the
y -3 is monotonically increasing for y # 3, we see that y -3 # 1
all y # 3. Then, we can substitute ld
ld and obtain that
ld
ld ld Therefore,
ld ld
ld ld
Assume that there is an edge
E, a time-out free x-u path P in H, and a
strictly time-respecting u # -x # path P # in H # . We want to verify that the concatenated path
PeP # is time-out free as well. For the subpath P , this follows from the induction hypothesis.
Node u and all nodes on the path P # are at distance at least k # from x. For all these nodes
the departure time is at most t # , whereas the departure time from node x is at
least t. Therefore, we obtain that
so PeP # is time-out free as well.
We thus know that for any edge
E, the event F H k , -
E,e #TH,x,u #EH # ,u # ,x # implies
the existence of a time-out free x-x # path, i.e. the event TH k ,x,x # . By the same argument as
before, the three events F H k , -
E,e , TH,x,u and EH # ,u # ,x # are independent for any fixed x, x # and
Using again that the events F H k , -
E,e are disjoint for distinct e, we obtain
that
ld
E,e ]-
ld ld
ld
ld ld
ld ld
Because the length of the interval I is ld ld
ld
obtain from Lemma 2.2, applied to B,B # , B k , and I, that Pr[F
ld
therefore
ld completing the proof.



--R

"Epidemic algorithms in replicated databases,"
"Bimodal multicast,"
"Epidemic algorithms for replicated database maintenance,"
"Next century challenges: Scalable coordination in sensor networks,"
"Label-connected graphs and the gossip problem,"
"Scalable Fault-tolerant Aggregation in Large Process Groups,"
"A survey of gossiping and broadcasting in communication networks,"
"Adaptive protocols for information dissemination in wireless sensor networks,"

"Randomized rumor spreading,"
"Connectivity and Inference Problems for Temporal Networks,"
"A scalable location service for geographic ad hoc routing,"
"Gossip versus deterministic flooding: Low message overhead and high reliability for broadcasting on small networks,"
"On spreading a rumor,"
"Scalable and secure resource location,"
"A gossip-style failure-detection service,"
--TR

--CTR
Bogdan S. Chlebus , Dariusz R. Kowalski, Robust gossiping with an application to consensus, Journal of Computer and System Sciences, v.72 n.8, p.1262-1281, December, 2006
resource location;decentralized algorithm;gossip