流行病广播树
概要
在流行病和基于树的广播原语之间存在固有的权衡。基于树的方法在稳定状态下具有较小的消息复杂度,但在存在故障时非常脆弱。gossip或者epodemic协议有高信息复杂度,但是页提供了更高的弹性。
这篇论文提出了综合的广播模式结合了俩者。我们使用地代价的模式来见了一个维护广播树,嵌入基于gossip的覆盖上。协议通过树的分支发送消息负载,但使用gossip覆盖的链路来加块回复和加速树的愈合。实验结果表明,该策略开销低,并且能够支持大数量的故障的同时保证高可靠性。
1 介绍
许多系统需要高可用和可靠的广播原语。这些原语的目的是确保正确的参与者收到所有的广播消息,即使在网络遗漏或者节点故障。Gossip已经成为了一种高度可扩展和弹性的实现可靠广播的方法。不幸的是,在稳态下,为了保证高概率的可靠性,gossip协议表现出过多的消息开销。另一方面,基于树的广播原语在稳态下具有较小的复杂性,但是在失败面前非常脆弱,缺乏流行病协议的弹性。
双峰广播是第一个开拓者结合了给予树的和基于gossip的原语。该方法的原理如下:在第一阶段广播信息使用不可靠的组播原语进行传播;在第二阶段,参与者gossip交流以掩盖在第一个阶段发生的遗漏。这个方法有俩个主要的缺点。一个是依赖于可用的IP组播,这并没有大范围的进行部署。为了客服这个限制,我们可以设想替代通过一些应用层的协议实现IP组播。然而,第二个缺点任然存在:这个方法需要使用俩中不同的协议,因此,这可能会带来不必要的复杂性。由于这个缺点最近的工作更倾向于用纯gossip的选项[10,25]。
在这篇论文中,我们提出了新的方法来结合基于树的和gossip协议来实现低消息复杂度和高可用。与之前的工作相反,我们的方法基于gossip的覆盖上创建了一个广播树。使用低成本算法创建和维护广播树,在这篇论文中描述。广播主要是通过在树枝上使用push gossip来实现的。然而,基于gossip覆盖的剩余链接也使用延迟推送的方法广播消息。lazy-push确保了高可靠性(通过保证,在面对失败时,协议退回到纯粹的gossip方法),此外,也提供了方式来快速的治愈广播树。我们将我们的协议命名为push-lazy-push多播树或者简称plumtree。plumtree有着低开销,因为它只需要基于gossip的随机覆盖就可以完成操作,避免了对于其他方案的依赖(比如基于IP的应用级别的组播)。模拟结果展示了,Plumetree具有良好的可扩展性,并且能够快速恢复80%节点的故障。
本文的其余部分组织如下。在第2节中,我们简要介绍了纯八卦协议,这是我们协议的基础。第3节介绍了Plumtree,解释了其设计背后的基本原理并详细描述了其算法。第4节给出了通过仿真得到的实验结果,并对这些结果进行了较为深入的讨论。对Plumtree的相关工作进行了比较。第5节和最后的第6节介绍了未来的工作并对本文进行了总结。
2 gossip 协议
2.1 原理
启发gossip协议的基本思想在于让所有节点以平等的份额贡献消息传播。为了达到这一点,当一个节点需要广播一个信息,他随机选择项其发送消息的t个节点(t是一个典型的参数成为fanout)。在第一次接受到消息时,节点重复此过程(选择t个gossip目标并且转发消息给它们)。如果节点接收到了相同的信息俩次-这是可能的,因为每个节点使用独立的方式选择目标(而不知道其他节点选择的gossip目标)-它会简单的丢弃消息。假设每个节点跟踪它已经看到和传递的消息。清除消息历史记录的问题超过了本文的范围,以前已经讨论过了[14]。简单的gossip协议的操作模型不止提供高扩展性,也提供了高容错性,由于其内在能够掩盖网络遗漏和节点故障。
为了完全按照上述操作,gossip协议需要每个节点维护关于整个系统的成员(来选择每个gossip步中的目标)。显然,这种解决方案是不可伸缩的,不止是因为可能构成视图的大量节点,而且还因为维护完成成员的最新成本。为了克服这个问题,几个gossip协议都依赖于部分视图而不是完成的视图。不分视图是整个系统成员一个小的子集,节点在选择gossip协议时使用。不分视图建立了节点之间的邻居关系,它可以作为基于gossip的覆盖网络进行描述。
2.2 Gossip策略
以下的策略可以被用来实现gossip协议:
急切推送方式:只要它们是第一次接收到信息,节点随机发送消息负载到随机选择的对等。
推送方式:周期性的,节点查询随机被选中的对等节点,获取有关最近收到的消息。如果节点有新的信息,它们将其转发给查询节点。这种策略在结合一些不可靠的广播机制结合使用的时候效果最好。(IP多播)
懒推送方法:当一个节点接收到信息的第一时间,它发送消息标识符(而不是载荷)到随机选择的节点。如果对等节点还没有收到这个消息,那么就发送push请求。
这也是一个在急切push和其他策略中的取舍。急切push策略产生了更多的冗余流量,但是它们比懒推送或者拉去的方式有更低的延迟,因为它们需要额外的往返时间来交付。自然的,这些策略可以混合不同的方法。顾名思义,Plumtree结合了急切和懒push的思想。
2.3 度量
在这一章节我们定义指标来评估gossip协议。
可靠性:八卦可靠性定义为发送八卦广播的活动节点的百分比。100%的可靠性意味着协议能够交付信息给所有的其他节点,换句话说,该消息产生原子广播[13]。
相对的消息冗余(RMR):该指标衡量gossip协议的消息开销,它的定义是
$$ (\frac{m}{n-1})-1 $$
其中m是有效负载消息的总数,n是收到该广播的节点数。这个度量在只少有俩个节点接受消息时才够用。
RMR值为0意味着系统中的每个节点只有一个有效的负载交换,这显然是最优值。相反,高的RMR值代表着广播策略导致不良的网络使用率。请注意,如果不可靠可能会得到非常低的RMR值。因此目标是结合低RMR值和高可靠性相结合。此外RMR值进队具有相似可靠性的协议具有可比性。在纯gossip协议中,RMR与协议的扇出密切相关,因此它倾向于为扇出(fanout)-1。
Piggyback策略通常用于 双向通信 或 协议中交换消息 的场景,特别是当两个通信方需要相互传递信息时。具体来说,Piggyback策略允许在一个消息的传输过程中,同时携带另一个消息的响应或附加信息,从而避免单独发送额外的消息。
此度量不考虑控制消息,比如一些应用[18]它们通常比有效载荷的消息小的多,它们并不是导致网络资源枯竭的主要原因;此外这些消息可以使用piggyback策略发送来提供更号的利用网络。
最后交付跳(LDH):是广播到所有接收者所需要的跳数。当消息第一次被转发时,它的跳数被设置为1,并且每转发一次,跳数就增加一次。最后交付跳是由gossip协议传递最后一条消息的跳数。换句话说就是消息必须在交付之前的最大跳数。这个度量与gossip覆盖层的大小密切相关,它还提供了一些关于gossip协议的延迟见解。gossip协议的延迟是LDH乘以链路延迟。
3 流行病广播树
3.1 架构
图1描述了Plumetree架构和主要组件之间的交互。对等的采样服务是维护随机环绕网络的组件。这是依赖于部分视图的基于gossip协议的成员关系服务。plumtree protocol是实现我们gossip协议的组件;它有俩个主要的功能:
树构造我这个组件选择随机覆盖网络的哪些链路将使用急切推送转发有效的消息负载。我们的目标是一个简单的树构造机制,在控制消息方面具有最小的开销。
树修补 这个组件在树故障时修复树。该过程应该确保,尽管出现故障,生成树仍然覆盖所有节点。因此,它应该能够检测和修复树分区。此操作带来的开销也应该尽可能的低。
我们假设每个对等样本服务导出GetPeers()原语在它的接口中,如[11]中所建议的那样,流言广播协议使用该原语来获取有关应该向其发送消息的邻居的信息。此外,Plumtree protocol协议导出俩个原语:NeighborUp()和NeighborDown()。这些原语用于在对等抽样服务维护的部分视图发生更改时通知八卦协议。这些原语用于支持广播树的快速修复。
3.2 总览
Plumtree主要的设计原则如下。协议操作和任何的纯gossip协议一样运行,在这个场景下,为了广播一个信息,每个节点与对等采样服务的提供的f个节点交互(其中f是协议的扇出)。然而,每个及诶单使用急切推送和懒推送gossip。急切推送只用于f节点的子集,懒推送被用于剩下的节点。被选中使用急切推送的链路的方式是,它们的闭包有效的构建了嵌入在随机覆盖网络中的广播树。延迟推送链路用于确保节点故障时的八卦可靠性,也用于快速修复广播树。此外,与其他的gossip协议相反,(随机)对等体的集合在每一轮gossip中都不会改变。相反,在检测到故障之前使用相同的对等节点。鉴于gossip的交流关系是稳定的,我们使用TCP连接来支持消息交换,因为它提供了可靠的额外的故障检测的来源。
3.3 对等采样和初始化
plumtree依赖于随机覆盖网络,它通过对等采样服务维护。覆盖网络需要具备一些基本特性,由对采样服务来保证,如下:
连通性:覆盖需要是连接的。所有节点在其局部视图中至少应该有另一个正确的节点;所有的节点都在正确的节点和局部的视图中;所有节点应该都属于一个集群。
可扩展的:我们的协议是大型的分布式应用,因此对等采样服务需要在这样的大型系统下正常运行(超过10,000节点)
交互的成员:生成树的稳定性取决于对等抽象维护视图的稳定性。当一个节点被添加或从视图中删除时,它可能会对锁产生的生成树做改动。这些改动也许不可取,因此,对等采样服务应该采用响应策略,在稳定状态下运行时在部分视图中维护相同的元素。
为了添加这些特性,这些特性是Plumtree的运行基础,对等抽样服务还可以展示一些其他需要的属性,从某种意义上说,它们改进了协议的操作。其中一个属性是对称的视图。如果采样数中的链路是对称的,那么树可能被多个源共享。对称的局部视图让创建双向树的任务更简单,并且减少了每个节点必须维护的对等节点的数量。
为了算法的正确操作,它维护俩个对等的集合:eagerPushPeers它使用急切推送消息lazyPushPeers使用懒推送消息。最初eagerPushPeers包含f个随机节点,且lazyPushPeers是空的(算法1.12-17行)。因此,在第一轮,协议操作作为纯push gossip。扇出值f必须这样选择,所有节点的eagerPushPeers所定义的覆盖网络是联通的,并且涵盖所有节点。
3.4 gossip和树构造
我们使用类似[12]中的机制来构造生成树。在初始化上述的eagerpushPeers 集合后,节点通过移动令居从eagerPushPeers到lazyPushPeers,这样一来,在协议演化后,第一个集合定义的覆盖变成了树。当一个节点第一次接收到消息,它将发送方包含在集合eagerPushPeers中(算法1 24-33行)。这确保了发送方节点的链接是双向的,并且属于广播树。当接收到一个副本时,它的发送者被移动到lazyPushPeers(图34-37行)。此外Prune消息被发送到该发送方,作为响应,它也将链接移动到lazyPushPeers(算法1 38行-40行)。此过程确保了在第一次广播终止时生成了树。
一个有趣的方面是,假设一个稳定的网络(即不变的负载),它将会倾向于最小消息延迟的生成树(因为它只保留在每个节点上生成第一跳消息的接受路径)。
只要节点被添加到lazyPushPeers集合中,消息开始使用急切推送和延迟推送进行传播。延迟推送是通过发送IHAVE消息实现的。只包含广播ID,发送给所有lazyPushPeers。但是请注意,为了减少控制流量,IHAVE消息不需要立即发送。pigyback策略用于在单个控制消息中附带多个IHAVE通知。IHAVE消息的唯一要求是,每条IHAVE消息最终都要被调度传输。
3.5 容错和修复树
当错误发生了,只少有一个树枝受到影响。因此,急切推送不足以保证消息的传递。懒推送消息通过剩下的节点交换延迟推送消息不仅用于恢复丢失的消息,也提供了一种快速修复多播树的机制。
当一个节点收到IHAVE消息,它简单的标记对应的消息为缺失(算法2 1-15行)。然后启动一个定时器,并且使用预定义的超时值,并在计时器到期之前等待通过急切推送接受丢失的消息。超时值是一个协议参数,应该根据覆盖的直径和目标最大恢复延迟进行配置,按照应用的需要进行定义。
当给定节点的计时器到期,该节点将丢失的消息选择它收到的第一个IHAVE通知。然后发送GRAFT消息到IHAVE的声明源(算法2 6-11行)。GRAFT消息有俩个用途。第一,它出发丢失消息有效的负载传输。第二,它将相应的链添加到广播树中,恢复它(算法2 12-16行)。读者应该注意到,当GRAFT消息被发送,另一个计时器在一定超时后开始过去,来确保消息在未收到的情况下会被请求到另一个邻居。按照邻居平均往返时间的顺序,第二个超时值应该比第一个小。
注意由于单点故障多个节点可能会断开连接,因此几个节点可能会尝试修复生成树。然而这并不是问题,因为构建树的自然过程将会扇出此过程产生的任何冗余的分支。(当消息被节点多次接收时)
3.6动态成员关系
我们现在描述Plumetree在gossip覆盖下。这些变化由NeighborDown和NeighborUp通知。当邻居探测到离开环绕它简单的从成员列表中进行删除。从丢失的历史记录中删除失败成员发送的IHAVE消息记录。(算法2 17-21行)。当新的成员被单测到,只需要将其添加到eagerPushPeers中,即它被认为是候选树的一部分。
修复中一个有趣的方面是,当子树被生成,由于全局成员的变化,它只需要,其中一个断开连接的节点收到IHAVE消息,将所有的这些节点连接到根节点(修复整个生成树)。只要失败的节点数量减少,这就足以修复生成树,生成断开连接的子树。当大量节点失败时,更有可能从树中分离出单个节点。在这种情况下,修复树所需的时间可能很长。为了加速这个处理过程,我们利用了对等抽样服务的修复特性。一旦对等抽样服务断开连接的及诶单继承到另一个成员的部分视图中,它生成一个NeighborUp 通知。这个通知立即将断开连接的成员放回广播树中。
3.7 基于发送的树VS共享树
由于Plumtree是针对发送方进行优化:用于将节点从eagerPushPeers集合移动到lazyPushPeers的第一个广播源。在有多个发送者的网络中,Plumtree可以以俩中不同的方式使用。
- 对于优化延迟,可以为每个不同的发送者使用一个不同的Plumtree实例。然而这需要为每个基于发送方的树维护一个Plumtree状态的实例,以及内存和信令开销。考虑到Plumtree的低开销,这对于少数发送者来说是可行的。
- 或者,一个共享的Plumtree可以用于多个发送者。显然,LDH值除了发送方的所有都不是最优的。另外,需要执行Plumtree协议的单个实例。
在评估章节中,我们将描述使用共享树的单个发送者和多个发送者的Plumtree性能结果,这样读者就可以评估所涉及的权衡。
3.8 优化
我们算法的生成树主要有系统中交换的第一跳广播消息所遵循的路径来定义。因此,该协议没有利用覆盖层中可能出现的最终新的、最好的路径。此外修复过程受到用于调度IHAVE消息策略的影响。随着算法系统的演进,这俩个因素会对LDH值产生负面影响。
为了克服这些限制(我们提出了算法2 24-28行),对于Plumtree算法的优化。如果对树进行了优化,那么急切推送受到的消息的跳数应该小于或等于懒推送接收到的消息的通知的跳数。如果不是这种情况,这表明可以通过(更好的)懒连接来替换最优的渴望链接来优化。为了提高树的稳定性,当跳数的差异大于某个阈值时,才会执行此优化。阈值的设置会影响生成树的整体稳定性。该值越低,协议就越容易通过交换属于树的链接来优化树。读者需要注意,由于每个源节点到每个接受者的距离是相对恒定的,当协议在单方模式下运行时,阈值可能会更低。另一方面,对于多个发送者,该值应该更高,并且接近覆盖的直径,以避免链路不断变化。注意对于多个发送者,源和接收方之间的距离随着每个广播消息的变化而变化。
4 评估
我们使用广泛的模拟评估广播的性能。我们使用基于周期的仿真引擎在PeerSim模拟器中进行了所有仿真。为此我们实现了Plummtree协议并对其进行了优化。为了获得对比数据,我们使用简单的push gossip策略,该策略展示了使用嵌入树的相同随机覆盖中所有链接的特殊性。我们将这个协议命名为eager,我们在[15]中给出了它的原理。
所有的模拟都从一个链接周期开始,在这个链接周期中所有的节点通过peer sampling协议的加入机制加入覆盖。所有的模拟执行250个模拟周期,其中前50个是用来确保稳定的。所有的循环从一个故障步骤开始,在预定于的模拟循环中,节点被标记为故障,接下来是广播步骤,其中随机选一个节点来发送广播消息。当没有更多的消息在覆盖层中传播时,广播才被认为终止。成员步骤被执行,其中对等采样协议定期定期执行操作删除故障节点。
在章节3.7中我们实验了Plumtree协议并且优化了单个的发送者(s-s)以及多个发送者(m-s),这个生成树是由所有节点共享的,以散步消息。
4.1 实验性设置
所有实验是由10000节点组成的网络下进行的,结果展示了每个实验的运行结果。我们在所有环境中使用对等采样服务。我们使用ParView对等采样协议[15,16],因为其提供的服务具有3.3条所述的所有理想属性。HyParView使用小的活动视图来传播消息,这使得eager策略是有效的,HyPar配置了与[5]中相同的设置。许多设置都是特定与协议进行内部操作的,与这些实验的背景无关。然而需要说明的是,协议的活动成员关系大小的配置为5因此。eager协议和Plumtree协议的扇出配置都为4.
假设HyParView的属性允许我们使用一个非常小的扇出值,任然得到一个链接的覆盖,急切的消息复杂度多少有些保守。
至今是任意俩个节点之间最长最短的路径(最大的跳数)
对于模拟,我们不适用任何piggyback策略于IHAVE消息,即每个IHAVE在懒链路中立即发送。最后,将Plumtree优化版本的阈值参数配置为单发送方模式的值为3,多发送方模式的值为7。这个阈值选择考虑了覆盖的直径,通常在8-9之间,因为它在早期模拟中是非常好的选择。
4.2 稳定的环境
我们先介绍在稳定环境下对Plumtree协议的评估,其中在整个模拟中没有引起节点的故障。图2描述了最后200个模拟周期的相对消息冗余(如第二节所定义)。从这个数字中需要记住的重要方面是,正如预期的那样,eager策略产生一个常数值3,而Plumtree即其优化的生成值为0(对于大部分消息)。
在构建树的过程中观察详细的协议行为是很有趣的。可以预期的是,在构造生成树的过程中会出现一些开销。我们在图2(b)中描述了对第一种方法在前10次模拟的相对消息冗余。对于模拟的前俩个周期,Plumtree协议生成更多冗余消息。然而冗余消息的数量永远低于渴望产生的冗余消息数量。
图2(c)展示了所有协议的LDH值。eager协议和Plumtree和但发送方表现出最好的性能。此外eager协议使用所有可用的链接来衡量消息,这确保了最短路径都被沿用。这表明使用单个发送器,Plumtree能够选择最快的链接进行交付。对于多个发送方,原始Plumtree协议值非常高。这是因为生成树被优化到广播第一条消息节点,当消息位于树叶位置节点发送时,它需要在覆盖层中执行更多的跳数才能达到所需要的节点。另一方面协议的优化可以显著的较低LDH值。读者应该注意到因为优化出发了不同的发送者,事实上它将更号地通过覆盖分布形成树的链接,有效的写出了树的第一条发送者的偏差。
表1展示了在100轮中,接收数量。当使用Plumtree额外的控制消息。使用Plumtree时收到的额外控制消息基本上是由于IHAVE消息。然而读取者需要考虑
- 通常IHAVE消息比有效负载消息小,因此这些消息对耗尽网络资源的贡献较小
- 通过延迟这些消息的传输并在单个IHAVE消息中发送多个有效负载消息标识符来聚合IHAVE消息。当负载信息长于控制信息时,我们的方法更有吸引力。但如果不是这种情况,可以使用消息piggybacking等技术将控制消息的影响最小化。
读取者需要注意Plumtree协议优化与多个发送方生成接近的10000个额外的控制消息,这些消息与单个发送者或者具有多个发送者的原始Plumtree协议相同。这意味着信号成本增加了22.5%。这种情况的发生是由于以下现象,因为每个信息是被不同的节点发送的,协议将会出发多次优化例程。这需要向邻居发送俩条额外的消息,这就解释了为什么会有更多的控制消息。
4.3 大量的故障
最后我们提出了大规模的故障对协议行为的影响。大规模的故障是指大量的节点同事发生故障。为了实现这一点,我们在稳定期后引导了几个百分比节点的故障。我们实验了系统的故障率从10%-95%不等。
图3(a)-3(b)展示了所有协议在3个不同的故障率下的LDH。如预期的,它证实了上述结果。所有协议都为LDH保持一个恒定的值。其中有单个发送方的eager协议和Plumtree(和它的优化)具有最佳性能,其次是具有多个发送者的优化Plumtree,最后是具有多个原始发送者的Plumtree。
图3(c)-3(d)描述了相同故障百分比下故障后的RMR。从这些图中要记住的重要方面是,所有协议都能够在几个周期内恢复故障前的RMR水平。故障后所有协议都表现出低水平的冗余。对于所有故障百分比,故障后,所有版本的Plumtree协议都展示了冗余消息的增加。这是由于覆盖层的修复过程,增加了新的链路来补偿由于故障丢失的链路,从而传输了额外的有效载荷消息。负载消息的eager协议冗余随着覆盖的愈合而增加。
我们最后提出对于每个百分点了这些大量故障的一些影响的概要。图3(e)描述了每个协议在故障之后立即的可靠性。读者应该注意到当故障百分比超过70%,协议的可靠性下降到0。这种情况的发生是因为覆盖层断开了连接。然而协议能够恢复它的可靠性。如图3(f)所示,其中计算了所有协议恢复其可靠性所需要的周期数。在模拟循环次数中重新可靠性的时间没有显著差异。假设树嵌入只用于选择哪些链接用于急于/延迟推送,这清楚的展示了Plumtree维护eargergossip协议的可靠性。
4.4 多次故障
我们也评估了系统在恒定故障率下的性能。为此,我们运行实验,其中在固定周期,我们失败首100个循环50个节点。它展示了,即便在这样一个不稳定的环境,Plumtree也能够保持100%的稳定性,以及LDH和RMR值接近故障出现之前。不幸的是由于篇幅所限,我们无法描绘出数组。感兴趣的读者可以参考在线提供的扩展报告。[17]
4.5讨论
我们展示了嵌入的生成树,在低延迟和随机覆盖网络实现了以可靠的方式传播消息,和简单的gossip协议相比,覆盖上的流量要少得多。此外利用不属于生成树的随机覆盖的链接,可以有效检测分区和修复树。我们的方法的一个有趣的方面是,通过维护每个源生成树的状态,可以很容易的为少量源节点提供优化的结果。这是可行的,就像我们的方法不需要维护复杂的状态。
在延迟方面,我们的方案对于构建基于发送者的数更有效,它也可以被用来支持共享的树,它在整个系统方面的损失是这个值的俩倍。这可以通过放宽对生成树稳定性的约束来实现。给出了生成树稳定性的约束条件。通过这种方式,可以改善系统的延迟,并在生成树由多个节点共享以传播消息时提供更好的结果。我们展示了相同的策略用来探和修复生成树,可以很容易的扩展和优化这些条件。我们认为这是至关重要的,以避免共享树时产生负面的影响。
6 相关工作
7 结论和未来工作
流行病协议吸引方法来构建高可用和可伸缩的广播原语,因为他们对消息丢失有天然的弹性。另一方面,基于树的广播最小化消息的复杂度,但在存在故障节点时非常脆弱。
在这篇论文中我们提出了总和广播模式结合了俩中方法。我们使用低代价模式来构建维护广播树嵌入在低代价的随机gossip环绕网络上。协议传播负载信息最好是通过树干,但是使用随机覆盖的剩余链接快速恢复和加速树的愈合。实验表明,我们的信策略开销低,它能支持大规模的故障数,同时维护高可用。
作为将来的工作,我们渴望开发新的策略和成员关系服务,它能够暴露关于底层网络条件的自适应的行为。我们的最终目标是开发基于自声音环绕网络的系统,它能够直接和低延迟的广播原语竞争,比如IP多播。此外我们没有解决负载均衡问题,涉及到节点的分布的同事保持生成树结构。实际上,当依赖于HyParView成员协议[15]的属性时,这项任务变得容易。在将来我们也会学习如何使用对等采样服务时,确保负载均衡时维护生成树。
8 引用
- Badishi, G., Keidar, I., & Sasson, A. (2004). Exposing and eliminating vulnerabilities to denial of service attacks in secure gossip-based multicast. In Proc. of the Intl. Conf. on Dependable Systems and Networks (DSN) (pp. 201–210). June – July 2004.
- Birman, K., Hayden, M., Ozkasap, O., Xiao, Z., Budiu, M., & Minsky, Y. (1999). Bimodal multicast. ACM Transactions on Computer Systems, 17(2). May 1999.
- Carvalho, N., Pereira, J., Oliveira, R., & Rodrigues, L. (2007). Emergent structure in unstructured epidemic multicast. In Proc. of the Internacional Conf. on Dependable Systems and Networks (DSN), Edinburgh, UK. June 2007.
- Castro, M., Druschel, P., Kermarrec, A., & Rowstron, A. (2002). SCRIBE: A large-scale and decentralized application-level multicast infrastructure. IEEE Journal on Selected Areas in Communications (JSAC), 20(8), 1489–1499.
- Chu, Y.-H., Rao, S., Seshan, S., & Zhang, H. (2002). A case for end system multicast. IEEE Journal on Selected Areas in Communications, 20(8), 1456–1471. October 2002.
- Chun, B., Culler, D., Roscoe, T., Bavier, A., Peterson, L., Wawrzoniak, M., & Bowman, M. (2003). Planetlab: An overlay testbed for broad-coverage services. SIGCOMM Computer Communication Review, 33(3), 3–12.
- Deering, S. E., & Cheriton, D. R. (1990). Multicast routing in datagram internetworks and extended LANs. ACM Transactions on Computer Systems, 8(2), 85–110.
- Deshpande, M., Xing, B., Lazardis, I., Hore, B., Venkatasubramanian, N., & Mehrotra, S. (2006). Crew: A gossip-based flash-dissemination system. In Proc. of the 26th IEEE Intl. Conf. on Distributed Computing Systems (ICDCS) (p. 45). Washington, DC, USA: IEEE Computer Society.
- Diot, C., Levine, B. N., Lyles, B., Kassem, H., & Balensiefen, D. (2000). Deployment issues for the IP multicast service and architecture. IEEE Network, 14(1), 78–88.
- Ganesh, A. J., Kermarrec, A.-M., & Massoulie, L. (2001). SCAMP: Peer-to-peer lightweight membership service for large-scale group communication. In Networked Group Communication (pp. 44–55).
- Jelasity, M., Guerraoui, R., Kermarrec, A.-M., & van Steen, M. (2004). The peer sampling service: Experimental evaluation of unstructured gossip-based implementations. In Proc. of the 5th ACM/IFIP/USENIX International Conference on Middleware (pp. 79–98).
- Jiang, S., & Zhang, X. (2003). FloodTrail: An efficient file search technique in unstructured peer-to-peer systems. In IEEE Globecom’03, San Francisco, California. December 2003.
- Kermarrec, A.-M., Massoulie, L., & Ganesh, A. J. (2003). Probabilistic reliable dissemination in large-scale systems. IEEE Transactions on Parallel and Distributed Systems, 14(3), 248–258.
- Koldehofe, B. (2003). Buffer management in probabilistic peer-to-peer communication protocols. In Proc. of the 22nd IEEE Symposium on Reliable Distributed Systems (SRDS’03) (pp. 76–87). Florence, Italy. October 2003.
- Leitao, J., Pereira, J., & Rodrigues, L. (2007). HyParView: A membership protocol for reliable gossip-based broadcast. In Proc. of the 37th Annual IEEE/IFIP Intl. Conf. on Dependable Systems and Networks (DSN’07) (pp. 419–429). Edinburgh, UK: IEEE Computer Society.
- Leitao, J. (2007). Gossip-based broadcast protocols. Master’s thesis, University of Lisbon.
- Leitao, J., Pereira, J., & Rodrigues, L. (2007). Epidemic broadcast trees. DI/FCUL TR 07–14, Department of Informatics, University of Lisbon. May 2007.
- Li, H. C., Clement, A., Wong, E. L., Napper, J., Roy, I., Alvisi, L., & Dahlin, M. (2006). BAR gossip. In Proc. of the 7th USENIX Symposium on Operating Systems Design and Implementation (OSDI’06) (pp. 14–14). Berkeley, CA, USA: USENIX Association.
- Liang, J., Ko, S. Y., Gupta, I., & Nahrstedt, K. (2005). MON: On-demand overlays for distributed system management. In 2nd USENIX Workshop on Real, Large Distributed Systems (WORLDS’05).
- Peersim p2p simulator. Retrieved from http://peersim.sourceforge.net/.
- Pereira, J., Rodrigues, L., Pinto, A., & Oliveira, R. (2004). Low-latency probabilistic broadcast in wide area networks. In Proc. of the 23rd IEEE Symposium on Reliable Distributed Systems (SRDS’04) (pp. 299–308). Florianopolis, Brazil. October 2004.
- Rowstron, A. I. T., & Druschel, P. (2001). Pastry: Scalable, decentralized object location, and routing for large-scale peer-to-peer systems. In Proc. of the IFIP/ACM Intl. Conf. on Distributed Systems Platforms Heidelberg (pp. 329–350). London, UK: Springer-Verlag.
- Rowstron, A. I. T., Kermarrec, A.-M., Castro, M., & Druschel, P. (2001). SCRIBE: The design of a large-scale event notification infrastructure. In Networked Group Communication (pp. 30–43).
- Tang, C., & Ward, C. (2005). GoCast: Gossip-enhanced overlay multicast for fast and dependable group communication. In Proc. of the 2005 Intl. Conf. on Dependable Systems and Networks (DSN’05) (pp. 140–149). Washington, DC, USA: IEEE Computer Society.
- Voulgaris, S., Gavidia, D., & Steen, M. (2005). Cyclon: Inexpensive membership management for unstructured p2p overlays. Journal of Network and Systems Management, 13(2), 197–217. June 2005.
- Zhao, B. Y., Kubiatowicz, J. D., & Joseph, A. D. (2001). Tapestry: An infrastructure for fault-tolerant wide-area location and routing. Technical Report UCB/CSD-01-1141, UC Berkeley. April 2001.
- Zhuang, S. Q., Zhao, B. Y., Joseph, A. D., Katz, R. H., & Kubiatowicz, J. D. (2001). Bayeux: An architecture for scalable and fault-tolerant wide-area data dissemination. In Proc. of NOSSDAV. June 2001.