Programowanie współbieżne i rozproszone/PWR Wykład 7

Algorytmy roproszone

Obecnie zajmiemy się algorytmami, które realizują podstawowe zadania w systemach rozproszonych.

Algorytm uzgadniania

Zadanie

Danych jest $n$ procesorów. Każdy procesor może działać poprawnie lub być wadliwy. Wiadomo, że co najwyżej $m$ procesorów jest wadliwych. Każdy procesor przechowuje pewną wartość. Oznaczmy wartość przechowywaną w procesorze $p$ przez $v_p$. Procesory porozumiewają się poprzez wymianę komunikatów, która odbywa się zgodnie z następującymi założeniami:

• Każdy procesor może wysłać komunikat do każdego.
• Komunikacja między dobrymi procesorami jest niezawodna.
• Odbiorca zna nadawcę komunikatu.

Zaprojektować algorytm, który umożliwi każdemu procesorowi $p$ ustalenie wektora wartości $V_p$ takiego, że:

1. Dla każdych dwóch dobrych procesorów $p$ i $q$ zachodzi: $V_p(q)=v_q$.
2. Dla każdych dwóch dobrych procesorów $p$ i$q$ oraz dowolnego procesora $r$ zachodzi: $V_p(r)=V_q(r)$

Intuicyjnie wartością $q$ współrzędnej wektora $V_p(q)$ jest to, co procesor $p$ przypuszcza o wartości $v_q$. Powyższe dwa warunki wyrażają fakt, że w wyniku działania algorytmu, procesor dobry musi uzyskać dokładną wiedzę o wartości przechowywanej w każdym dobrym procesie. Warunek drugi oznacza, że wiedza procesorów dobrych musi być spójna: każdy procesor dobry musi wiedzieć to samo o każdym innym (także wadliwym) procesorze.

Wariant pierwszy. $n=3,m=0$

Gdy mamy 3 procesory i wszystkie są dobre to wystarczy, aby każdy przesłał każdemu swoją wartość. Jako $V_p(q)$ procesor $p$ przyjmuje to, co otrzymał od procesora $q$. Ponieważ komunikacja między dobrymi procesorami jest niezawodna, a wszystkie procesory są dobre, więc oczywiście zachodzi: $V_p(q)=v_q$ i oba warunki poprawności są spełnione.

Wariant drugi. $n=4,m=1$

Załóżmy teraz, że wśród 4 procesorów jeden jest wadliwy. Przeanalizujmy tę fazę algorytmu, w której ustala się wiedzę o procesorze wadliwym. Na wszystkich rysunkach w tym wykładzie procesory wadliwe będziemy przedstawiać w postaci kwadratów, a dobre w postaci okręgów. Przypuśćmy, że procesor wadliwy $q$ wysyła do pozostałych trzech wartość $v_q$. Czy procesory mogą przyjąć jako swoją wiedzę o $q$ to, co od niego otrzymały? Oczywiście, nie! Ponieważ komunikacja między procesorem wadliwym nie musi być poprawna, więc dobre procesory mogą otrzymać różne wartości. Przyjęcie jako $V_p(q)$ tego, co dotarło do procesu $p$ od procesu $q$ może sposowodować niespełnienie drugiego warunku poprawności:

Rysunek 1

Jest zatem potrzebna dodatkowa wiedza o procesie $q$. Jej źródłem jest dodatkowa wymiana informacji, którą procesory otrzymały od procesora $q$.

Usupełnijmy więc algorytm w następujący sposób. Aby ustalić wiedzę procesorów o procesorze $q$:

1. Procesor $q$ wysyła wartość $v_q$ do pozostałych procesorów. Oznaczmy wartość, którą w wyniku tej komunikacji otrzymał proces $p$ przez ${v_p}^{\prime }$
2. Pozostałe procesory wymieniają między sobą wartości otrzymane od procesora $q$. W ten sposób każdy procesor dysponuje multizbiorem trzech wartości.
3. Jako wartość $V_p(q)$ przyjmuje się tę wartość z multizbioru wartości, który dotarły do procesora $q$, która występuje w niej największą liczbę razy. Tak sposób wyboru będziemy oznaczać wyborem większościowym i oznaczać przez maj.

Popatrzmy na przykład, w którym procesory ustalają swoją wiedzę na temat procesora dobrego:

Rysunek 2

Jednak w dalszym ciągu problematyczna jest sytuacja, w której ustalamy informacje o procesorze wadliwym. Może on wysłać do każdego procesora inną wartość:

Po wymianie informacji między procesorami dobrymi okazuje się, że dysponują one tym samym multizbiorem wartości. Nie ma w nim jednak wartości pojawiającej się najczęściej. W takiej sytuacji przyjmujemy, że wartością funkcji maj jest pewna z góry ustalona wartość. Zauważmy, że ponieważ wszystkie procesory mają ten sam multizbiór, więc wartości funkcji maj będą w nich takie same. Jest to zgodne z wymaganiem drugim. Oczywiście ta wartość nie musi być równa $v_q$, ale pierwszy warunek poprawności wymaga równości jedynie w przypadku, gdy $q$ jest dobry.

Wariant 3. $n=3,m=1$

Popatrzmy jeszcze na przypadek trzech procesorów wśród których jeden jest wadliwy. Popatrzmy na przypadek, w którym ustala się wartość przechowywaną w wadliwym procesorze.

Rysunek 3

Jeśli wadliwy procesor wyśle do pozostałych różne wartości, to będą one dysponowały multizbiorem $\{a,b\}$. Zatem procesory dobre zakładają, że w procesorze wadliwym jest pewna z góry ustalona wartość $c$. Zastanówmy się, czym powinno być $c$. W tym celu rozpatrzmy następującą wymianę komunikatów (tym razem prowadzącą do ustalenia wartości przechowywanej w dobrym procesorze):

I tym razem procesor 2 dysponuje multizbiorem $\{a,b\}$. Aby zapewnić warunek pierwszy poprawności należy zatem przyjąć $c=a$. Z drugiej jednak strony przy następującym scenariuszu:

Rysunek 4

należy przyjąć $c=b$. Otrzymana sprzeczność pokazuje, że nie da się rozwiązać problemu dla $n=3,m=1$.

Z powyższych rozważań wynika, że przedstawiony problem nie zawsze ma rozwiązanie. Warunkiem koniecznym i wystarczającym na to, aby rozwiązanie istniało jest zachowanie nierówności $n>3m$. W dalszych rozwiązaniach przyjmujemy, że taka nierówność zachodzi.

Algorytm OMIC

Przedstawimy teraz algorytm o nazwie Oral Messages Interchange Communication (w skrócie: OMIC), który rozwiązuje zadanie postawionie na wstępie przy założenu $n>3m$.

Algorytm OMIC jest rekurencyjny. Składa się on z $m+1$ faz. Jego wykonanie rozpoczyna się od fazy o numerze $m$ a kończy na fazie o numerze 0. Opiszmy najpierw nieformalnie działanie tego algorytmu. W opisie przedstawimy sposób uzyskania informacji o jednym wyróżnionym procesie. Aby uzyskać informację o wszystkich procesach należy powtórzyć go wyróżniając po kolei każdy proces.

Niech OMIC (f) oznacza f-tą fazę algorytmu. Mamy:

1. OMIC (0): proces $q$ rozsyła swoją wartość $v_q$ do wszystkich pozostałych procesorów. Oznaczmy przez ${v_p}^{\prime }$ to, co proces $p$ otrzymał od procesu $q$. Przyjmujemy $V_p(q)={v_p}^{\prime }$. Zauważmy, że w sytuacji, gdy $m=0$ ta jedna faza faktycznie wystarcza do zapewnienia obu warunków poprawności.

Rysunek 5

1. OMIC(f): proces $q$ rozsyła swoją wartość $v_q$ do wszystkich pozostałych procesorów. Oznaczmy przez ${v_p}^{\prime }$ to, co proces $p$ otrzymał od procesu $q$. Ponieważ proces $q$ mógł oszukiwać, więc tym razem nie można jako $V_p(q)$ przyjąć ${v_p}^{\prime }$, gdyż mogłoby to prowadzić do niespełnienia drugiego warunku poprawności. Tak naprawdę wszystkie procesy z wyjątkiem $q$ powinny teraz uzgodnić wspólną wiedzę o tym, co otrzymały od $q$, czyli o wartościach primowanych. I to właśnie prowadzi do rekurencji. Wszystkie procesy z wyjątkiem $q$ wykonują teraz bowiem algorytm OMIC(f-1). Każdy proces $p$ biorący udział w tej fazie rozsyła jednak ${v_p}^{\prime }$, a nie $v_p$. Wykonanie OMIC(f-1) prowadzi oczywiście do obliczenia wartości ${V_p}^{\prime }(r)$ w każdym procesie $p$ biorącym udział w tej fazie. Zgodnie z intuicją

${V_p}^{\prime }(r)$ oznacza wiedze, jaką proces p przyjmuje o wartości początkowej z procesu $r$, czyli w tym wypadku to, co proces $p$ zakłada o wartości ${v_r}^{\prime }$, czyli jeszcze inaczej: to co proces $p$ zakłada o wartości, którą proces $r$ otrzymał od procesu $q$ wysyłającego $v_q$. Popatrzmy, jaką informacją dysponuje teraz proces $p$ o procesie $q$:

1. Po pierwsze ma wartości ${V_p}^{\prime }(r)$ dla każdego $r\ne p,r\ne q$. Jest to informacja o $v_q$ otrzymana za pośrednictwem $r$.
2. Po drugie: wartość ${v_p}^{\prime }$, czyli informacja o $v_q$ uzyskana bezpośrednio od $q$. Oznaczmy tę wartość jako ${V_p}^{\prime }(q)$.

Jako rozwiązanie, czyli $V_p(q)$ przyjmuje się tę wartość z multizboru $\{{V_p}^{\prime }(r)|r\ne q\}$, która występuje w nim najczęściej.

Rysunek 6

Spróbujmy opisać ten algorytm nieco bardziej precyzyjnie. Ponumerujmy procesory od 0 do n-1, a fazy od 0 do m przyjmując następujące definicje typów:

type
  Procesor = 0 .. n;
  Faza = 0 .. m;

Wartości początkowe $v_p$ możemy traktować jak tablicę wartości pewnego typu indeksowaną procesorami:

  Wektor = array [Procesor] of Typ;

Umówmy się, że zbiory procesorów reprezentujemy za pomocą typu setof[Procesor]. Spróbujmy zapisać funkcję OMIC, która wylicza wartości $V_p$. Aby ustalić, jakie argumenty powinna mieć ta funkcja, zastanówmy się, co zmienia się w kolejnych wywołaniach funkcji OMIC. Oczywiście zmienia się numer fazy, ale także zestaw wartości początkowych oraz zbiór procesorów biorących udział w kolejnej fazie. Wynikiem algorytmu jest tablica $V$ indeksowana procesorami, której elementami są wektory wartości. Zatem OMIC możemy zapisać jako funkcję:

 function OMIC (f: Faza; v: Wektor; S: setof Procesor): array [Procesor] of Wektor

To, co poprzednio zapisawaliśmy, jako V_p(q) teraz zapiszemy więc, jako OMIC (m, v, {}) (p) (q). Jest to wartość, jaką procesor p założy o wartości początkowej w q w wyniku wykonania algorytmu OMIC z m fazami, wektorem wartościami początkowymi v, i zbiorem s. Aby sprecyzować treść funkcji OMIC przyjmijmy, że mamy daną funkcję wyboru większościowego maj (S: setof, v: Wektor) jest to wartość, która występuje najczęściej pośród wszystkich wartości tablicy v na pozycjach należących do zbioru S. Załóżmy także, że działanie sieci jest symulowane za pomocą funkcji send:

 send(f, t, q, p) jest to wartość jaką proces p otrzymuje w wyniku przesłania przez proces q wartości t w rundzie f. Oczywiście, jeśli procesory p i q są dobre, to mamy:
 send (f, t, q, p) = t 

Ponadto przez distr (f, t, q) oznaczmy tablicę, która na pozycji p ma wartość, jaką procesor p otrzyma na skutek rozgłoszenia przez proces q wartości t. Możemy zapisać:

 distr (f, t, q) (p) = send (f, t, q, p). 

Zdefiniujmy teraz formalnie OMIC (f, v, S) (p) (q) dla każdego p, q \in S:

OMIC (f, v, S) (p) (q) =  
  if f = 0 then send (r, v(q), q, p)
  else
    if p = q then 
      send (r, v(q), q, q)
    else 
      maj (S-{q}, OMIC (f-1, distr (r, v(q), q), S-{q}) (p))
 

Poprawność algorytmu OMIC

Dowód poprawności algorytmu OMIC polega na pokazaniu następujących lematów pomocnuczych:

Lemat

Przypuśćmy, że p oraz q są dobrymi procesorami należącymi do zbioru s. Jeśli liczba dobrych procesorów w zbiorze S przekracza liczbę procesorów wadliwych w S zwiększoną o numer fazy, to

            OMIC (f, v, s) (p) (q) = v (q) 

Wniosek

 OMIC (m, v, Full) (p) (q) = v (q)

Lemat

Niech p, q, r będą procesorami należącymi do zbioru S. Ponadto przypuśćmy, że p, q są dobre, liczba procesorów w zbiorze s przekracza 3f, a liczba wadliwych procesorów w zbiorze S nie przekracza f. Wówczas:

      OMIC (f, v, s) (p) (r) = 
      OMIC (f, v, s) (q) (r)

Wniosek

 OMIC (m, v, Full) (p) (r) = 
OMIC (f, v, s) (q) (r)