Dlaczego liczba konsensusu dla testu i zestawu 2?

Według Wikipedii ,

Operacja testowania i ustawiania może rozwiązać problem konsensusu bez czekania dla nie więcej niż dwóch równoległych procesów.

Dlaczego nie może rozwiązać problemu dla więcej niż dwóch procesów?

Aby upewnić się, że jesteśmy na tej samej stronie, najpierw rozważmy trzy następujące definicje:

Definicja. Test-and-set jest instrukcją odczytu-modyfikacji-zapisu w jakimś rejestrze binarnym (powiedzmy, że 0 i 1 są możliwymi wartościami), gdzie wątek uzyskuje starą wartość i zapisuje 1.

Definicja. Osiągnięto konsensus między wątkami i wszystkie n wątki decydują o tej samej wartości (wymóg spójności), a wszystkie wątki decydują o wartości, która została faktycznie zaproponowana przez jeden z wątków (wymóg ważności).$n$$n$

Definicja Protokół konsensusu jest bez czekania, gdy każde wywołanie metody kończy się w skończonej liczbie kroków.

Teraz wykonaj dwa szkice próbne.

Twierdzenie 1. Konsensus liczba testów i zestawów wynosi co najmniej 2. Dowód. Załóżmy, że mamy dwa wątki 0 i 1, które muszą osiągnąć konsensus. Możemy to zrobić, pozwalając każdemu wątkowi postępować zgodnie z poniższym protokołem konsensusu:

1. Napisz proponowaną wartość do , gdzie t to identyfikator wątku, a $A[t]$$t$$A$ to tablica o rozmiarze 2.
2. Wykonaj instrukcję testowania i ustawiania dla niektórych rejestrów z R zainicjalizowanym na 0.$R$$R$
3. Jeśli zwracana wartość to 0, byłeś pierwszy: zwróć . W przeciwnym razie byłeś drugi: zwróć A [ | t - 1 | ] .$A[t]$$A[|t-1|]$

Możesz sprawdzić, czy konsensus i brak oczekiwania są spełnione. $\square$

(Dla następnego dowodu zagnieżdżę niektóre dowody i definicje, ponieważ myślę, że ułatwi to śledzenie).

Twierdzenie 2. Liczba konsensusowa testu i zestawu wynosi co najwyżej 2. Dowód. Przez sprzeczność. Załóżmy, że mamy trzy wątki , B i C, które chcą decydować o wartościach a , b i $A$$B$$C$$a$$b$$c$ , i że mamy jakiś ważny protokół konsensusu bez czekania, który jest implementowany za pomocą testowania i ustawiania (oraz atomowych odczytów i zapisów ).

Możemy wizualizować proces konsensusu jako ukierunkowane drzewo, w którym:

• Korzeń to stan, w którym żaden z wątków „nie wykonał ruchu”;
• Lewe dziecko węzła reprezentuje stan powstały po ruchu przez , środkowe dziecko reprezentuje stan, który powstaje po ruchu przez B , a prawe dziecko reprezentuje stan, który powstaje po ruchu przez C ;$A$$B$$C$
• Węzeł liścia reprezentuje stan, w którym wszystkie wątki zostały zakończone. Z węzłem liścia jest powiązana wartość , b lub c , gdzie wartość zależy od tego, która wartość została podjęta dla tego konkretnego wykonania.$a$$b$$c$

Definicja. Niech stan będzie wielowartościowy, jeśli wynik procesu konsensusu nie jest jeszcze określony. Innymi słowy, nie wszystkie możliwe przeploty pozostałych ruchów prowadzą do tego samego rezultatu. Niech stan będzie jednoznaczny, gdy zostanie ustalony wynik procesu konsensusu .

Korzeń jest wielowartościowy. Dowód. Jeśli tylko jeden wątek jest aktywny, a pozostałe wątki pozostają w stanie uśpienia na zawsze, X zakończy się w skończonej liczbie kroków (gwarantowane przez założenie oczekiwania na brak oczekiwania) i zdecyduje x (ponieważ ma dostęp tylko do tej wartości i jej decyzja spełni wymóg ważności konsensusu). Tak więc w naszej sytuacji wszystkie możliwe wyniki są a , b i c . $X$$X$$x$$a$$b$$c$$\square$

Definicja. Niech stanem krytycznym będzie stan wielowartościowy, z dodatkową właściwością, że ruch określi a , a ruch B wyznaczy b .$A$$a$$B$$b$

Istnieje stan krytyczny. Dowód. Z góry wiemy, że zaczynamy w stanie wielowartościowym. Niech nie wykona żadnego ruchu. Tak długo, jak A lub B nie zmusza drzewa do przejścia w stan jednoznaczny, pozwól mu się ruszyć. Wait-freeness gwarantuje, że drzewo jest skończone, więc w pewnym momencie należy napotkać stan krytyczny. $C$$A$$B$$\square$

Rozważmy teraz scenariusz, w którym znajdujemy się w stanie krytycznym. Istnieją co najmniej dwie możliwości:

1) wykonuje swój ruch (określając w ten sposób a ) i zatrzymuje się. B następnie wykonuje ruch i zatrzymuje się. Następne C działa aż do końca, ostatecznie decydując o .$A$$a$$B$$C$$a$

2) wykonuje ruch (określając w ten sposób b ) i zatrzymuje się. Następne C działa aż do końca, ostatecznie decydując b . A nie wykonuje ruchu.$B$$b$$C$$b$$A$

Ponieważ odczyty i zapisy atomowe mają konsensus nr 1, ruchy i B musiały być instrukcjami testowania i ustawiania w tym samym rejestrze (jeśli rejestry są różne, to C nie byłby w stanie określić kolejności, w której A i Ruchy B miały miejsce). Od C perspektywy „s, następnie scenariusze 1 i 2 są nie do odróżnienia, więc musimy mieć, że C decyduje zarówno A i B . To jest niemożliwe. $A$$B$$C$$A$$B$$C$$C$$a$$b$$\square$

To, że instrukcja testowania i ustawiania ma konsensus nr 2 wynika zarówno z zastrzeżeń 1, jak i 2.

Artykuł na Wikipedii zawiera odniesienie, które odpowiada na twoje pytania, ale być może nie chcesz czytać tego 26-stronicowego artykułu. Podam uproszczoną wersję (dość technicznego) dowodu, pokazując, że testowanie i ustawianie nie może rozwiązać binarnego konsensusu dla 3 procesów. Ten rodzaj argumentów jest szeroko stosowany przy potwierdzaniu liczb konsensusowych.

Załóżmy, że mamy algorytm konsensusowy wykorzystujący rejestry TAS dla 3 procesów.

W dowolnym momencie każdy proces będzie miał ruch (instrukcję) gotowy do wykonania. Która z trzech instrukcji zostanie wykonana, jest niedeterministyczna.

Załóżmy, że znajdujemy się w stanie dwuwartościowym (stan, w którym nadal możliwa jest zarówno decyzja 0, jak i 1) i którykolwiek proces przejdzie dalej, kolejny stan będzie jednoznaczny. Taki stan musi zostać ostatecznie osiągnięty z powodu warunku braku oczekiwania.

Załóżmy (wlg), że jeśli proces 1 się poruszy, stan będzie 0-wartościowy, a jeśli proces 2 się poruszy, stan będzie 1-walentny. Oba ruchy muszą być operacją TAS (lub przynajmniej: pewnego rodzaju zapisu) na tym samym rejestrze, ponieważ jeśli byłyby to operacje TAS na różnych rejestrach, nie moglibyśmy stwierdzić, czy proces 1 przesunął się pierwszy, czy proces 2 przesunął się pierwszy.

Rozważmy te dwie możliwe wykonania:

• Proces 1 najpierw się porusza, następnie proces 2 się porusza, a następnie proces 3 biegnie sam
• Proces 2 najpierw się porusza, a następnie proces 3 uruchamia się sam

Z punktu widzenia procesu 3 stany te są nierozróżnialne, ponieważ po prostu widzi wartość zapisaną przez proces 2. Jednak w pierwszym przypadku powinna dać 0 jako wynik, a w drugim 1 jako wynik. Oczywiście jest to sprzeczność.

Procesy 1 i 2 mogą między sobą decydować, które przesunęły się jako pierwsze (ponieważ mogą zobaczyć, jaka wartość była w rejestrze przed ich zapisem), ale trzeci proces widza nie może.

Innym sposobem udowodnienia, że ​​test i zestaw nie mogą być użyte do rozwiązania konsensusu 3-procesorowego, jest wykazanie, że testy i zestaw mogą być zaimplementowane przy użyciu konsensusu 2-procesorowego. Zatem założenie, że testy i zestaw mogą rozwiązać konsensus 3-procesorowy prowadzi do sprzeczności: Załóżmy, że testy i zestaw mogą rozwiązać konsensus 3-procesorowy; następnie poprzez zastąpienie test-and-set jego implementacją przy użyciu konsensusu 2-procesorowego uzyskuje się implementację konsensusu 3-procesorowego przy użyciu konsensusu 2-procesorowego, co jest niemożliwe. Zatem testowanie i ustawianie nie może rozwiązać konsensusu 3-procesorowego.

Aby zaimplementować test i zestaw dla n-procesorów wykorzystujących konsensus 2-procesorowy, pozwól procesorom określić zwycięzcę testu i zestawu w turnieju, w którym każde dopasowanie jest implementowane przy użyciu konsensusu 2-procesorowego (w meczu procesory zaproponuj swój identyfikator, a wynik konsensusu powie im, kto wygra).

W sensie praktycznym może wystarczyć mniej ścisła definicja konsensusu (tutaj nazywam to konsensusem światła):

Definicja . Osiągnięto konsensus świetlny między n wątków iff (a) każdy wątek decyduje się na tę samą wartość lub wartość jest dla niego nieznana, (b) co najmniej jeden wątek zna wartość i (c) ta wartość została faktycznie zaproponowana przez jeden z wątki.

Stąd ten konsensus w jego lżejszym sensie pozwala, że ​​niektóre wątki nie znają konsensusu, o wartości, która jest ustalona.

Następstwo : w tym jaśniejszym sensie testowanie i ustawianie ma nieskończoną liczbę zgodności światła.

Twierdzenie : Ten lżejszy sens jest praktyczny. Na przykład, aby wybrać wątek, który ma wejść do sekcji krytycznej, nie jest konieczne tworzenie konsensusu w ścisłym tego słowa znaczeniu. To znaczy: każdy wątek musi wiedzieć, czy został wybrany, czy nie, jednak jeśli nie zostanie wybrany, nie będzie musiał wiedzieć, który został wybrany. Innymi słowy, dla wzajemnego wykluczenia ścisły konsensus nie jest konieczny, wystarczy światło.