Czytam artykuł „Fast Paxos” autorstwa Leslie Lamport i utknąłem z dowodami poprawności zarówno klasycznych Paxos, jak i Fast Paxos.
Aby zachować spójność, wartość wybrana przez koordynatora w fazie 2 a w rundzie i powinna spełniać
Dla dowolnej rundy j < i żadna wartość inna niż v nie była lub może być wybrana w rundzie j .
W przypadku klasycznego Paxos dowód (strona 8) jest podzielony na trzy przypadki: , j = k oraz j < k , gdzie k jest największą liczbą zaokrągloną, w której jakiś akceptor zgłosił koordynatorowi w fazie 1 b wiadomość. Nie zrozumiałem argumentu trzeciego przypadku:
Przypadek . Możemy założyć, przez indukcję , że własność C P odbyło gdy akceptor 0 głosował na V w rundzie k . Oznacza to, że w rundzie j nie wybrano ani nie można było wybrać innej wartości niż v .
Moje pytanie brzmi:
- Dlatego można założyć, że nieruchomość odbyło gdy akceptor 0 głosował na V w rundzie k ?
Wydaje się, że używamy indukcji matematycznej, a zatem, na czym polegają podstawy, hipoteza indukcyjna i kroki indukcyjne?
W przypadku Fast Paxos ten sam argument (Strona 18) jest kontynuowany. To mówi,
Przypadek . Dla dowolnego v w V , żadna inna wartość niż v nie była lub może być jeszcze wybrana w rundzie j .
Moje pytanie brzmi:
- Jak to uzyskać? W szczególności dlaczego tutaj jest „For any in V ”?
Moim zdaniem dowód poprawności przypadku opiera się (rekurencyjnie) na przypadkach k < j < i oraz j = k .
Zatem jak możemy zakończyć przypadek bez uprzedniego pełnego udowodnienia j = k (czyli pominięcia podtekstu j = k, gdzie V zawiera więcej niż jedną wartość)?
źródło
Lamport tends to use another type of hierarchy. He'll prove a simpler algorithm, and then prove that a more complex algorithm maps onto (or "extends") the simpler algorithm
tym, czy mógłbyś zatem podać przykład lub zacytować powiązany artykuł? Ponadto, czy wasze artykuły mają wcześniej wydrukowane, (komercyjnie) niesklasyfikowane wydania?