3
of the infinite random graphs G constructed as above, if
GOSSIP1(p,0) is used by every node to spread a message,
then there is a probability θ
0
(p) < 1 such that the mes-
sage reaches infinitely many nodes is θ
0
(p). Moreover,
the probability that a node receives the message and for-
wards it in an execution where the message reaches in-
finitely many nodes is also θ
0
(p).
Note that the probability of a message dying out (i.e.,
not spreading to infinitely many nodes) is taken over the
executions of the algorithm. That is, the theorem says that
if we execute the algorithm repeatedly, the probability that
a message does not die out in any given execution is θ
0
(p).
On the other hand, the second θ
0
(p) talks about the prob-
ability that a node receives and forwards the message in a
given execution of the algorithm. The intuition behind the
equality of the above two probabilities is easy to explain.
A gossip initiated by a source n
0
dies out if there is a set
of nodes N that disconnects n
0
from the rest of the graph;
that is, every infinite path starting at n
0
must go through
a node in N . Thus, θ
0
(p) is the probability that there is
no disconnecting set N such that none of the nodes in N
forward the message. (Note that N could consist of the
singleton node n
0
itself.) Similarly, the probability that a
random node n does not receive and forward the message
is precisely the probability that there is a set N
′
such that
N
′
disconnects n from n
0
and none of the nodes in N
′
for-
wards the message. In a regular graph or a random graph
of the type considered here, these probabilities are clearly
the same.
It follows from these results that, in an execution where
the message does not die out, the probability that a random
node receives the message is θ
0
(p)/p, since receiving the
message is independent of forwarding it. Thus, in terms of
the notation used in the introduction, θ
S
(p) = θ
0
(p) and
θ
R
(p) = θ
0
(p)/p.
Let θ
S
k
(p) be the probability that a message reaches
infinitely many nodes if GOSSIP1(p, k) is used. It is
easy to see that θ
S
1
(p) = θ
0
(p)/p, since the probabil-
ity that the message reaches infinitely many nodes using
GOSSIP1(p, 1) is precisely the probability that a message
reaches infinitely many nodes using GOSSIP1(p, 0) given
that the source actually gossips. However, note that the
probability that a node receives and forwards a message
if GOSSIP1(p, k) is used, given that the message does not
die out, is still θ
0
(p). That is, the probability that a node
receives the message is independent of the choice of k. On
the other hand, it is not hard to see that if each node learns
the network topology in a zone of radius k (so that it can
route a message directly to any node in its zone), then the
probability that a node receives and forwards a message
given that the message does not die out is θ
k
(p).
All these results are for infinite graphs. It is not hard
to show that essentially the same results hold for finite
graphs, except possibly near the boundary. In sufficiently
large finite graphs, there will be two types of executions:
those where hardly any node gets the message, and those
where the message makes it all the way to the boundary.
It follows easily from the Central Limit Theorem that, in
sufficiently large graphs, in almost all executions where
the gossip does not die out, a fraction θ
0
(p)/p nodes will
get the message. That is, we expect the bimodal behav-
ior: either hardly any nodes get the message, or a fraction
θ
0
(p)/p receive the message. As we shall see, in cases of
interest, θ
0
(p) is quite close to p. Thus, in almost all exe-
cutions of the algorithm in sufficiently large graphs, either
hardly any nodes receive the message, or most do.
This leads to a number of obvious questions:
• How large is “sufficiently large”?
• What is the behavior of θ
k
(p) for different graphs of in-
terest?
• What can be done to improve the performance of gos-
siping in realistic settings?
We investigate these questions in the next two sections.
III. GOSSIPING IN FINITE NETWORKS
We did a number of experiments to investigate the be-
havior of gossiping. We summarize some of the more in-
teresting results here. We assumed an ideal MAC layer for
these experiments because we wanted to decouple the ef-
fect of the MAC layer from the effect of gossiping. (When
we consider more realistic scenarios in Section V, we use
the IEEE 802.11 MAC layer.) We first study regular net-
works, since they allow us to easily analyze how GOSSIP1
behaves with respect to different parameters, such as the
gossip probability, network size, and node degree, without
other complicating factors. As we shall see, the behavior
in regular graphs seems quite indicative of the behavior
of gossiping in general. We then study random networks
constructed as follows: Nodes are placed at random on a
two-dimensional area; an edge is placed between any pair
of nodes less than a fixed distance d apart. This type of
random graph seems appropriate for modeling a number
of applications involving ad hoc networks. Nodes have a
limited amount of power, and so can communicate only
with reasonably close nodes. The random placement can
be viewed as modeling features such as the random mo-
bility of nodes and the random placement of sensors in a
large region.
Our first set of experiments involves “medium-sized”
networks, with 1000 nodes. We start by considering a
20×50 grid (i.e., a regular graph of degree 4). We focus on
GOSSIP1(p, 4), since taking k = 4 produces a reasonable
剩余11页未读，继续阅读
gu1013
- 粉丝: 0
- 资源: 3
我的内容管理
展开
最新资源
- 李兴华Java基础教程：从入门到精通
- U盘与硬盘启动安装教程：从菜鸟到专家
- C++面试宝典：动态内存管理与继承解析
- C++ STL源码深度解析：专家级剖析与关键技术
- C/C++调用DOS命令实战指南
- 神经网络补偿的多传感器航迹融合技术
- GIS中的大地坐标系与椭球体解析
- 海思Hi3515 H.264编解码处理器用户手册
- Oracle基础练习题与解答
- 谷歌地球3D建筑筛选新流程详解
- CFO与CIO携手：数据管理与企业增值的战略
- Eclipse IDE基础教程：从入门到精通
- Shell脚本专家宝典：全面学习与资源指南
- Tomcat安装指南：附带JDK配置步骤
- NA3003A电子水准仪数据格式解析与转换研究
- 自动化专业英语词汇精华：必备术语集锦
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
