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

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

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

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

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

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

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

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

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

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

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

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

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

Примеры

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

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

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

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

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

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

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

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

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

См. также

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

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

• Аллавена, Андре; Демерс, Алан; Хопкрофт, Джон Э. (2005). «Правильность протокола членства, основанного на сплетнях». Материалы двадцать четвертого ежегодного симпозиума ACM SIGACT-SIGOPS по принципам распределенных вычислений — PODC '05 . п. 292. дои : 10.1145/1073814.1073871 . ISBN  978-1-58113-994-5 . OCLC   8876665695 . S2CID   9378092 .
• Бирман, Кеннет П.; Хайден, Марк; Озкасап, Ознур; Сяо, Чжэнь; Будю, Михай; Мински, Ярон (май 1999 г.). «Бимодальная многоадресная рассылка» . Транзакции ACM в компьютерных системах . 17 (2): 41–88. дои : 10.1145/312203.312207 . S2CID   207744063 .
• Югстер, П.Т.; Геррауи, Р.; Хандуруканде, SB; Кузнецов П.; Кермаррек, А.-М. (ноябрь 2003 г.). «Облегченная вероятностная трансляция» (PDF) . Транзакции ACM в компьютерных системах . 21 (4): 341–374. дои : 10.1145/945506.945507 . S2CID   6875620 .
• Гупта, Индранил; Бирман, Кен; Линга, Пракаш; Демерс, Эл; Ван Ренесс, Робберт (2003). «Келипс: создание эффективного и стабильного P2P DHT за счет увеличения памяти и фоновых затрат». Одноранговые системы II . Конспекты лекций по информатике. Том. 2735. стр. 160–169. дои : 10.1007/978-3-540-45172-3_15 . ISBN  978-3-540-40724-9 .
• Систематическое проектирование P2P-технологий для распределенных систем. Индранил Гупта, Глобальное управление данными, ред.: Р. Бальдони, Дж. Кортезе, Ф. Давиде и А. Мельпиньяно, 2006 г.
• Лейтао, Жоао; Перейра, Хосе; Родригес, Луис (2007). «HyPar View : протокол членства для надежного вещания на основе сплетен». 37-я ежегодная Международная конференция IEEE/IFIP по надежным системам и сетям (DSN'07) . стр. 419–429. дои : 10.1109/DSN.2007.56 . hdl : 1822/38895 . ISBN  978-0-7695-2855-7 . S2CID   9060122 .
• Гупта, И.; Кермаррек, А.-М.; Ганеш, AJ (июль 2006 г.). «Эффективные и адаптивные протоколы эпидемического типа для надежной и масштабируемой многоадресной рассылки». Транзакции IEEE в параллельных и распределенных системах . 17 (7): 593–605. дои : 10.1109/TPDS.2006.85 . S2CID   1148979 .
• Йеласити, Марк; Монтрезор, Альберто; Бабаоглу, Озалп (август 2009 г.). «T-Man: быстрое построение топологии наложения на основе сплетен» (PDF) . Компьютерные сети . 53 (13): 2321–2339. дои : 10.1016/j.comnet.2009.03.013 .
• Лейтао, Жоао; Перейра, Хосе; Родригес, Луис (2007). «Деревья эпидемической трансляции». 2007 26-й Международный симпозиум IEEE по надежным распределенным системам (SRDS 2007) . стр. 301–310. дои : 10.1109/SRDS.2007.27 . hdl : 1822/38894 . ISBN  978-0-7695-2995-0 . S2CID   7210467 .
• Йеласити, Марк; Монтрезор, Альберто; Бабаоглу, Озалп (август 2005 г.). «Агрегация на основе сплетен в больших динамических сетях» (PDF) . Транзакции ACM в компьютерных системах . 23 (3): 219–252. дои : 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 о системах и программном обеспечении , 2007.
• Создайте один, получите один бесплатно: использование сосуществования нескольких оверлейных сетей P2P. Баласубраманеям Маниймаран, Марин Бертье и Анн-Мари Кермаррек. Учеб. ICDCS , июнь 2007 г.
• Подсчет одноранговых узлов и выборка в оверлейных сетях: методы случайного блуждания. Лоран Массули, Эрван Ле Меррер, Анн-Мари Кермаррек, Аялвади Ганеш. Учеб. ACM 25-й ПОДК . Денвер, 2006 г.
• Аккорд по требованию. Альберто Монтресор, Марк Еласити и Озалп Бабаоглу. Учеб. 5-я конференция по одноранговым вычислениям (P2P), Констанц, Германия, август 2005 г.
• Нильсен, Майкл А. (2005). «Введение в графы-расширители» (PDF) . Майкл Нильсен . S2CID   3045708 . Архивировано из оригинала (PDF) 15 июля 2011 г.
• Построение P2P-сетей малого диаметра. Г. Пандуранган, П. Рагхаван, Эли Упфал . В материалах 42-го симпозиума по основам информатики (FOCS), 2001.
• Ван Ренесс, Робберт; Бирман, Кеннет П.; Фогельс, Вернер (май 2003 г.). «Астролябия: надежная и масштабируемая технология для мониторинга, управления и анализа распределенных систем». Транзакции ACM в компьютерных системах . 21 (2): 164–206. дои : 10.1145/762483.762485 . S2CID   6204358 .
• Вулгарис, С.; Кермаррек, А.-М.; Массули, Л.; Ван Стин, М. (2004). «Использование семантической близости при одноранговом поиске контента». Слушания. 10-й международный семинар IEEE по будущим тенденциям распределенных вычислительных систем, 2004 г. FTDCS 2004 г. стр. 238–243. дои : 10.1109/FTDCS.2004.1316622 . hdl : 1871/12832 . ISBN  0-7695-2118-5 . S2CID   9464168 .
• Гупта, Ручир; Сингх, Ятиндра Натх (2015). «Агрегация репутации в одноранговой сети с использованием алгоритма дифференциальных сплетен». Транзакции IEEE по знаниям и инженерии данных . 27 (10): 2812–2823. arXiv : 1210.4301 . дои : 10.1109/TKDE.2015.2427793 . S2CID   650473 .
• Бейли, Норман Ти Джей (1957). Математическая теория эпидемий . Хафнер. ISBN  978-0-85264-113-2 .