Тут на досуге вдруг подумал, а как устроен алгоритм выбора хоста-лидера в простой локальной сети. Условия задачи:
В простой локальной сети (допустим рассматривает единый сегмент) появляются и исчезают хосты. Хосты изначально не знают о существовании друг-друга и сколько их. В каждый момент времени среди них должен быть только один хост-лидер.
Какие вообще существуют подходы к решению данной задачи? Если можно, объясните на пальцах принципы ну или почему данная задача не решаема в общем виде.

Здравствуйте, Videoman, Вы писали:

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

Для начала, зачем вообще нужен лидер в локальной сети?

А так, посмотри на consensus algorithms. Начни с википедии: https://en.wikipedia.org/wiki/Consensus_(computer_science)

Здравствуйте, Pzz, Вы писали:

Pzz>Для начала, зачем вообще нужен лидер в локальной сети?

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

Pzz>А так, посмотри на consensus algorithms. Начни с википедии: https://en.wikipedia.org/wiki/Consensus_(computer_science)

Спасибо, посмотрю конечно, если так всё сложно. Есть надежда, может кто решал уже похожую задачу и даст советы, какие подходы работают, какие нет.

спроецируйте текущую политическую обстановку в мире на алгоритм
и станет понятно кто такой лидер, кем определяется и почему другие с ним согласуются
вот и весь алго консенсуса

Не знаю как это делается в сетях, но можно обратить внимание на алгоритмы, которые применяются в распределенных системах (что в БД, что в СааСах) при выборе/назначении главного/мастер сервера и репликаций/запасного/слейва.

Например, вот https://cseweb.ucsd.edu/classes/sp16/cse291-e/applications/ln/lecture6.html. Хорошая такая статья с описанием алгоритмов, расписанными формулами и картинками.

Дальше гуглить по словам distributed systems master slave election, distributed systems failover election.

Здравствуйте, Videoman, Вы писали:

Pzz>>Для начала, зачем вообще нужен лидер в локальной сети?

V>Допустим задача такая. Есть несколько узлов, лидер реплицирует на них какие-то данные, узлы с данными работают. Нужно что бы в случае остановки или выхода из строя лидирующего узла, его место занял другой узел и делал бы тоже самое.

Многое зависит от того, сколько у тебя этих данных, и что это за данные. Возможно, есть смысл, чтобы каждый просто сам отвечал свои данные (так работает ARP и мултикастный DNS), или чтобы у всех была копия с распределенной синхронизацией.

Pzz>>А так, посмотри на consensus algorithms. Начни с википедии: https://en.wikipedia.org/wiki/Consensus_(computer_science)

V>Спасибо, посмотрю конечно, если так всё сложно. Есть надежда, может кто решал уже похожую задачу и даст советы, какие подходы работают, какие нет.

Бывают распределенные базы данных. Они все это делают, а заодно и данные хранят.

В целом, да, p2p — это сложно.

Здравствуйте, reversecode, Вы писали:

R>
R>спроецируйте текущую политическую обстановку в мире на алгоритм
R>и станет понятно кто такой лидер, кем определяется и почему другие с ним согласуются
R>вот и весь алго консенсуса

Да, как обычно у тебя, все настолько просто что даже не стоит об этом писать, херня-война, и т.д. и т.п. ... Не грусти, лидер по ходу словил "альцгеймера" и перестал слать кип-алайф.

Здравствуйте, Videoman, Вы писали:

V>Тут на досуге вдруг подумал, а как устроен алгоритм выбора хоста-лидера в простой локальной сети. Условия задачи:
V>В простой локальной сети (допустим рассматривает единый сегмент) появляются и исчезают хосты. Хосты изначально не знают о существовании друг-друга и сколько их. В каждый момент времени среди них должен быть только один хост-лидер.
V>Какие вообще существуют подходы к решению данной задачи? Если можно, объясните на пальцах принципы ну или почему данная задача не решаема в общем виде.

Гуглите, см. на ютубе, лекции по paxos или raft.

отсутствие у вас абстрактного мышления это уже хуже чем проф не пригодность...

S>Гуглите, см. на ютубе, лекции по paxos или raft.

Это совсем уж далеко от изначально поставленной задачи: сии протоколы решают вопрос "какое значение записать в регистр, если предлагаются разные варианты".

Впрочем, изначальный вопрос вообще ничего о "выборе лидера" не содержит. Разве что о group membership, и то с натяжкой. Если бы автор конкретнее поставил вопрос "а зачем вообще в локальной сети нужен некий лидер", суть "какие функции эта машина выполняет", можно было бы порассуждать. Например, о примитивном bully election (который, в некотором роде, и используется в самых простых случаях, со всеми прилагающимися эффектами).

Здравствуйте, SkyDance, Вы писали:

S>>Гуглите, см. на ютубе, лекции по paxos или raft.

SD>Это совсем уж далеко от изначально поставленной задачи: сии протоколы решают вопрос "какое значение записать в регистр, если предлагаются разные варианты".

Ну а кто в конце концов решает какое значение записать? Лидер. Соотв. сначала надо выбрать лидера.

SD>Впрочем, изначальный вопрос вообще ничего о "выборе лидера" не содержит. Разве что о group membership, и то с натяжкой. Если бы автор конкретнее поставил вопрос "а зачем вообще в локальной сети нужен некий лидер", суть "какие функции эта машина выполняет", можно было бы порассуждать. Например, о примитивном bully election (который, в некотором роде, и используется в самых простых случаях, со всеми прилагающимися эффектами).

Вопрос вроде уточнили:

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

Как раз для paxos или raft задача.

S>Ну а кто в конце концов решает какое значение записать? Лидер. Соотв. сначала надо выбрать лидера.

Вы не совсем правильно понимаете терминологию. Какое значение записать решает клиент См. бумаги про роли (client, proposer, acceptor, learner). Лидера как такового вообще может и не быть, см. EPaxos и другие leader-less SMR. Более того, в Paxos нет понятия "лидер". Оно появляется в Multi-Paxos, примерно соответствуя идее "кэширования полномочий конкретного участника кворума на внесение предложений".

RAFT и Paxos по сути одно и то же. С минимальной разницей в содержании сообщения о перевыборах), а также в том, что бумага про RAFT написана для конкретной инженерной реализации (потому там рассматриваются вопросы snapshotting & log truncation).

S>Допустим задача такая. Есть несколько узлов, лидер реплицирует на них какие-то данные, узлы с данными работают. Нужно что бы в случае остановки или выхода из строя лидирующего узла, его место занял другой узел и делал бы тоже самое.

Это я как-то упустил. В такой постановке, да, действительно, Raft или multi-paxos (в зависимости от конкретики решаемой задачи).

S>Как раз для paxos или raft задача.

Задача уж очень рекурсивно поставлена
Ведь лидер с самого начала был как-то выбран, не? Иными словами, как делается bootstrap такого кластера из нескольких узлов? Как решается вопрос cluster membership? (Ответ, понятно, все в том же raft/multi-paxos, где записями лога является подтверждение membership).

Здравствуйте, SkyDance, Вы писали:

S>>Ну а кто в конце концов решает какое значение записать? Лидер. Соотв. сначала надо выбрать лидера.

SD>Вы не совсем правильно понимаете терминологию. Какое значение записать решает клиент См. бумаги про роли (client, proposer, acceptor, learner). Лидера как такового вообще может и не быть, см. EPaxos и другие leader-less SMR. Более того, в Paxos нет понятия "лидер". Оно появляется в Multi-Paxos, примерно соответствуя идее "кэширования полномочий конкретного участника кворума на внесение предложений".

Кто-то один на основе кворума должен выбрать значение, которое таки необходимо записать и разослать остальным участникам. И вроде этот кто-то лидер. Или не так?
А то я теория копал, но без практики или регулярной работы с этим, все забывается.

S>Кто-то один на основе кворума должен выбрать значение, которое таки необходимо записать и разослать остальным участникам. И вроде этот кто-то лидер. Или не так?

Не, не так. Значения записываются все. Лидер (если таковой есть) выбирает порядок (тот самый log изменений).

В общем случае лидера может и не быть. Есть, скажем, и такой вариант, когда клиент самостоятельно рассылает значения в "кворум" (варианты CASPaxos, RMWPaxos) безо всяких там лидеров, как на запись, так и на чтение. Впрочем, это все к оригинальному вопросу про SMR (state machine replication) совсем уж отдаленное отношение имеет. Вы правы в том смысле, что с уточненным заданием про "один лидер реплицирует все на кучу машин в локалке" нужен как раз MultiPaxos/Raft (это одно по сути одно и то же, разница только в технике перевыборов, и то небольшая, но Raft проще реализовать, там вообще 50 строк на эрланге на весь рафт нужно).