Sprzeczność w prostym papierze Lamporta

Z pewnością nie ma problemu z wysłaniem żądania Akceptuj do wszystkich akceptantów. Nie musisz ograniczać go tylko do tych, które odpowiedziały na oryginalne żądanie przygotowania. Znalazłeś rzadki przypadek złego sformułowania w piśmie doktora Lamporta.

Jest jednak błąd w kontrprzykładu. Po pierwsze, zapis jest zdefiniowany w następujący sposób:

X(n:v,m) aby określić status akceptanta X: propozycja n:v jest największą ponumerowaną propozycją zaakceptowaną przez X

Ale potem w kroku 7 węzeł C ma stan C(100:b,-), a następnie w kroku 9 zmienia się na stan C(1:a,-). Nie jest to poprawne przejście: po zaakceptowaniu 1:a powinna pozostać w stanie C(100:b,-), ponieważ 100:b jest nadal największą ponumerowaną propozycją zaakceptowaną przez C.

Zauważ, że to jest w porządku, że akceptuje 1:a po 100:b, głównie dlatego, że sieć jest asynchroniczna, więc wszystkie wiadomości mogą być opóźnione lub zmienione bez niszczenia czegokolwiek, więc reszta świata Nie wiem, która propozycja została przyjęta jako pierwsza.

NECROBUMP. Nawet przy słabszej części obu wariantów nie ma niespójności. Spójrzmy na krok 9 w przykładzie w pytaniu:

"Stan jest a (-: -, 100) B (100:b,100) C(1:a,-). Wybrana propozycja jest porzucona, Paxos zawiedzie "

Jednak w tym momencie wszystko, co mamy, to wartość nieokreślona, ponieważ nie ma wartości akceptowanej przez większość (musimy ostatecznie wybrać "b", ponieważ b została zaakceptowana przez większość podczas kroku 6.)

Aby kontynuować protokół, my potrzebujesz nowych kart do głosowania i ostatecznie niektóre nowsze karty do głosowania zostaną zaakceptowane. Głosowanie musi mieć wartość "b",

Dowód: C odpowie za pomocą (100, 'b') na każde przygotowane żądanie, ponieważ najwyżej numerowaną kartą do głosowania jest (100, 'b'), nawet jeśli ostatnia zaakceptowała kartę do głosowania (1, 'a'). B odpowie również za pomocą (100, 'b'). W związku z tym nie jest już możliwe uzyskanie większości głosów z jakąkolwiek wartością, ale "b".

Język Lamporta polega na tym, że akceptant odpowie " propozycją z najwyższa liczba mniejsza od N, którą zaakceptowała, jeśli Dowolna "

Zaakceptowana odpowiedź myli "najwyższy numer" z "ostatnio zaakceptowaną", ponieważ przykład pokazuje, że akceptant może przyjmować wartości w malejącej kolejności. Aby całkowicie dostosować się do protokołu Lamporta, C musi pamiętać, że odpowiedział na (100, 'b'), nawet jeśli" najnowsza " akceptacja jest (1, 'a').

(nie zdziwiłbym się, gdyby wiele implementacji tego nie prawidłowo, a zatem są podatne na ten problem.)

W artykule jest pewna dwuznaczność, dlatego Specyfikacja TLA+, a nie Papier powinna być używana do implementacji algorytmu.

Akceptując wartość, akceptant musi ponownie zaktualizować swój stan, a mianowicie ostatnio obiecane głosowanie. Jest to jasne ze specyfikacji Paxos tla + , Sprawdź fazę 2b, w której acceptor aktualizuje maxBal, i porównaj z fazą 1b, gdzie robi to samo.

Leslie Lamport zajmuje się tym pytaniem w swoim ostatnim wykład , gdzie wyjaśnia, że odbywa się to specjalnie po to, aby zbiór akceptorów różnił się od zbioru węzłów obiecujących głosowanie.

C nie może przyjąć propozycji, ponieważ nie przeszła fazy 1. IOWs aby vale został zaakceptowany przez akceptanta, akceptant musi przejść przez obie fazy protokołu.

Jeśli akceptując wartość węzeł obiecuje również nie akceptować wcześniejszych wartości, algorytm jest poprawny, ale w artykule Lamport nie wspomniał o tym wymogu, prawda?

Powyższy warunek nie jest wymagany. Załóżmy, że najwyższa karta do głosowania obiecana przez akceptanta to X. Załóżmy, że przychodząca wiadomość Akceptuj ma numer karty do głosowania Y. Jeśli Y X, oznacza to, że akceptant nie otrzymał żądania przygotowania dla Y. oznacza to, że otrzymaliśmy nieprawidłową wiadomość paxos. W takim przypadku wiadomość accept dla Y powinna zostać odrzucona.

Jedynym wyjątkiem jest sytuacja, gdy Y = = 0. W takim przypadku wystawienie karty z numerem do głosowania 0 nie ma sensu, ponieważ numery do głosowania poniżej 0 są nieważne. Tak więc faza 1 może zostać pominięta dla głosowania 0, a kandydat może bezpośrednio przejść do fazy 2. W tym przypadku, tzn. gdy y == 0, akceptor może przyjąć wartość tylko wtedy, gdy nie zaakceptował wartości. To jest to samo, co proponujesz powyżej, ale jest to wymagane tylko w zoptymalizowanej wersji Paxos, gdzie fazę 1 można pominąć dla Y == 0.

IOWs, jedyny raz, kiedy akceptor akceptuje wartość jest wtedy, gdy Y = = X. jedynym wyjątkiem jest, gdy Y = = 0. W takim przypadku akceptant może przyjąć wartość tylko wtedy, gdy nie zaakceptował wartości.

Zgadzam się z większością odpowiedzi Bena Brauna.

C może zaakceptować (1, a), nie zmienia wybranej wartości. Powiedzmy C accepted (1, a), a przyjrzymy się historii accept z perspektywy ucznia.

(100, b) przyjęte przez B i C
(1, a) jest akceptowane przez C

(100, b) jest wybierany, ponieważ jest akceptowany przez większość akceptantów.

W tym momencie protokół nie musi być kontynuowany, jeśli uczeń ma pełną historię akceptacji, chyba, że uczniowie nie zdali egzaminu lub wiadomości do uczniów zostały utracone. Tu nie zgadzam się z odpowiedzią Bena Brauna.

Ale akceptanci powinni zachować zaakceptowaną propozycję z największą liczbą, w przypadku wydania nowej propozycji.

Update: zgadzam się również z Dave ' em Turnerem, że w rzeczywistości nie ma powodu, aby zaakceptować niższą numerację propozycji. Numer wniosku jest jak logiczny zegar czasu, można bezpiecznie ignorować Starsze wiadomości.