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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Algorytmy roproszone

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

Algorytm uzgadniania

Zadanie

Danych jest procesorów. Każdy procesor może działać poprawnie lub być wadliwy. Wiadomo, że co najwyżej procesorów jest wadliwych. Każdy procesor przechowuje pewną wartość. Oznaczmy wartość przechowywaną w procesorze przez . 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 ustalenie wektora wartości takiego, że:

  1. Dla każdych dwóch dobrych procesorów i zachodzi: .
  2. Dla każdych dwóch dobrych procesorów i oraz dowolnego procesora zachodzi:

Intuicyjnie wartością współrzędnej wektora jest to, co procesor przypuszcza o wartości . 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.

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

Wariant drugi.

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 wysyła do pozostałych trzech wartość . Czy procesory mogą przyjąć jako swoją wiedzę o 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 tego, co dotarło do procesu od procesu może sposowodować niespełnienie drugiego warunku poprawności:

Rysunek 1

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

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

  1. Procesor wysyła wartość do pozostałych procesorów. Oznaczmy wartość, którą w wyniku tej komunikacji otrzymał proces przez
  2. Pozostałe procesory wymieniają między sobą wartości otrzymane od procesora . W ten sposób każdy procesor dysponuje multizbiorem trzech wartości.
  3. Jako wartość przyjmuje się tę wartość z multizbioru wartości, który dotarły do procesora , 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 , ale pierwszy warunek poprawności wymaga równości jedynie w przypadku, gdy jest dobry.

Wariant 3.

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 . Zatem procesory dobre zakładają, że w procesorze wadliwym jest pewna z góry ustalona wartość . Zastanówmy się, czym powinno być . 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 . Aby zapewnić warunek pierwszy poprawności należy zatem przyjąć . Z drugiej jednak strony przy następującym scenariuszu:

Rysunek 4

należy przyjąć . Otrzymana sprzeczność pokazuje, że nie da się rozwiązać problemu dla .

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 . 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 .

Algorytm OMIC jest rekurencyjny. Składa się on z faz. Jego wykonanie rozpoczyna się od fazy o numerze 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 rozsyła swoją wartość do wszystkich pozostałych procesorów. Oznaczmy przez to, co proces otrzymał od procesu . Przyjmujemy . Zauważmy, że w sytuacji, gdy ta jedna faza faktycznie wystarcza do zapewnienia obu warunków poprawności.
Rysunek 5
  1. OMIC(f): proces rozsyła swoją wartość do wszystkich pozostałych procesorów. Oznaczmy przez to, co proces otrzymał od procesu . Ponieważ proces mógł oszukiwać, więc tym razem nie można jako przyjąć , gdyż mogłoby to prowadzić do niespełnienia drugiego warunku poprawności. Tak naprawdę wszystkie procesy z wyjątkiem powinny teraz uzgodnić wspólną wiedzę o tym, co otrzymały od , czyli o wartościach primowanych. I to właśnie prowadzi do rekurencji. Wszystkie procesy z wyjątkiem wykonują teraz bowiem algorytm OMIC(f-1). Każdy proces biorący udział w tej fazie rozsyła jednak , a nie . Wykonanie OMIC(f-1) prowadzi oczywiście do obliczenia wartości w każdym procesie biorącym udział w tej fazie. Zgodnie z intuicją

oznacza wiedze, jaką proces p przyjmuje o wartości początkowej z procesu , czyli w tym wypadku to, co proces zakłada o wartości , czyli jeszcze inaczej: to co proces zakłada o wartości, którą proces otrzymał od procesu wysyłającego . Popatrzmy, jaką informacją dysponuje teraz proces o procesie :

  1. Po pierwsze ma wartości dla każdego . Jest to informacja o otrzymana za pośrednictwem .
  2. Po drugie: wartość , czyli informacja o uzyskana bezpośrednio od . Oznaczmy tę wartość jako .

Jako rozwiązanie, czyli przyjmuje się tę wartość z multizboru , 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 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 . 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 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)