алгоритм голосования в распределенных системах

предположим сеть распределенных систем. Каждая система измеряет значение. Существует правильное решение, которое должно быть принято консенсусом всеми системами в зависимости от всех значений. коммуникационные каналы могут обрываться. Есть ли алгоритм голосования и синхронизации для этого случая?


synchronization algorithm distributed-system voting consensus
person beni    schedule 10.01.2015    source источник
comment
Из скольких взаимоисключающих вариантов можно выбрать? Это решение типа пожара ядерной бомбы или имя вашего любимого актера-ребенка?   -  person dwn    schedule 10.01.2015
comment
Привет. Все системы находятся в некотором состоянии (например, А). Каждая система может обнаружить проблему и предложить изменить состояние с текущего (например, A) на другое (например, B). Другие правильные системы могут ответить, что согласны, или сочтут это плохой идеей. Основываясь на весе каждой системы и их ответах, все системы должны прийти к консенсусу, менять состояние или нет, и действовать в соответствии с ним. Система асинхронная, но можно предположить, что можно использовать тайм-ауты и добиться приемлемых результатов. Мы можем упростить, предположив сбои при сбоях (или сбоях связи). Существует вероятность того, что 2 системы будут предлагать разные состояния.   -  person beni    schedule 13.01.2015

Ответы (2)


arrow_upward
1
arrow_downward

Примеры алгоритма голосования в распределенных системах:

  1. Алгоритм запугивания (http://en.wikipedia.org/wiki/Bully_algorithm)
  2. Алгоритм Чанга и Робертса (http://en.wikipedia.org/wiki/Chang_and_Roberts_algorithm)
person sribin    schedule 23.01.2015

arrow_upward
1
arrow_downward

Я решил аналогичную проблему. Это схема обнаружения сбоев, поэтому я буду описывать ее в этих терминах, а не в общих терминах OP.

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

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

Когда принимается решение (в нашем случае - объявление клиента мертвым), на любом из серверов есть сносно актуальная таблица всех сердцебиений клиента. Любой сервер волен принимать решение, что мы и делаем через протокол консенсуса между собой (Paxos или Raft). Учтите, что сервер может ошибиться в своем решении, но маловероятно, что у него нет обновленной таблицы, но все же успешно проведен раунд Paxos.

person Michael Deardeuff    schedule 10.02.2015
comment
спасибо, Майкл. Я изучу ваш ответ и, надеюсь, он будет иметь смысл для моей проблемы. - person beni; 18.02.2015