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

From Studia Informatyczne

Spis treści

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 iq 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'
  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' to, co proces p otrzymał od procesu q. Przyjmujemy V_p(q) = v_p'. 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' 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', 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', a nie v_p. Wykonanie OMIC(f-1) prowadzi oczywiście do obliczenia wartości V_p'(r) w każdym procesie p biorącym udział w tej fazie. Zgodnie z intuicją

V_p'(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', 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'(r) dla każdego r\neq p, r \neq q. Jest to informacja o v_q otrzymana za pośrednictwem r.
  2. Po drugie: wartość v_p', czyli informacja o v_q uzyskana bezpośrednio od q. Oznaczmy tę wartość jako V_p'(q).

Jako rozwiązanie, czyli V_p(q) przyjmuje się tę wartość z multizboru \{V_p'(r) | r \neq 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)