Table of ContentsEpidemic Protocols (or, Gossip is Good) Overview Data Dissemination History How does gossip spread? State Monotonic Property Anti-Entropy How fast does gossip spread? Probability of Infection? Intuition: 2 phases Phase 1: fast growth of infection Phase 2: fast decline of uninfection Exponential growth #rounds distribution Expected #rounds Case Study 1: Failure Detection Informal Properties Environment Basic Gossip Protocol Linear Bandwidth Model Failure Caveat Analysis Failure Detection Time Quality of Detection Effect of Failed Members Effect of Message Loss Case Study 2: Bimodal Multicast PPT Slide PPT Slide PPT Slide An aside: Push vs. Pull PPT Slide PPT Slide Example Delivery? Garbage Collection? Throughput with perturbed processes But, gossip doesn’t scale... High load on routers Problems with partitions Idea: add locality to gossip Domains Multi-level Gossip Protocol Better properties Two-level hierarchy Two-level cost No longer logarithmic... Problems New idea Case Study 3: Astrolabe Example HMIB HMIB tree HMIB node/table Example: digital library Applications Other applications Implementation Membership issues Failure detection Member detection / Partition resolver Condensation Functions A few word on security Related Literature |
Author: Robbert van Renesse
Email: rvr@cs.cornell.edu Home Page: http://www.cs.cornell.edu/home/rvr |