Gossip (протокол)

Gossip (англ. сплетник) — это группа протоколов в одноранговой компьютерной коммуникации, в которых распространение информации идёт способом, схожим с образом распространения эпидемий^[1], и сводящимся к тому, что каждый или некоторые из узлов могут передавать обновляемые данные известным этому узлу соседям. Некоторые распределенные системы используют такой тип протокола, чтобы обеспечить распространение данных между всеми узлами распределённой системы. В некоторых сетях нет центрального реестра узлов, и использование gossip — единственный способ надёжно распространять между узлами общие данные. В качестве синонима этого термина также иногда используют словосочетание эпидемический протокол, имея в виду, что сплетни и вирусы распространяются в обществе схожим способом.

Общая идея править

Концепцию протокола-сплетника можно проиллюстрировать аналогией с офисными работниками, распространяющими слухи. Например, каждый час офисные работники собираются вокруг кулера для воды. Каждый сотрудник начинает общаться с другим, выбранным наугад, и делится с ним последними сплетнями. В начале дня Дэйв запускает новый слух: он рассказывает Бобу, что, по его мнению, Чарли красит свои усы. На следующей встрече Боб рассказывает об этом Алисе, а Дэйв повторяет эту сплетню Еве. После каждого похода к кулеру количество людей, услышавших этот слух, примерно удваивается (эта оценка не учитывает пересказ сплетни дважды одному и тому же человеку; возможно, Дэйв пытался рассказать эту историю Фрэнку, но обнаружил, что Фрэнк уже слышал её от Алисы). Компьютерные системы обычно реализуют этот тип протокола в форме случайного «однорангового выбора»: с заданной частотой каждый узел одноранговой сети случайным образом выбирает другой известный ему узел и передаёт тому обновлённую информацию.

Разумеется, аналогия с офисными сплетнями не точна. При реализации протоколов этой группы достижение хорошего качества обслуживания (то есть полного и своевременного распространения информации) обычно основывается на требовании, чтобы каждый из узлов-участников не дискриминировал другие узлы и обеспечивал быструю и надежную передачу данных одинаковым образом. В реальном сценарии офисных сплетен обычно не все сотрудники причастны к их распространению. Сплетни, в отличие от трансляций, носят дискриминационный характер, и некоторые сотрудники офиса часто не участвуют в жизненно важных или важных коммуникациях. Таким образом, сравнение с «офисными сплетнями» не так хорошо, как сравнение с распространением эпидемии, на которую социальный компонент влияет в меньшей степени. Тем не менее, название «gossip» устоялось и широко применяется.

Детали и варианты реализации править

Вероятно, существуют сотни вариантов конкретных протоколов, относящихся к этой группе. Постольку, поскольку Gossip — это идеология, а не стандарт, каждая конкретная реализация адаптируется к потребностям и сценарию использования, актуальными в конкретном случае.

Протокол Gossip может использовать некоторые из этих идей:

Протокола реализует периодические, попарные, межпроцессные взаимодействия.
Информация, которой узлы обмениваются во время этих взаимодействий, имеет ограниченный размер.
Когда агенты взаимодействуют, состояние по крайней мере одного агента изменяется, чтобы отражать состояние другого.
Надежной связи между узлами не предполагается.
Частота взаимодействий мала по сравнению с типичными задержками при передаче сообщений, поэтому затраты на протокол незначительны.
Выбор узла для взаимодействия происходит случайным образом.
Узлы для взаимодействия могут быть выбраны из полного набора узлов или из меньшего набора соседей.
За счет репликации происходит неявное дублирование доставляемой разными маршрутами информации.

Литература править

Литература по тематике, связанной с протоколом:

Correctness of a Gossip-based Membership Protocol. André Allavena, Alan Demers and John Hopcroft. Proc. 24th ACM Symposium on Principles of Distributed Computing (PODC 2005).
Bimodal Multicast. Kenneth P. Birman, Mark Hayden, Oznur Ozkasap, Zhen Xiao, Mihai Budiu and Yaron Minsky. ACM Transactions on Computer Systems, Vol. 17, No. 2, pp 41-88, May, 1999.
Lightweight probabilistic broadcast. Patrick Eugster, Rachid Guerraoui, S. B. Handurukande, Petr Kouznetsov, Anne-Marie Kermarrec. ACM Transactions on Computer Systems (TOCS) 21:4, Nov 2003.
Kelips: Building an Efficient and Stable P2P DHT Through Increased Memory and Background Overhead. Indranil Gupta, Ken Birman, Prakash Linga, Al Demers, Robbert van Renesse. Proc. 2nd International Workshop on Peer-to-Peer Systems (IPTPS '03)
Systematic Design of P2P Technologies for Distributed Systems. Indranil Gupta, Global Data Management, eds: R. Baldoni, G. Cortese, F. Davide and A. Melpignano, 2006.
HyParView: a Membership Protocol for Reliable Gossip-based Broadcast. João Leitão, José Pereira, Luís Rodrigues. Proc. 37th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN’07)
Efficient and Adaptive Epidemic-Style Protocols for Reliable and Scalable Multicast. Indranil Gupta, Ayalvadi J. Ganesh, Anne-Marie Kermarrec. IEEE Transactions on Parallel and Distributed Systems, vol. 17, no. 7, pp. 593—605, July, 2006.
T-Man: Gossip-based fast overlay topology construction. Márk Jelasity, Alberto Montresor, and Ozalp Babaoglu. Computer Networks, 53(13):2321-2339, 2009.
Epidemic Broadcast Trees. João Leitão, José Pereira, Luís Rodrigues. Proc. 26th IEEE International Symposium on Reliable Distributed Systems (SRDS’07).
Gossip-based aggregation in large dynamic networks. Márk Jelasity, Alberto Montresor, and Ozalp Babaoglu. ACM Transactions on Computer Systems, 23(3):219-252, August 2005.
Ordered slicing of very large overlay networks. Márk Jelasity and Anne-Marie Kermarrec. IEEE P2P, 2006.
Proximity-aware superpeer overlay topologies. Gian Paolo Jesi, Alberto Montresor, and Ozalp Babaoglu. IEEE Transactions on Network and Service Management, 4(2):74-83, September 2007.
X-BOT: A Protocol for Resilient Optimization of Unstructured Overlays. João Leitão, João Marques, José Pereira, Luís Rodrigues. Proc. 28th IEEE International Symposium on Reliable Distributed Systems (SRDS’09).
Spatial gossip and resource location protocols. David Kempe, Jon Kleinberg, Alan Demers. Journal of the ACM (JACM) 51: 6 (Nov 2004).
Gossip-Based Computation of Aggregate Information. David Kempe, Alin Dobra, Johannes Gehrke. Proc. 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS). 2003.
Active and Passive Techniques for Group Size Estimation in Large-Scale and Dynamic Distributed Systems. Dionysios Kostoulas, Dimitrios Psaltoulis, Indranil Gupta, Ken Birman, Al Demers. Elsevier Journal of Systems and Software, 2007.
Build One, Get One Free: Leveraging the Coexistence of Multiple P2P Overlay Networks. Balasubramaneyam Maniymaran, Marin Bertier and Anne-Marie Kermarrec. Proc. ICDCS, June 2007.
Peer counting and sampling in overlay networks: random walk methods. Laurent Massoulié, Erwan Le Merrer, Anne-Marie Kermarrec, Ayalvadi Ganesh. Proc. 25th ACM PODC. Denver, 2006.
Chord on Demand. Alberto Montresor, Márk Jelasity, and Ozalp Babaoglu. Proc. 5th Conference on Peer-to-Peer Computing (P2P), Konstanz, Germany, August 2005.
Introduction to Expander Graphs. Michael Nielsen. https://pdfs.semanticscholar.org/4c8a/e0bc0dca940264b7ed21fa58f826937f7b12.pdf Архивная копия от 23 февраля 2019 на Wayback Machine. Technical report, June 2005.
Building low-diameter P2P networks. G. Pandurangan, P. Raghavan, Eli Upfal. In Proceedings of the 42nd Symposium on Foundations of Computer Science (FOCS), 2001.
Astrolabe: A Robust and Scalable Technology for Distributed System Monitoring, Management, and Data Mining. Robbert van Renesse, Kenneth Birman and Werner Vogels. ACM Transactions on Computer Systems (TOCS) 21:2, May 2003.
Exploiting Semantic Proximity in Peer-to-peer Content Searching. S. Voulgaris, A.-M. Kermarrec, L. Massoulie, M. van Steen. Proc. 10th Int’l Workshop on Future Trends in Distributed Computing Systems (FTDCS 2004), Suzhou, China, May 2004.

Литература по математической стороне вопроса:

Reputation aggregation in peer-to-peer network using differential gossip algorithm. R. Gupta, Y. N. Singh. CoRR, vol. abs/1210.4301, 2012.
The Mathematical Theory of Epidemics. N.J.T. Bailey, 1957. Griffen Press.

Примечания править

↑ Alan Demers, Dan Greene, Carl Hauser, Wes Irish, John Larson. Epidemic algorithms for replicated database maintenance (англ.) // Proceedings of the sixth annual ACM Symposium on Principles of distributed computing - PODC '87. — Vancouver, British Columbia, Canada: ACM Press, 1987. — P. 1–12. — doi:10.1145/41840.41841.

[1] Alan Demers, Dan Greene, Carl Hauser, Wes Irish, John Larson. Epidemic algorithms for replicated database maintenance (англ.) // Proceedings of the sixth annual ACM Symposium on Principles of distributed computing - PODC '87. — Vancouver, British Columbia, Canada: ACM Press, 1987. — P. 1–12. — doi:10.1145/41840.41841.

[1]