轉載自：http://blog.163.com/liaoxiangui@126/blog/static/795696402012121112831272/
1.背景
Gossip算法又被稱為反熵（Anti-Entropy），熵是物理學上的一個概念，代表雜亂無章，而反熵就是在雜亂無章中尋求一致，這充分說明了Gossip的特點：在一個有界網絡中，每個節點都隨機地與其他節點通信，經過一番雜亂無章的通信，最終所有節點的狀態都會達成一致。每個節點可能知道所有其他節點，也可能僅知道幾個鄰居節點，只要這些節可以通過網絡連通，最終他們的狀態都是一致的，當然這也是疫情傳播的特點。
要注意到的一點是，即使有的節點因宕機而重啟，有新節點加入，但經過一段時間后，這些節點的狀態也會與其他節點達成一致，也就是說，Gossip天然具有分布式容錯的優點。
Gossip是一個帶冗余的容錯算法，更進一步，Gossip是一個最終一致性算法。雖然無法保證在某個時刻所有節點狀態一致，但可以保證在”最終“所有節點一致，”最終“是一個現實中存在，但理論上無法證明的時間點。
因為Gossip不要求節點知道所有其他節點，因此又具有去中心化的特點，節點之間完全對等，不需要任何的中心節點。實際上Gossip可以用于眾多能接受“最終一致性”的領域：失敗檢測、路由同步、Pub/Sub、動態負載均衡。
但Gossip的缺點也很明顯，冗余通信會對網路帶寬、CPU資源造成很大的負載，而這些負載又受限于通信頻率，該頻率又影響著算法收斂的速度，后面我們會講在各種場合下的優化方法。
2.基本概念
gossip分為兩種. 本文只討論anti-entropy
■anti-entropy 只要數據不同步，就開始同步數據
■rumor mongering 每隔固定的時間同步數據
見公式(1). 此公式表示在節點p上，q節點的屬性k的值是v，其版本號是n。
為了保證一致性，規定數據的value及version只有宿主節點才能修改，其他節點只能間接通過Gossip協議來請求數據對應的宿主節點修改，即m (p)只能由有節點p來修改。
anti-entropy協議通過版本號大小來對數據進行更新。
兩個節點（A、B）之間存在三種通信方式:
■push-gossip: A節點將數據推送給B節點，B節點更新A中比自己新的數據
■pull-gossip：A僅將摘要數據 (node,key,value,version)推送給B，B根據摘要數據來選擇那些版本號比A高的數據推送給A，A更新本地。
■push-pull gossip：與pull類似，只是多了一步，A再將本地比B新的數據推送給B，B更新本地。
如果把兩個節點數據同步一次定義為一個周期，則在一個周期內，push需通信1次，pull需2次，push/pull則需3次。從效果上來講，push/pull最好，理論上一個周期內可以使兩個節點完全一致。直觀上也感覺，push/pull的收斂速度是最快的。
3.數據同步(RECONCILIATION)
3.1精確同步(precise reconciliation)
精確同步希望在每次通信周期內都非常準確地消除雙方的不一致性，具體表現為相互發送所有對方需要更新的數據。實現過程中，精確同步很難做到。因為摘要數據過多，但Gossip消息存在大小限制。因此每次選擇發送哪些數據就成了問題。
3.2整體同步(Scuttlebutt reconciliation)
節點會維護一個唯一的時間戳生成器， 時間戳生成器為各個屬性生成時間戳，時間戳的值單調遞增。節點在生成摘要數據時，每個節點只有一份數據{node,最大時間戳)。需要傳輸的摘要數據和同步的實體數據的量大大的減少了。
對于敏感的網絡而言，可能同步的實體數據還是太多，還存在選擇發送哪些數據的問題，如下的原則需要遵守：Scuttlebutt requires that if a certain delta (r; k; v; n) is omitted, then all the deltas with higher version numbers for the same r should be omitted as well.。即低版本號的實體數據比高版本號的實體數據的優先級高。
要實現上述原則有2種方法。
■廣度優先(scuttle breadth)
出發點是對每個節點都公平。
It uses a ranking on deltas for the same participant. The delta with the lowest version number has rank 0, the next lowest rank 1, and so on. The deltas are first ordered by rank so that deltas with lower ranks are included before deltas with higher ranks.
■深度優先(scuttle-depth)
相比廣度優先，此方法對所有節點不公平。待傳輸的數據(delta data)越多，其優先級越高。這個方法要好于以上方法，但是作者沒有進行解釋。
4.流控(flow control)
待研究。。。。。