Synchronizatory - jak alg synch ruchomić w sieci asynch?

Po co się to robi?

  1. alg synch łatwiej się projektuje niż asynch
  2. wirtualne rundy = "pulsy" mają różne zastosowania:
    np. prędkość pakietów w alg LE w cyklu...

Podstawowe zasady:

  1. Potwierdzanie dostarczenia komunikatu (ACK)
    bo w modelu asynch nadawca nie wie kiedy kom został dostarczony!!
  2. A=alg synch; def: wierz jest „bezpieczny” w k-tej rundzie A
    jeśli wszystkie kom k-tej rundy alg A zostały potwierdzone
  3. Kiedy mogę przejść do k+1 (wirtualnej) rundy ?
    odp: gdy jestem bezpieczny i moi sąsiedzi są bezpieczni!!
    to jest minimalny warunek każdego synchron!
  4. Jest kilka typów synchron. α, β, γ, … (niżej oznaczane S)

Wada synchronizatorów: „narzut” czyli dodatkowe komunikaty/czas...
narzut komunikatowy M(S) i czasowy T(S) na 1 rundę wirt
oznaczenia: A=alg synch, A'=alg asynch (A'=A+S)
M(A')=Minit(S) + M(A) + T(A) M(S)
T(A') = Tinit(S) + T(A) T(S)
??? co to jest czas alg asynch ???

Synchronizator α

synch alfa

Synchronizator β

synch beta

Synchronizator γ

synch gamma
synch gamma
Pozostaje kwestia obliczania "klastrów" dla synch γ...
pomijamy temat, jako że robi się to sekwencyjnie, po 1 klastrze!

Dalszy rozwój synchronizatorów?

  1. rozwinięcia synchron γ: klastry "cover" (nakładające się) zamiast klastrów "partition"...
    prostsze działanie, narzuty takie same jak w synchron γ
    patrz slajd na str 7 tutaj
  2. spannery Pelega (to nie te od skojarzeń !!)
    podgraf H o malej liczbie kraw, zachowujący odległość: dist_H(a,b) < const dist_G(a,b)
    dla synchron α mniejszy narzut komunikatowy, większe "zwichrowanie" czasu...
    patrz slajd na str 8 tutaj

...

Zadania

ZADANIE 40 impl synch α
Zaimplementuj synchronizator α w symulatorze asynch
oraz zbadaj jaki jest numer rundy/pulsu na dwóch wierz w odl =k,
w czasie działania takiego algorytmu:

   set liczRundy 0  
   while 1 {  
      incr liczRundy  
      ## wstawka realizująca "koniec rundy" ##
   }

Wskazówka: dla ułatwienia użyj komendy "dostarcz" zamiast "wyslij", dzięki czemu
trzeba genereować jedynie zdarzenia obliczeniowe (a nie obliczeniowe i dostarczenia),
czyli nie jest konieczne używanie dostarczKom...
Uwaga 1: w modelu asynch. wszystkie wierzchołki powinny działać w nieskończoność
Uwaga 2: najłatwiej zrobić eksperyment do tego zadania w cyklu...
(ale procedure "koniec rundy" lepiej napisać ogólnie!)
Uwaga 3: jak budować alg asnych w symulatorze? patrz przykład z "zar01" !!

ZADANIE 41 (1.5pkt) impl synch β
podobne zasady jak dla zadania 40

ZADANIE 42 synchronizator/ realne zastosowanie
użyj synchronizatora α lub β dla prostego alg synch,
np: każdy wierz cyklu wysyła w lewo swój ID, które potem krążą w lewo w cyklu;
albo: jeden wierz wysyła liczbę 0 w lewo, pozostałe wierz przekazują ją, zwiększając o 1;
sprawdź czy procedura "koniec rundy" prawidłowo dostarcza komunikaty alg synch...

ZADANIE 43 (1.5pkt) odległość w ścieżce, synchronizator α
W ścieżce są 2 wierz a i b. Wierzchołek a chce odpowiedzieć na pytanie czy "dist(a,b)≤x".
Podaj i przetestuj wersję algorytmu, która działa pod synchronizatorem alfa,
w czasie O(x) wirtualnych rund (niezależnie od dist(a,b)).
Wierz a i b są oznaczone "ręcznie", dodatkowo wierz a ma podaną wartość x.