Gossip Tutorial
65 Pages
English
Downloading requires you to have access to the YouScribe library
Learn all about the services we offer

Gossip Tutorial

-

Downloading requires you to have access to the YouScribe library
Learn all about the services we offer
65 Pages
English

Description

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. ...

Subjects

Informations

Published by
Reads 45
Language English

Exrait

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)