Gossip协议

1 .Gossip Protocols CS 6410 Eugene Bagdasaryan 

2 .Gossip Protocols CS 6410 Eugene Bagdasaryan 

3 .What was covered before?  Paxos  Byzantine Generals  Impossibility consensus What are these ideas aimed for? What is the difference with the current paper? 

4 .What was covered before?  Paxos  Byzantine Generals  Impossibility consensus What are these ideas aimed for? Data consistency, fault-tolerance What is the difference with the current paper? “Eventual” consistency, scalability, fault-tolerance 

5 .CAP theorem CAP = Consistency, Availability, Partition tolerance  Previous papers focused on Consistency and Partition Tolerance Paxos sometimes is unavailable for writes, but would remain consistent  This paper wants to provide Availability, Partition Tolerance, and “relaxed” form of consistency 

6 .EPIDEMIC ALGORITHM FOR REPLICATED DATABASE MAINTENANCE Xerox Palo Alto Research Center 1987 

7 .Authors Alan Demers Dan Greene Palo Alto Carl Hauser Wesley Irish Cornell Univ. Coyote Hill Research Center Washington State Univ. Consulting LLC John Larson Howard Sturgis Dan Swinehart Scott Shenker Doug Terry EECS Berkley Samsung Research America 

8 .Real applications  Uber uses SWIM for real-time platform  Apache Cassandra internode communication  Docker’s multi-host networking  Cloud providers multi node networking (Heroku)  Serf by Hashicorp 

9 .Context  Xerox wanted to run replicated database on hundred or thousand sites  Each update is injected at a single site and must be propagated to all other sites  A packet from a machine in Japan to one in Europe may traverse as many as 14 gateways and 7 phone lines 

10 .Problem  High network traffic to send update over the large set of nodes  Time to propagate update to all nodes is significant 

11 .Problem  High network traffic to send update over the large set of nodes  Time to propagate update to all nodes is significant ” For a domain stored at 300 sites, 90,000 mail messages might he introduced each night”. 

12 .Basic idea Max Planck Institute für Dynamics and Self-organization 

13 .Objective  Design algorithms that scale gracefully  Every replica receives every update eventually 

14 .Objective  Design algorithms that scale gracefully  Every replica receives every update eventually “Replace complex deterministic algorithms for replicated database consistency with simple randomized algorithms that require few guarantees from the underlying communication system.“ 

15 .Why epidemic? Why gossip?  Highly available  Fault-tolerant  Overhead is tunable  Fast  Scalable  Epidemic spreads eventually to everyone 

16 .Types of nodes infective – node that holds an update it is willing to share susceptible – node that has not yet received an update  removed – node that has received an update but is no longer willing to share 𝑠+𝑖+𝑟 =1 

17 .Types of communication Direct mail Anti-entropy Rumor mongering 

18 .DIRECT MAIL  attempts to notify all other sites of an update soon after it occurs.  Social network case – infected accounts sends private message to his whole contact list with malicious link 

19 .DIRECT MAIL © Ki Suh Lee 

20 . DIRECT MAIL May not know this node © Ki Suh Lee 

21 .DIRECT MAIL Messages may be dropped © Ki Suh Lee 

22 .DIRECT MAIL  Pros: Fast  Cons: not reliable heavy load on network 

23 .ANTI-ENTROPY  Every site regularly chooses another site at random and by exchanging database contents with it resolves any differences between the two  Real life case – meet sometimes with old friends and tell all the fun stories about you and your friends. 

24 .ANTI-ENTROPY © Ki Suh Lee 

25 .ANTI-ENTROPY © Ki Suh Lee 

26 .ANTI-ENTROPY © Ki Suh Lee 

27 .ANTI-ENTROPY © Ki Suh Lee 

28 .ANTI-ENTROPY © Ki Suh Lee 

29 .ANTI-ENTROPY © Ki Suh Lee