2013-11-07 5 views
4

В Паксосе сделан простой Лампорта описывает Фазу 2 (а) алгоритма следующим образом:Что такое «ценность предложения с наивысшим номером» в алгоритме Paxos?

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

  • Означает ли это, что может послать предлагающую принять запрос, как только он собрал ответ от большинства акцепторов, независимо от их количества предложения? (Я считаю, что подчеркнутая часть цитаты подразумевает это, потому что все предложения с одинаковыми номерами должны иметь одинаковую ценность, не так ли?)
  • Или разработчику нужны ответы с тем же предложением № от большинства акцепторов ? (Это означает, что ответы с числовым м (будучи менее п) не засчитываются большинство для ответов пронумерованного п)

ответ

3

Означает ли это, что заявитель может отправить заявку на прием, как только он соберет ответ от большинства акцепторов независимо от их номеров предложений? (Я считаю, подчеркнутую часть цитаты подразумевает так, потому что все одинаково пронумерованные предложения должны иметь такое же значение, верно?)

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

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

Вот пример.Предположим, что предлагающий отправляет Propose(4) пяти акцепторам и получает обратно Ack(abc, 2), Ack(abc, 2) и Ack(xyz, 3) его должен отправить Accept(xyz, 4).

+0

Вы написали 'tell the acceptor, значение которого нужно отправить в запрос accept'. Глядя на [здесь] (http://en.wikipedia.org/wiki/Paxos_ (computer_science) #Message_flow: _Basic_Paxos), мне кажется, что предложение отправляет запросы на прием? Можете ли вы прокомментировать это? –

+0

Вы правы; глупая опечатка. Исправлена. –

2

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

Ответ содержит номер предложения и принятое число. В ответе номер предложения совпадает с предложением, а принятый номер - тот, который принял ранее принимающий.

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

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