//img.uscri.be/pth/c577a011300c0b267caf3fb9fbda06364de5f798
La lecture en ligne est gratuite
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres
Télécharger Lire

Gossip Tutorial

De
65 pages
Epidemic Protocols(or, Gossip is Good)Robbert van RenesseOverview• Introduction• History• Building intuition• Case studies:– Failure Detection– Bimodal Multicast– Monitoring/Resource LocationData Dissemination• Want efficiency, robustness, speed, scale• Tree distribution is efficient, but fragile– (plus configuration is difficult)• Flooding is robust, but inefficient• Gossip is both efficient and robust, but has relatively high latencyTrade-OffsfastTree FloodrobustefficientGossipHistory• Ladies and Telephones (MIT, 1972)• Grapevine/Clearinghouse Directory Service (Demers, Xerox PARC, 1987)• Refdbms (Golding, UCSC, 1993)• Bayou (Xerox PARC, 1995)• Bimodal Multicast (Cornell, 1998)• Astrolabe (Cornell, 1999)Gossip ProtocolForever Foreverwait a while receive message mpick a random peer p state’ := Merge(state, m)send state to pGossipGossipRound 1: 2GossipRound 2: 4GossipRound 3: 7Gossip Propagation Time1.01/NTime →Time to complete “infection”: O(log N)% infectedState Monotonic Property• A gossip message contains the state of the sender of the gossip.• The receiver uses a Merge function to merge the received state and the sent state:– State’ = Merge(State, Gossip)• Need some kind of monotonicity:–State’ ≥ State–State’ ≥ GossipAnti-Entropy• This gossip scheme with monotonic merge is sometimes called anti-entropy.• The protocol is called a simple epidemic.How fast does gossip really spread?• Epidemic theory (e.g. ...
Voir plus Voir moins
Epidemic Protocols (or, Gossip is Good)
Robbert van Renesse
Introduction
History
Overview
Building intuition
Case studies:
– Failure Detection
– Bimodal Multicast
– Monitoring/Resource Location
Data Dissemination
Want efficiency, robustness, speed, scale
Tree distribution is efficient, but fragile
– (plus configuration is difficult)
Flooding is robust, but inefficient
Gossip is both efficient and robust, but has relatively high latency
Tree
efficient
Trade-Offs
fast
Gossip
Flood
robust
History
Ladies and Telephones (MIT, 1972)
Grapevine/Clearinghouse Directory Service (Demers, Xerox PARC, 1987)
Refdbms (Golding, UCSC, 1993)
Bayou (Xerox PARC, 1995)
Bimodal Multicast (Cornell, 1998)
Astrolabe (Cornell, 1999)
Forever
wait a while
Gossip Protocol
pick a random peer p
send state to p
Forever
receive message m
state’ := Merge(state, m)
Gossip
Gossip
Round 1: 2
Gossip
Round 2: 4
Gossip
Round 3: 7
Gossip Propagation Time
1.0
1/N
Time
Time to complete “infection”: O(log N)