Алгоритм paxos - как работает этап предложения?

Я смотрю на псевдокод для этапа PROPOSE алгоритма paxos: https://www.cs.rutgers.edu/%7Epxk/417/notes/paxos.html

did I receive PROMISE responses from a majority of acceptors?
if yes
    do any responses contain accepted values (from other proposals)?
    if yes
        val = accepted_VALUE    // value from PROMISE message with the highest accepted ID
    if no
        val = VALUE     // we can use our proposed value
    send PROPOSE(ID, val) to at least a majority of acceptors

Если один из партнеров ранее принял значение (accepted_VALUE), что произойдет со значением, которое предлагает предложить (VALUE)?

Насколько я понимаю, глядя на псевдокод, он отбрасывается? Это похоже на потерю информации ...


distributed-computing distributed-system paxos
person nz_21    schedule 07.12.2020    source источник

Ответы (1)


arrow_upward
1
arrow_downward

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

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

В том же ключе вы можете думать об этом, как о том, что предлагающий продолжает работу предыдущего, потенциально мертвого предлагающего.

Вы можете увидеть это более четко в более простом, неконсенсусном протоколе Аттия / Бар-Ноя / Долева (ABD). Даже при чтении в ABD предлагающий повторно записывает значение партнерам, чтобы гарантировать, что значение распределено по системе.

ABD: Надежное совместное использование памяти в системах передачи сообщений, Х. Аттия, А. Бар-Ной и Д. Долев, 1995.

person Michael Deardeuff    schedule 08.12.2020
comment
Спасибо за объяснение. Я все еще немного запутался. Если бы кто-то строил магазин кв на базе paxos, как бы вы удостоверились, что все ключи правильно учтены? Как вы справляетесь с неизбранными ценностями? - person nz_21; 08.12.2020
comment
@ nz_21 Думайте о каждом экземпляре Paxos как о выборе одной записи в журнале упреждающей записи (WAL), а НЕ как о том, что хранит значения в базе данных. value, выбранное в каждом экземпляре paxos, будет большим двоичным объектом, представляющим полную транзакцию, даже с изменением нескольких строк. Таким образом, выбранное значение paxos будет примерно таким: SET x=1, y=2 where id=123; SET x=4, y=3 where id=456; - person Michael Deardeuff; 08.12.2020