Протокол сплетен

Концепция в вычислительной технике

Протокол сплетен или эпидемический протокол — это процедура или процесс компьютерной пиринговой связи, основанный на способе распространения эпидемий . ^[1] Некоторые распределенные системы используют пиринговые сплетни, чтобы гарантировать, что данные будут распространены среди всех членов группы. Некоторые сети ad hoc не имеют центрального реестра, и единственный способ распространения общих данных — полагаться на то, что каждый член передаст их своим соседям.

Коммуникация

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

Варианты и стили

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

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

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

Типы протоколов

Полезно различать два преобладающих стиля протокола сплетен: ^[2]

• Протоколы распространения (или протоколы распространения слухов). Они используют сплетни для распространения информации; в основном они работают путем затопления агентов в сети, но таким образом, что создают ограниченные нагрузки в худшем случае:
  1. Протоколы распространения событий используют сплетни для выполнения многоадресных рассылок . Они сообщают о событиях, но сплетни происходят периодически, и события фактически не запускают сплетни. Одной из проблем здесь является потенциально высокая задержка с момента возникновения события до его доставки.
  2. Протоколы распространения фоновых данных постоянно сплетничают об информации, связанной с участвующими узлами. Обычно задержка распространения не вызывает беспокойства, возможно, потому, что рассматриваемая информация меняется медленно или нет существенного штрафа за действия на основе слегка устаревших данных.
• Протоколы, вычисляющие агрегаты . Они вычисляют общесетевой агрегат путем выборки информации в узлах сети и объединения значений для получения общесистемного значения — наибольшее значение для некоторых узлов измерения, наименьшее и т. д. Ключевым требованием является то, что агрегат должен быть вычислимым с помощью парных обменов информацией фиксированного размера; они обычно заканчиваются после нескольких раундов обмена информацией, логарифмических по размеру системы, к тому времени, когда будет установлена ​​схема потока информации «все ко всем». В качестве побочного эффекта агрегации можно решать другие виды задач с помощью сплетен; например, существуют протоколы сплетен, которые могут упорядочивать узлы в наложении сплетен в список, отсортированный по идентификатору узла (или какому-либо другому атрибуту) за логарифмическое время с использованием обмена информацией в стиле агрегации. Аналогично существуют алгоритмы сплетен, которые упорядочивают узлы в дерево и вычисляют агрегаты, такие как «сумма» или «количество», сплетничая по шаблону, смещенному для соответствия структуре дерева.

Многие протоколы, которые предшествовали самому раннему использованию термина «сплетня», попадают в это довольно всеобъемлющее определение. Например, протоколы маршрутизации Интернета часто используют обмен информацией, похожий на сплетни. Субстрат сплетен может использоваться для реализации стандартной маршрутизируемой сети: узлы «сплетничают» о традиционных сообщениях точка-точка, эффективно проталкивая трафик через уровень сплетен. Если позволяет пропускная способность, это означает, что система сплетен потенциально может поддерживать любой классический протокол или реализовывать любую классическую распределенную службу. Однако такая широко всеобъемлющая интерпретация редко подразумевается. Более типичными протоколами сплетен являются те, которые специально работают в регулярной, периодической, относительно ленивой, симметричной и децентрализованной манере; высокая степень симметрии между узлами особенно характерна. Таким образом, хотя можно было бы запустить протокол двухфазной фиксации на субстрате сплетен, это противоречило бы духу, если не формулировке, определения.

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

Примеры

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

• Чтобы начать поиск, пользователь должен попросить локального агента начать распространять информацию о строке поиска. (Мы предполагаем, что агенты либо начинают с известного списка пиров, либо извлекают эту информацию из какого-то общего хранилища.)
• Периодически, с некоторой скоростью (скажем, десять раз в секунду, для простоты), каждый агент выбирает другого агента наугад и сплетничает с ним. Строки поиска, известные A, теперь будут известны и B, и наоборот. В следующем «раунде» сплетен A и B выберут дополнительных случайных пиров, возможно, C и D. Это явление удвоения раунд за раундом делает протокол очень надежным, даже если некоторые сообщения теряются или некоторые из выбранных пиров являются теми же или уже знают о строке поиска.
• Получив строку поиска в первый раз, каждый агент проверяет свой локальный компьютер на наличие соответствующих документов.
• Агенты также сплетничают о лучшем совпадении на сегодняшний день. Таким образом, если A сплетничает с B, после взаимодействия A узнает о лучших совпадениях, известных B, и наоборот. Лучшие совпадения будут «распространяться» по сети.

Если сообщения могут стать большими (например, если одновременно активны многие поиски), следует ввести ограничение на размер. Кроме того, поиски должны «стареть» в сети.

Из этого следует, что в течение логарифмического времени по размеру сети (количества агентов) любая новая строка поиска достигнет всех агентов. В течение дополнительной задержки той же приблизительной длины каждый агент узнает, где можно найти наилучшее совпадение. В частности, агент, который начал поиск, найдет наилучшее совпадение.

Например, в сети с 25 000 машин мы можем найти лучшее совпадение примерно после 30 раундов сплетен: 15 для распространения строки поиска и еще 15 для обнаружения лучшего совпадения. Обмен сплетнями может происходить так часто, как раз в десятую долю секунды, не создавая чрезмерной нагрузки, поэтому эта форма сетевого поиска может обыскать большой центр обработки данных примерно за три секунды.

В этом сценарии поиски могут автоматически устаревать в сети, скажем, через 10 секунд. К тому времени инициатор знает ответ, и нет смысла продолжать сплетничать об этом поиске.

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

Эпидемические алгоритмы

Протоколы сплетен могут использоваться для распространения информации способом, довольно похожим на тот, которым вирусная инфекция распространяется в биологической популяции. Действительно, математика эпидемий часто используется для моделирования математики сплетен. Термин « алгоритм эпидемии» иногда используется при описании программной системы, в которой используется этот вид распространения информации на основе сплетен.

Смотрите также

• Протоколы Gossip — это всего лишь один класс среди многих классов сетевых протоколов. См. также виртуальную синхронность , распределенные конечные автоматы , алгоритм Paxos , транзакции баз данных . Каждый класс содержит десятки или даже сотни протоколов, различающихся по деталям и свойствам производительности, но схожих на уровне гарантий, предлагаемых пользователям.
• Некоторые протоколы сплетен заменяют механизм случайного выбора пиров более детерминированной схемой. Например, в алгоритме NeighbourCast вместо общения со случайными узлами информация распространяется путем общения только с соседними узлами. Существует ряд алгоритмов, использующих схожие идеи. Ключевым требованием при проектировании таких протоколов является то, чтобы набор соседей трассировал граф экспандера .
• Маршрутизация
• Tribler , одноранговый клиент BitTorrent, использующий протокол Gossip.

Ссылки

1. Демерс, Алан; Грин, Дэн; Хаузер, Карл; Айриш, Уэс; Ларсон, Джон (1987). "Эпидемические алгоритмы для обслуживания реплицированных баз данных". Труды шестого ежегодного симпозиума ACM по принципам распределенных вычислений - PODC '87 . стр. 1–12. doi :10.1145/41840.41841. ISBN 978-0-89791-239-6. OCLC  8876960204. S2CID  1889203.
2. Jelasity, Márk (2011-01-01). "Gossip" (PDF) . В Serugendo, Giovanna Di Marzo; Gleizes, Marie-Pierre; Karageorgos, Anthony (ред.). Самоорганизующееся программное обеспечение . Серия Natural Computing. Springer Berlin Heidelberg. стр. 139–162. doi :10.1007/978-3-642-17348-6_7. ISBN 978-3-642-17347-9. S2CID  214970849.

Дальнейшее чтение

• Аллавена, Андре; Демерс, Алан; Хопкрофт, Джон Э. (2005). "Корректность протокола членства на основе сплетен". Труды двадцать четвертого ежегодного симпозиума ACM SIGACT-SIGOPS по принципам распределенных вычислений - PODC '05 . стр. 292. doi :10.1145/1073814.1073871. ISBN 978-1-58113-994-5. OCLC  8876665695. S2CID  9378092.
• Бирман, Кеннет П.; Хейден, Марк; Озкасап, Ознур; Сяо, Чжэнь; Будиу, Михай; Минский, Ярон (май 1999 г.). «Бимодальная многоадресная передача». ACM Transactions on Computer Systems . 17 (2): 41–88. doi : 10.1145/312203.312207 . S2CID  207744063.
• Eugster, P. Th.; Guerraoui, R.; Handurukande, SB; Kouznetsov, P.; Kermarrec, A.-M. (ноябрь 2003 г.). "Легковесная вероятностная трансляция" (PDF) . ACM Transactions on Computer Systems . 21 (4): 341–374. doi :10.1145/945506.945507. S2CID  6875620.
• Gupta, Indranil; Birman, Ken; Linga, Prakash; Demers, Al; Van Renesse, Robbert (2003). "Kelips: Building an Efficient and Stable P2P DHT through Increased Memory and Background Overhead". Peer-to-Peer Systems II . Lecture Notes in Computer Science. Vol. 2735. pp. 160–169. doi :10.1007/978-3-540-45172-3_15. ISBN 978-3-540-40724-9.
• Систематическое проектирование технологий P2P для распределенных систем. Индранил Гупта, Глобальное управление данными, ред.: Р. Балдони, Дж. Кортезе, Ф. Давиде и А. Мельпиньяно, 2006.
• Leitao, Joao; Pereira, Jose; Rodrigues, Luis (2007). "HyPar View : протокол членства для надежного вещания на основе сплетен". 37-я ежегодная международная конференция IEEE/IFIP по надежным системам и сетям (DSN'07) . стр. 419–429. doi :10.1109/DSN.2007.56. hdl :1822/38895. ISBN 978-0-7695-2855-7. S2CID  9060122.
• Gupta, I.; Kermarrec, A.-M.; Ganesh, AJ (июль 2006 г.). «Эффективные и адаптивные эпидемические протоколы для надежной и масштабируемой многоадресной передачи». IEEE Transactions on Parallel and Distributed Systems . 17 (7): 593–605. doi :10.1109/TPDS.2006.85. S2CID  1148979.
• Джеласити, Марк; Монтресор, Альберто; Бабаоглу, Озалп (август 2009 г.). «T-Man: быстрое построение топологии наложения на основе сплетен» (PDF) . Компьютерные сети . 53 (13): 2321–2339. doi :10.1016/j.comnet.2009.03.013.
• Лейтао, Жоао; Перейра, Хосе; Родригес, Луис (2007). «Деревья эпидемического вещания». 2007 26-й Международный симпозиум IEEE по надежным распределенным системам (SRDS 2007) . стр. 301–310. doi :10.1109/SRDS.2007.27. hdl :1822/38894. ISBN 978-0-7695-2995-0. S2CID  7210467.
• Джеласити, Марк; Монтресор, Альберто; Бабаоглу, Озалп (август 2005 г.). «Агрегация на основе сплетен в больших динамических сетях» (PDF) . ACM Transactions on Computer Systems . 23 (3): 219–252. doi :10.1145/1082469.1082470. S2CID  2608879.
• Упорядоченное нарезание очень больших оверлейных сетей. Марк Джеласити и Энн-Мари Кермаррек. IEEE P2P, 2006.
• Топологии суперпиров с наложением, учитывающие близость. Джан Паоло Джеси, Альберто Монтресор и Озалп Бабаоглу. Труды IEEE по управлению сетями и службами, 4(2):74–83, сентябрь 2007 г.
• X-BOT: протокол устойчивой оптимизации неструктурированных наложений. Жоау Лейтан, Жоау Маркеш, Жозе Перейра, Луис Родригеш. Учеб. 28-й Международный симпозиум IEEE по надежным распределенным системам (SRDS'09).
• Пространственные сплетни и протоколы определения местоположения ресурсов. Дэвид Кемпе, Джон Клейнберг, Алан Демерс. Журнал ACM (JACM) 51: 6 (ноябрь 2004 г.).
• Вычисление совокупной информации на основе слухов. Дэвид Кемпе, Алин Добра, Йоханнес Герке. Труды 44-го ежегодного симпозиума IEEE по основам компьютерной науки (FOCS). 2003.
• Активные и пассивные методы оценки размера группы в крупномасштабных и динамических распределенных системах. Дионисиос Костулас, Димитриос Псалтулис, Индранил Гупта, Кен Бирман, Эл Демерс. Elsevier Journal of Systems and Software , 2007.
• Создай один, получи второй бесплатно: использование сосуществования нескольких сетей P2P Overlay. Баласубраманейам Маниймаран, Марин Бертье и Энн-Мари Кермаррек. Proc. ICDCS , июнь 2007 г.
• Подсчет и выборка пиров в оверлейных сетях: методы случайного блуждания. Лоран Массулье, Эрван Ле Меррер, Энн-Мари Кермаррек, Айалвади Ганеш. Труды 25-го ACM PODC . Денвер, 2006.
• Chord on Demand. Альберто Монтресор, Марк Джеласити и Озалп Бабаоглу. Труды 5-й конференции по пиринговым вычислениям (P2P), Констанц, Германия, август 2005 г.
• Нильсен, Майкл А. (2005). "Введение в экспандерные графы" (PDF) . Майкл Нильсен . S2CID  3045708. Архивировано из оригинала (PDF) 2011-07-15.
• Построение сетей P2P с малым диаметром. G. Pandurangan, P. Raghavan, Eli Upfal . В трудах 42-го симпозиума по основам компьютерной науки (FOCS), 2001.
• Van Renesse, Robbert; Birman, Kenneth P.; Vogels, Werner (май 2003 г.). «Astrolabe: надежная и масштабируемая технология для мониторинга, управления и анализа данных распределенных систем». ACM Transactions on Computer Systems . 21 (2): 164–206. doi :10.1145/762483.762485. S2CID  6204358.
• Voulgaris, S.; Kermarrec, A.-M.; Massoulie, L.; Van Steen, M. (2004). «Использование семантической близости в одноранговом поиске контента». Труды. 10-й Международный семинар IEEE по будущим тенденциям распределенных вычислительных систем, 2004. FTDCS 2004. стр. 238–243. doi :10.1109/FTDCS.2004.1316622. hdl :1871/12832. ISBN 0-7695-2118-5. S2CID  9464168.
• Гупта, Ручир; Сингх, Ятиндра Нат (2015). «Агрегация репутации в одноранговой сети с использованием алгоритма дифференциальных сплетен». Труды IEEE по знаниям и инжинирингу данных . 27 (10): 2812–2823. arXiv : 1210.4301 . doi : 10.1109/TKDE.2015.2427793. S2CID  650473.
• Бейли, Норман Т.Дж. (1957). Математическая теория эпидемий . Хафнер. ISBN 978-0-85264-113-2.