通过利用社交网络原则达到可预测的Gossip传播
abstract
Gossip协议提供了概率性的可靠和扩展，但它们固有的随机性可能导致不同节点接收到的消息数量差异很大。这篇论文提出了技术它利用了社交网络原则允许节点智能的选择gossip目标。本文中提出的简单的启发式方法在每个节点上实现了更统一的消息开销，降低整个系统的gossip流量，同事减少Gossip的延迟（高达25%）。通过比较我们的JetStream系统，对于传统的gossip和在chord覆盖下gossip的违反。直觉上，JetStream让gossip传播更符合直觉和可预测，同时保持内在的扩展性和可靠性。JetStream也提供了额外的好处，通过减少网络带宽利用和gossip注入的持续率。
介绍
RSS和ATOM等Web 提要的出现，以及流式网络连接，使得大组多播成为一个重要的问题。大规模的多播设计包括了FeedTree[17]BitTorrent [7], Bullet [12]。然而我们相信，我们相信gossip提供了概率性可扩展和可靠性的正确组合来解决这些新问题。一个主要的限制在gossip协议中是固有的随机型。随机选择的gossip目标位于不同的节点导致了高的多变的传入消息开销 - 一些节点可能接受30次副本来源于同一个gossip消息，同时其他节点只接受少数的（这个更可取）。我们需要智能的策略来进行gossip目标选择来减少在可预测方式中的随机开销。同时，我们也想要随机gossip继承的可靠性和拓展性。
这篇论文提出了JetStream，一个使用社交网络原则的gossip协议来达到智能gossip目标选择。我们想要向读者澄清这篇论文不利用社交网络连接（即来自社交网络系统列斯Orkut等）来提高蔓延。相反我们借用纯社交网络想法来开发JetStream。出奇的，简单的社交网络启发和gossip相结合导致了更统一的消息负载，减少了gossip延伸的延迟，和更低的系统范围流量。
互惠性和是网络双方向交换帮助或资源。这种互惠的关系有助于简历信任和合作
结构洞指，网络中某些个群体之间缺乏直接联系，形成空洞。占据这个位置能连接不同的群体获得更多的信息
俩个社交网络原则，互惠性（Reciprocity）和结构洞（structural Holes）被用在JetStream。俩者都是在人类发展社会关系时（无意识的）使用的。互惠理论指出，个人更倾向于回报它人感情。结构洞理论指出，个人倾向于建立关系来最大化他们的连接。
我们在经验上比较JetStream的性能和传统的随机gossip，以及在Chord覆盖上传播的gossip。我们的经验展示了JetStream更低的消息开销在自身节点上。将gossip的延迟减少了25%，将总的gossip流量减半。我们希望指出本文没有提出拓扑感知的gossip，适应性gossip，或者语义gossip算法。尽管社交网络规则可以添加到这个机制中，但是它们超出了本文的范围。
本文的其他组织如下：我们将在第2节讨论八卦协议的基本性质。在第3节中，我们介绍了互易理论和结构洞的数学启发式。第4节讨论了我们的算法和实现。我们在第5节中提供了仿真结果。最后，第六部分总结。
双峰组播（Bimodal Multicast） 是一种结合了 可靠组播（Reliable Multicast） 和 Gossip 协议 的混合通信机制，旨在提高大规模分布式系统中的消息传递可靠性和可扩展性。它通过两种不同的模式（双峰）来确保消息的可靠传递。
可靠组播阶段：
- 发送者通过可靠组播协议将消息发送给所有接收者。
- 接收者收到消息后，发送确认（ACK）给发送者。
- 如果发送者未收到某个接收者的确认，会进行重传。
Gossip 阶段：
- 在可靠组播的基础上，引入 Gossip 协议。
- 接收者随机选择其他接收者交换消息，确保未收到消息的节点最终能通过 Gossip 协议获取消息。
- 这种方式弥补了可靠组播在高负载或网络不稳定时可能出现的确认丢失问题。
相关工作：大量的工作扩展可靠的多播（SRM[9]）最近为RSS提要开发了几个发布订阅系统（即FeedTree），和其他的连接 即Bullet[12]。文献中提出了几个扁平的规范，gossip协议包括双峰组播Kermarrec等人的工作包括Bimodal Multicast [4]、Kermarrec等人的工作 [11]、Kouznetsov等人的工作 [13] 等。这些Gossip协议的变体，如拓扑感知（例如 [10]）或语义感知（例如 [16]）的版本，也已被提出。Gossip已被用于设计多种分布式协议，例如成员机制，如 [8] 和 [19]。
在将社会网络原理与点对点系统相结合方面已经做了一些工作。然而这一领域的工作没有明确的从社交网络中汲取数学思想。Bernstein[2]提出了一种更号的对全局资源选择的对等体策略。Marti等[14]提出了DHT利用了朋友的朋友社交与着呢来增强同班之间的信任。
Monge 和Contractor [15] 以及Wasserman et al [20]是俩个主要的资源，它们使用数学结构描述了多样的社交网络原则。
2 gossip网络
在这一章节中，我们描述了扁平的gossip协议，以及通过模拟实验来刻画它。我们的网络模型为n个固定的节点（通过$v_0-v_{n-1}$）来表示，每个节点$v_i$可能会和其他的任意的$v_j$节点进行交流。在俩个节点发送消息的代价是统一的。
2.1 扁平化的gossip
在网络中简单的gossip协议可能被用来传播消息（例如，发布订阅系统更新）。最简答的gossip （叫做flat gossip）如下：由消息创始人开始，每个节点选择c个随机转发目标（统一从网络成员列表中获取）在每个时间间隔m内发送一条消息。节点收到最初的消息后，以d个时间间隔重复此过程。一个相对便宜的优化是，如果节点$v_i$已经收到了消息m，节点$v_i$不再发送消息给节点$v_j$（即 如果节点$v_j$由之前从转发消息到过消息给$v_i$）
之前的研究已经展示了gossip协议$c\times d=O(logn)$允许消息以非常高的概率传播到所有节点。确切的说如果每个节点转发消息到log n+k个节点，那恶魔那么所有节点收到消息的概率收敛于$e^{-e^{-k}}$.
2.2 覆盖网络
在俩个节点$v_i$和$v_j$之间建立初始连接的成本通常不为0。因此，选择相同的目标候选对于gossip消息是有好处的。这样做可以将连接建立的成本分摊到许多消息上。换句话说，一个节点和它的目标集合保持连接。这些总的连接形成了一个覆盖网络。
随机覆盖网络的性质：一种覆盖，其中每个节点都有一个目标大小集$l=O(logn)$（从其他所有n-1个节点中随机的选择）有一个有趣的特性：如图1(a)所示，在大小n为1000的网络中，节点入度的分布（即，选择某个节点作为转发目标节点数 ）服从二项分布。
图1：随机覆盖有不平衡的入度分布，导致了不平衡的gossip工作量。
节点中入度的变化导致了在gossip协议中部平衡的工作负载。图1(b)显示节点的度与接收到的消息总数之间存在紧密的线性相关关系。在大小为n=1000的网络中，目标集l=16。因此提高公平度分布可以降低网络的变化。
为了提升工作负载的分布和传播速度。我们使用社交网络原则。基础在下一章节讨论。
社交网络
大量的社交网络理论试图解释关系背后的逻辑。在这一章节，我们关注与俩个理论通过特定的目标选择来提升gossip协议的性能。
3.1 互惠
社会交换理论解释了二元互动的基础上，每个行动者必须提供的资源。互惠理论指出社会网络成员之间相互互动倾向会更高。直观上，互惠性改善了程度分分布，减少了平面gossip传播的消息总数。如果每个节点与其转发目标具有互惠关系，每个节点的入度完全等于出度l。此外，gossip中节点不需要转发消息它已经接收到消息的及节点。从本质上讲，这讲让消息数量减少一半。节点$v_i$可用的值（基于互惠）可以被计算如下
$$ Utility_{Reciprocity}(v_i)=\sum_{j=0}^{n-1}x_{ij}x_{ji}（1） $$
变量$x_{ij}$是一个boolean值代表当前在$v_i,v_j$节点之间的关系。节点的效用值（仅）对每个互惠关系有所提高。为了增强互惠，我们目标是最大化所有节点的效用值
3.2 结构洞
一个有趣的基于自我兴趣的社交理论是结构洞理论。结构洞理论认识到，在社会网络中企业家或创业者积极地在社交网络中将自己定位在有利的位置。
结构洞是一个网络中的位置，它提供了网络成员的直接优势。结构洞中一个行为体连接俩个不想连的行为体。在竞争激烈的世界中，填补这个洞的个体让他们从位置中获取优势，通过从他们联系人哪里收集更多高质量的信息，以及通过对它们施加更大的控制。
节点$v_i$的效用值（根据结构洞理论的规定）可以计算如下
$$ Utility_{Str.Holes}(v_i)=\sum_{j=0}^{n-1}x_{ij}\sum_{j=0}^{n-1}x_{ji}(1-x_{jk})（2） $$
只有当一个节点与彼此没有关系的节点建立关系时，它的效用值才会提高。基于结构孔理论改变转发目标的节点可以提高八卦消息的传播速度。
4 JetStream 方法
在网络中效用函数用语量化用户从交互互动中获得的收益或者满意度，它帮助分析用户行为、决策以及网络结构影响。
折扣重复是一种在信息传播或社交网络中分析的常用策略、推荐系统或社交网络分析中的常用策略，目的是减少重复信息对用户的影响。其核心思想是，随着相同或类似信息的重复出现，用户对其的注意力或兴趣会逐渐降低。
JetStream算法目的是提高节点的利用。每个节点目标集严格的基于效用函数的本地评估而不考虑决策对系统健康的影响（全局效用）。我们的经验是找到谈心行为让系统收敛到全局最优配置：
效用函数：我们的直觉是，上述的俩中理论（互惠[5]和结构洞[6]）应该会提高gossip网络的性能。我们通过结合互惠和结构洞的效用函数来导出节点$v_i$的效用函数如下。
$$ Utility(v_i)=\sum_{j=0}^{n-1}x_{ij}x_{ji}\sum_{j=0}^{n-1}x_{ik}x_{ki}(1-x_{jk})(1-x_{kj})（3） $$
给定l作为goosip的目标数量，最大可达到的效用值是$\frac{l\times(l-1)}{2}$（折扣重复）。达到最大效用的及诶单被称为最优节点，其他节点被标记为次优节点。
效用函数可以在部队目标施压硬约束和、或确定性规则集的情况下素造覆盖。例如，当且仅当$v_j$不是对于任何$v_i$的其他目标的目标。而这样确定性的规则允许节点迭代低构造它们的目标集- 一个新加入的节点可能无法快速构建目标集。使用效用函数，一个新的节点可能只是随机选择它初始目标集，然后逐渐改变它的目标集合。
通用算法详细信息：在任何给定时间内，每个节点维护成员关系列表（已知存在于网络中的节点组成的），除了gossip目标集。我们的算法是让每个节点不断的改变其gossip目标，来增加其本地效用值。这是通过让每个节点$v_i$在更新周期执行一次替换过程来实现的。在替换过程中，节点$v_i$（为了方便起见我们称为决定点）试探性的改变最多一个gossip目标，寻求提高其本地效用价值。
一开始决策节点计算它当前的效用值。这个值被标记为当前的最高效用，决定节点（随机）选择一个目标作为潜在的去除受害者 - 脱钩的后选人。节点然后创建空替换后选人名单，并将断开链接候选项添加到此列表中。
下一个决定节点遍历其成员列表中不是gossip目标元素$v_j$，通过目标集中的断开候选节点替换为节点$v_j$来计算效用值。这可能会出现三种情况，
- 如果新的效用低于当前的效用$v_j$从考虑中移除
- 如果效用更高，替换候选列表设置为单$\{v_j\}$，并且更新当前最高效用值
- 如果利用率一样，$v_j$添加到替换候选列表中
在看完所有成员名单后，一个从替换候选列表中选择随机节点作为断开链接候选节点的替换。本质上讲，上述机制实现了一种演进的效用覆盖。在4.1节中，我们讲分析JetStream全局实现的实验效果。在4.2章中，我们JetStream的本地实现继承了成员关系列表协议。
4.1 全局实现
为了研究描述算法的基本涌现特性，我们实验的系统有以下的假设
- 网络是非动态的，实际的及诶单不会离开，加入或者崩溃。
- 每个节点知道其他节点的存在，即成员列表是完备且一致的
- 每个节点都知道所有其他节点的当前目标集，换句话说，当一个节点更新它的目标集，更新会同时广播到所有其他节点。
一个简单的实现有以下重要的参数：更新周期1，替换的过程每隔一段时间执行一次。应该被指出，实现是简单的，单个节点替换过程计算复杂度为$O(n\times l^2)$。此外每个节点维护$O(n\times l)$的内存开销，来跟踪所有其他目标集。
结果：图2绘制了随机叠加的进程图（n=16，l=3）随着时间推移效用覆盖。单个节点选择产生更高效用的目标，最终得到$\frac{n\times l}{2}$双向的边。最初，节点的效用值迅速提高，很快达到收益递减点（图3(a)显示了n = 100, l = 5的网络中的现象）。然而，算法不断迫使节点产生更号效用的目标，直到网络稳定，而且不需要对覆盖层进行更多修改。因此当网络节点达到最大的利用值时网络收敛。
互惠在效用覆盖上执行费一定程度的平等：每个节点节点达到相同的入度值（回想一下，一个初始的随机网络覆盖有一个固定的常数外度-然而，度遵循二项分布）。图3为覆盖及诶单度分布标准差的递进图。最后，标准差减小为0，意味着节点度分布没有变化。在这一点上，网络不再显示出任何趋势值的变化。然而，这种特性仅在$n\times l$是偶数的情况下菜表现出来。当n·l为奇数时，网络不稳定，这是因为最后遗留的震荡（非往复式）目标点。解决这个问题的一个简单方法是总是使用偶数来表示l。
4.2 本地优化
4.3分析
5 结果
6 结论
gossip协议提供了概率性的可靠和可扩展性。然而，在章节2中，它们固有的随机性导致不同节点接收到的消息变化数量很大。在章节3和章节4我们提出了一种技术利用了简单的社交网络原则来智能的选择gossip目标。章节5我们展示了简单的启发式达到了更加一致的消息开销，同时降低了50%的系统带宽。我们通过实验将JetStream与规范的gossip以及Chord覆盖上的gossip进行比较。研究结果表明，JetStream可以帮助gossip以一种更确定可预测的方式传播，并将延迟减少到25%。同时仍然继承规模性和可靠性。最后，我们表明，如果连续八卦注入率超过低阈值，JetStream也比随机覆盖使用更少的带宽（对于大小为n=5000网络$I_{thresh}=0.076$）
引用
[5] D. J. Brass. A social network perspective on human resources management. Research in Personnel and Human Resources Management, 13:39–79, 1995.
[6] R. Burt. Structural Holes: The Social Structure of Competition. Harvard University Press, 1992.
[7] B. Cohen. Incentives build robustness in BitTorrent. In Proceedings of the Workshop on Economics of Peer-to-Peer Systems, 2003.
[8] A. Das, I. Gupta, and A. Motivala. SWIM: Scalable weakly-consistent infection-style process group membership protocol. In Proceedings of the International Conference on Dependable Systems and Networks (DSN), pages 303–312, 2002.
[9] S. Floyd, V. Jacobson, C. Liu, S. McCanne, and L. Zhang. A reliable multicast framework for light-weight sessions and application level framing. IEEE/ACM Transactions on Networking, 5(6):784–803, 1997.
[10] I. Gupta, A.-M. Kermarrec, and A. J. Ganesh. Efficient epidemic-style protocols for reliable and scalable multicast. In Proceedings of the Symposium on Reliable Distributed Systems (SRDS), 2002.
[11] A.-M. Kermarrec, L. Massouli, and A. J. Ganesh. Probabilistic reliable dissemination in large-scale systems. IEEE Transactions on Parallel and Distributed Systems, 14(3), 2003.
[12] D. Kostic, A. Rodriguez, J. Albrecht, and A. Vahdat. Bullet: High bandwidth data dissemination using an overlay mesh. In Proceedings of the ACM Symposium on Operating Systems Principles (SOSP), pages 282–297, 2003.
[13] P. Kouznetsov, R. Guerraoui, S. B. Handurukande, and A.-M. Kermarrec. Reducing noise in gossip-based reliable broadcast. In Proceedings of the Symposium on Reliable Distributed Systems (SRDS), 2001.
[14] S. Marti, P. Ganesan, and H. Garcia-Molina. DHT routing using social links. In Proceedings of the International Workshop on Peer-to-Peer Systems (IPTPS), pages 100–111, 2004.
[15] P. R. Monge and N. S. Contractor. Theories of Communication Networks. Oxford University Press, 2003.
[16] J. Pereira, L. Rodrigues, R. Oliviera, and A.-M. Kermarrec. Probabilistic semantically reliable multicast. In Proceedings of the IEEE International Symposium on Network Computing and Applications (NCA), 2001.
[17] D. Sandler, A. Mislove, A. Post, and P. Druschel. Feedtree: Sharing web micronews with peer-to-peer event notification. In Proceedings of the International Workshop on Peer-to-Peer Systems (IPTPS), 2005.
[18] I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, and H. Balakrishnan. Chord: A scalable peer-to-peer lookup service for internet applications. In Proceedings of the ACM SIGCOMM Conference, 2001.
[19] R. van Renesse, Y. Minsky, and M. Hayde. A gossip-style failure detection service. In Proceedings of the International Middleware Conference, 1998.
[20] S. Wasserman, K. Faust, D. Iacobucci, and M. Granovetter. Social Network Analysis: Methods and Applications. Cambridge University Press, 1994.