Gossip Tutorial

Amyfish

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

Informations

• Publié par: Urre
• Nombre de lectures: 45
• Langue: English

Extrait

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)