論文筆記：[DSN 2002] Scalable Weakly-consistent Infection-style process group Membership protocol

這篇論文提出了一種 epidemic-style membership protocol，對於這類協議，兩個功能是必須的：

1. Failure detector
2. Broadcast

論文的亮點在於使用 gossip 協議將這兩個必要組件一起搞定了，但是個人感覺還有很多可以優化的空間。

Failure detector 的部分通過 ping message 實現探測，為了提高準確率，在直接 ping 失效時，再額外尋找 $k$ 個節點轉發 ping 信息，如果都失敗了，則推斷對端失效。論文中還增加了 suspect 和 probe 機制來減少慢節點引起誤判帶來的節點抖動（反覆退出/加入）的影響。

Broadcast 部分則通過 push-pull 模式進行信息交換，論文中詳細論述了交換方式，以保證在網路中傳播的信息大小增長速度是 $O(n)$ 的（不確定）。

This is an improvement over all-to-all heartbeating based protocols that have a linear variation (with group size) of either the detection time for failures or the network bandwidth usage at each member (or an increase in the false positive rate).

Apache Cassandra 和 Serf by HashiCorp 都使用了一個修改版本的 SWIM 協議，在 broadcast 的時候，不是只返回「新鮮」的若干條消息，而是通過三次交換（syn-ack1-ack2）使得兩個節點得到一次全同步（full sync）。

也許使用其他更先進的 gossip 協議可以得到更好的結果（[PODC 2017] Optimal Address-Oblivious Epidemic Dissemination）。

A. Das, I. Gupta, and A. Motivala, 「SWIM: Scalable Weakly-consistent Infection-style process group Membership protocol,」 in Proceedings of the 2002 International Conference on Dependable Systems and Networks, 2002, pp. 303–312.

A. Dadgar, J. Phillips, and J. Currey, 「Lifeguard?: SWIM-ing with Situational Awareness,」 Jul. 2017.