Gossip protocols spread information the way an epidemic spreads: periodically, each informed node contacts a small random fanout. Duplicate messages look wasteful, but randomness removes a central bottleneck and makes dissemination robust to individual loss.
Push, pull, and push-pull
- Push: informed nodes send updates.
- Pull: nodes ask peers what they missed.
- Push-pull: both exchange summaries and updates.
Push spreads new information quickly at first; pull is efficient near completion; hybrids perform well across both phases. With a constant fanout, dissemination typically reaches a large group in logarithmic rounds with high probability, not an absolute guarantee.
Membership is a changing view
A membership service tracks which processes are believed to be in the group. Every member cannot probe every other member at large scale, so gossip-style protocols disseminate joins, leaves, heartbeats, and suspicions.
Failure detection is fundamentally imperfect in an asynchronous network. A missing heartbeat may mean crash, congestion, delay, or a partition.
In plain terms: a failure detector does not detect death; it detects that a response missed a deadline.
Suspicion is better than immediate eviction
A practical detector moves through states:
alive → suspected → failed
│
└── refutation/heartbeat → aliveIndirect probing asks other nodes to contact an unresponsive target. This separates a bad path from a bad process and reduces false positives. Suspicion timeouts let contradictory evidence arrive before membership changes become final.
Evaluate more than detection speed
| Metric | Question |
|---|---|
| Detection time | How long until a real failure is suspected? |
| Mistake rate | How often is a live member suspected? |
| Mistake duration | How long does a false suspicion last? |
| Message load | How much traffic does detection generate? |
Tighter timeouts reduce detection time but increase mistakes. There is no universally best detector; tune it to network variance and the cost of a false eviction versus slow failover.
Review card
- Gossip trades duplicate messages for decentralization and robustness.
- Push is strong early; pull helps finish dissemination.
- Membership is a local, changing belief rather than instant global truth.
- Timeout cannot distinguish failure from delay.
- Suspicion and indirect probes reduce premature eviction.
- Tune detection using speed, mistakes, duration, and message cost.
Gossip protocol 像 epidemic 一樣傳資訊：每個 informed node 定期聯絡少量 random target。Duplicate message 看似浪費，卻移除 central bottleneck，也讓 dissemination 能承受單點 message loss。
Push、pull、push-pull
- Push： informed node 主動送 update。
- Pull： node 問 peer 自己漏了什麼。
- Push-pull： 雙方交換 summary 與 update。
Push 在初期散播快；pull 在接近完成時有效；hybrid 橫跨兩個階段。Constant fanout 通常能以 logarithmic rounds、高機率覆蓋大型 group，但不是 absolute guarantee。
Membership 是持續變動的 view
Membership service 追蹤哪些 process 被相信仍在 group。大型系統不能讓每個 member probe 所有人，因此 gossip-style protocol 傳 join、leave、heartbeat 與 suspicion。
Asynchronous network 裡 failure detection 天生不完美。漏 heartbeat 可能是 crash、congestion、delay 或 partition。
白話來說： Failure detector 不是偵測死亡，而是偵測 response 錯過 deadline。
Suspicion 比立即移除安全
alive → suspected → failed
│
└── refutation/heartbeat → aliveIndirect probe 請其他 node 聯絡失聯 target，能分清壞 path 與壞 process，降低 false positive。Suspicion timeout 則讓反證有時間抵達。
不只比較 detection speed
| Metric | 問題 |
|---|---|
| Detection time | 真故障多久被懷疑？ |
| Mistake rate | 多常誤判 live member？ |
| Mistake duration | False suspicion 持續多久？ |
| Message load | Detection 產生多少 traffic？ |
Timeout 越緊，detection 越快，mistake 也越多。不存在 universally best detector；要依 network variance、false eviction 與 slow failover 的代價調整。
複習卡
- Gossip 用 duplicate message 換 decentralization 與 robustness。
- Push 擅長初期，pull 幫助完成覆蓋。
- Membership 是 local、持續變動的 belief，不是瞬時 global truth。
- Timeout 無法分清 failure 與 delay。
- Suspicion／indirect probe 降低過早 eviction。
- 以 speed、mistake、duration、message cost 共同調參。