Gossip Tutorial

pages

English

Documents

Écrit par
Amyfish

Publié par
Urre

Lire

Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres

pages

English

Documents

Lire

Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres

Publié par

Urre

Nombre de lectures

Langue

English

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

Publié par

Urre

Langue

English