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.