Как разобраться в Фазе 2 в алгоритме распределенного консенсуса Paxos?

Я вставил сюда псевдокод для алгоритма paxos:

Что такое представление в алгоритме консенсуса Paxos?

и было интересно, может ли кто-нибудь указать мне в правильном направлении.

Алгоритм говорит, что каждый узел имеет «состояние», которое содержит набор информации, которую узел должен отслеживать.

Предположим, у нас есть два узла: узел №1 и узел №2. В простейшем случае Node # 2 присоединяется к Node # 1, и они оба играют в paxos. Что именно происходит с состояниями Узла №1 и Узла №2 после того, как 2 присоединяются к 1? Когда меняется структура данных "просмотров" и что она содержит? Если кто-то может объяснить мне этот простой случай, когда два узла играют в paxos, то я думаю, что смогу выяснить случай с несколькими узлами.

Мое текущее понимание (которое, я уверен, неверно) таково:

  1. Узел №2 отправляет сообщение о присоединении к Узлу №1.
  2. Узел №1 получает сообщение от узла №2 с просьбой присоединиться.
  3. Узел № 1 принимает лидерство и переходит в фазу 1, вычисляет my_num = max (0,0) + 1 = 1
  4. Узел №1 отправляет все узлы в представлениях [0] (которые пусты) prepare (1,1)
  5. Узел # 1 отправляет начальный контактный узел (Узел # 2) prepare (1,1)
  6. Узел # 1 отправляет Узлу # 1 (сам) prepare (1,1)
  7. Узел № 2 получает команду prepare (1,1). Он устанавливает num_h = 1 и возвращает лидеру ОБЕЩАНИЕ (0, {пустой список})
  8. Узел № 1 получает prepare (1,1), устанавливает значение num_h = 1 и возвращает себе PROMISE (0, {пустой список}).

теперь мы переходим к фазе 2

Вот где я совершенно запутался.

Узел №1 является лидером и получает два сообщения ОБЕЩАНИЕ (0, {пустой список}). Согласно алгоритму, если лидер получает большинство обещаний в views [0], он может установить значение для «v» и отправить сообщение ACCEPT всем респондентам.

Что меня смущает, в настоящее время представления [0] для лидера пусты, так как же вы можете вычислить большую часть пустого списка?

Кроме того, предположим, что лидер получил большинство обещаний и приступает к установке v = набор проверяемых узлов (включая себя). Что такое узлы, доступные для проверки связи? Это только Узел №1 и Узел №2?

Буду признателен за любую / любую помощь и обязательно наградит тех, кто помогает.


distributed-computing algorithm consensus paxos
person user1068636    schedule 11.05.2012    source источник
comment
Возможно, список псевдокодов не очень хорош. Я посмотрел на страницу Paxos в Википедии, и она выглядела намного яснее, чем псевдокод ... В любом случае, просмотры [...] в псевдокоде никогда не являются набором. views - это карта от номера представления к выбранному значению в этом представлении. Я думаю, что утверждение большинства просто означает, что узел получает достаточно ОБЕЩАНИЙ на текущей фазе своего локального выполнения. Похоже, что псевдокод действительно пытается каким-то образом определиться с набором узлов. Но Paxos можно использовать для выбора любого значения (значений), а не только наборов узлов. Псевдокод специализируется на конкретной проблеме?   -  person Antti Huima    schedule 12.05.2012
comment
Вы читали исходный документ? За ним очень легко следить и довольно приятно; в отличие от любых других исследований в области информатики, которые вы когда-либо читали. В последующих статьях предлагалось внести несколько изменений для упрощения и / или расширения Paxos, но чтение этой оригинальной статьи даст вам твердое представление о принципах, лежащих в основе всего этого.   -  person erickson    schedule 12.05.2012
comment
Хорошо, спасибо, ребята. Думаю, это мне помогло. Но я полагаю, что никто из вас не опубликовал ответа, поэтому я не могу начислять баллы.   -  person user1068636    schedule 13.05.2012

Ответы (1)


arrow_upward
0
arrow_downward

Псевдокод не предназначен для решения конкретной проблемы. Фактически, профессор сказал, что нам не нужно использовать псевдокод, если мы этого не хотим, и сказал, что мы можем взглянуть на другие документы Paxos (например, paxos made simple, paxos made live и т. Д.) Для руководства по реализации этого алгоритма. . Может быть, вы правы, мне, наверное, стоит заглянуть в Википедию, чтобы реализовать этот алгоритм. Таким образом, views [..] - это просто хэш-карта, и узел может выбрать любое значение, которое пожелает. Если я правильно вас понял, вы говорите, что большинство операторов просто проверяет, получено ли "достаточно" сообщений ОБЕЩАНИЯ. Но единственный способ узнать, достаточно ли у нас, - это отслеживать ли узел членов своей группы. Это означает, что для этого мне нужна другая структура данных.

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

person user1068636    schedule 12.05.2012