Войти
A протокол сплетен - это процедура или процесс одноранговой компьютерной связи, основанный на способе распространения эпидемий. Некоторые распределенные системы используют одноранговые сплетни, чтобы гарантировать, что данные распространяются среди всех членов группы. Некоторые специализированные сети не имеют центрального реестра, и единственный способ распространять общие данные - это полагаться на то, что каждый участник передает их своим соседям.
Термин эпидемический протокол иногда используется как синоним протокола сплетен, поскольку сплетни распространяют информацию аналогично распространению вируса в биологическом сообщество.
Концепция общения сплетен может быть проиллюстрирована аналогией с офисными работниками, распространяющими слухи. Допустим, каждый час офисные работники собираются вокруг кулера с водой. Каждый сотрудник объединяется с другим, выбранным наугад, и делится последними сплетнями. В начале дня Дэйв запускает новый слух: он комментирует Бобу, что, по его мнению, Чарли красит ему усы. На следующей встрече Боб рассказывает Алисе, а Дэйв повторяет эту идею Еве. После каждого свидания с кулером количество людей, которые слышали слух, примерно удваивается (хотя это не учитывает сплетни дважды с одним и тем же человеком; возможно, Дэйв пытается рассказать эту историю Фрэнку, но обнаруживает, что Фрэнк уже слышал ее. от Алисы). Компьютерные системы обычно реализуют этот тип протокола в форме случайного «однорангового выбора»: с заданной частотой каждая машина случайным образом выбирает другую машину и распространяет горячие слухи.
Проблема с термином «сплетни» заключается в том, что качество обслуживания (то есть полное и своевременное распространение) основывается на требовании, чтобы каждый участник не дискриминировал и обеспечивал быструю и надежную передачу данных каждому члену их собственная одноранговая сеть. В реальном сценарии офисных сплетен не все причастны к распространяемым сплетням. Сплетни, в отличие от трансляции, носят дискриминационный характер, и участники часто не участвуют в жизненно важных или важных коммуникациях. Таким образом, сравнение с «офисными сплетнями» не так хорошо, как сравнение с распространением эпидемии. Тем не менее, метод однорангового общения иногда называют «сплетнями».
Вероятно, существуют сотни вариантов конкретных протоколов, подобных сплетням, потому что каждый сценарий использования, вероятно, будет адаптирован к конкретным потребностям организации.
Например, протокол сплетен может использовать некоторые из этих идей:
Полезно различать два преобладающих стиля протокола сплетен:
Многие протоколы, которые предшествовали самому раннему использованию термина « сплетни "подпадают под это довольно всеобъемлющее определение. Например, протоколы маршрутизации Интернет часто используют обмен информацией, напоминающий сплетни. Подложка для сплетен может использоваться для реализации стандартной маршрутизируемой сети: узлы «сплетничают» о традиционных двухточечных сообщениях, эффективно проталкивая трафик через слой сплетен. При наличии пропускной способности это означает, что система сплетен потенциально может поддерживать любой классический протокол или реализовывать любую классическую распределенную службу. Однако такая широкая инклюзивная интерпретация предназначена редко. Чаще всего используются протоколы сплетен, которые специально работают регулярно, периодически, относительно лениво, симметрично и децентрализованно; особенно характерна высокая степень симметрии между узлами. Таким образом, хотя можно было запустить протокол двухэтапной фиксации поверх основы сплетен, это противоречило бы духу, если не формулировке, определения.
Термин «конвергентно согласованный» иногда используется для описания протоколов, обеспечивающих экспоненциально быстрое распространение информации. Для этой цели протокол должен распространять любую новую информацию на все узлы, которые будут затронуты информацией в пределах времени, логарифмического по размеру системы («время смешивания» должно быть логарифмическим по размеру системы).
Предположим, мы хотим найти объект, который наиболее точно соответствует некоторому шаблону поиска, в сети неизвестного размера, но где компьютеры связаны друг с другом и где каждая машина запуск небольшой агентской программы, реализующей протокол сплетен.
Если сообщения могут стать большими (например, если одновременно выполняется много поисковых запросов), следует ввести ограничение на размер. Кроме того, поисковые запросы должны «устаревать» в сети.
Отсюда следует, что в течение логарифмического времени от размера сети (количества агентов) любая новая строка поиска достигнет всех агентов. В течение дополнительной задержки такой же приблизительной продолжительности каждый агент узнает, где можно найти наилучшее совпадение. В частности, агент, запустивший поиск, найдет лучшее совпадение.
Например, в сети из 25 000 машин мы можем найти лучшее совпадение примерно после 30 раундов сплетен: 15 для распространения строки поиска и еще 15 для обнаружения наилучшего совпадения. Обмен сплетнями может происходить так часто, как раз в десятую долю секунды, без чрезмерной нагрузки, поэтому этот вид сетевого поиска может обыскивать большой центр обработки данных примерно за 3 секунды.
В этом сценарии поисковые запросы могут автоматически исчезнуть из сети, скажем, через 10 секунд. К тому времени инициатор знает ответ, и нет смысла продолжать сплетничать об этом поиске.
Протоколы слухов также использовались для достижения и поддержания распределенной базы данных согласованности или с другими типами данных в согласованных состояниях, подсчитывая количество узлов в сети неизвестный размер, надежное распространение новостей, организация узлов в соответствии с некоторой политикой структурирования, построение так называемых оверлейных сетей, вычисление агрегатов, сортировка узлов в сети, выбор лидеров и т. д.
Протоколы сплетен могут использоваться для распространения информации способом, очень похожим на способ распространения вирусной инфекции в биологической популяции. Действительно, математика эпидемий часто используется для моделирования математики сплетен. Термин «эпидемический алгоритм» иногда используется при описании программной системы, в которой используется этот вид распространения информации на основе сплетен.
Вот несколько дополнительных ссылок на недавние работы сообщества сплетников. Работа Демерса рассматривается большинством исследователей как первая, кто действительно признал силу этих протоколов и предложил формальный подход к сплетням.
Хотя этот учебник старый, многие исследователи сплетен ссылаются на него как на авторитетный источник информации о математическом моделировании сплетен и протоколов эпидемий:
