# Ćwiczenia 7, grupa śr. 12-14, 7 grudnia 2022

###### tags: `PRW22` `ćwiczenia` `pwit`

## Deklaracje

Gotowość rozwiązania zadania należy wyrazić poprzez postawienie X w odpowiedniej kolumnie! Jeśli pożądasz zreferować dane zadanie (co najwyżej jedno!) w trakcie dyskusji oznacz je znakiem ==X== na żółtym tle.

**UWAGA: Tabelkę wolno edytować tylko wtedy, gdy jest na zielonym tle!**

:::danger
| | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- | --- | --- |
Michał Bronowicki | | | | | | | | | |
Wiktor Bukowski | X | X | X | X | X | X |==X==| X | X |
Jan Dalecki | X | | | | | | | | |
Mikołaj Depta | | X | X |==X==| X | X | | X | |
Kamil Galik | | | | | | | | | |
Bartosz Głowacki | | | | | | | | | |
Michał Hetnar | x | x | x | x | x | x | | x | x |
Adam Jarząbek | | | | | | | | | |
Michał Kierul | | | | | | | | | |
Mateusz Kisiel | ==X== | X | X | | X | X | | X | |
Maksymilian Komarnicki | X | | | X | | | | X | X |
Julia Matuszewska | | X | | | X | X | | X | |
Andrzej Morawski | | | | | | | | | |
Wojciech Pokój | | X | X | | X | X | | X | |
Marcin Sarnecki | | X | X | X |==X==| X | | X | |
Bartosz Szczeciński | X | X | X | | X | X | | X | |
Tomasz Wołczański | X | X | X | X | X | X | | X | |
Marcin Wróbel | | X | X | X | X | X | X | X | |
:::

:::info
**Uwaga:** Po rozwiązaniu zadania należy zmienić kolor nagłówka na zielony.
:::

**Poniżej można zadeklarować zadanie 6 z listy 6**:
-
-
-

## Zadanie 1
:::success
Autor: Mateusz Kisiel
:::

* Funkcja collect zrobi nam kopię tablicy. W trakcie robienia kopi mogły np. nastąpić dwa updaty na początku i na końcu tablicy, przez co w kopi pojawi się zmiana tylko ta z dołu tablicy (w tym momencie nasza kopia nie jest prawidłowym snaphotem).

Załóżmy nie wprost, że atomowa migawka SimpleSnaphot nie działa prawidłowo i zwróciła błędny wynik. Wykonanie metody scan zwróciło nam pewien stan tablicy, który nigdy nie istniał. W pewnym momencie funkcji scan musiało wykonać się `Array.equals(oldCopy, newCopy)` i zwrócić true. Mogło to nastąpić tylko jeżeli nie zmienił się żaden timestamp, a skoro się nie zmienił to znaczy w szczególności, że nie nastąpiła żadna zmiana w trakcie wykonania drugiej kopii tablicy. Zatem druga kopia tablicy jest prawidłowym snapshotem. A skoro pierwsza kopia jest równa drugiej to także jest prawidłowym snapshotem. Sprzeczność.

Timestampy są potrzebne, aby mieć pewność, że bład nie nastąpił 2 razy w ten sam sposób.

* W najgorszym przypadku, gdy jest dużo updatów będziemy ponawiać scan w nieskończoność, jeżeli jednak zatrzymamy drugi wątek i pozwolimy pracować scan'owi w odizolowaniu na pewno się on zakończy, zatem jest obstruction-free.
* update wykonuje się atomowo, bez żadnych pętli, zatem jest lock-free, a zatem cały system jest lock-free


## Zadanie 2
:::success
Autor: Bartosz Szczeciński
:::


Załóżmy nie wprost, że istnieje nieczekająca implementacja protokołu binarnego konsensusu dla n > 2 wątków, używająca jedynie rejestrów atomowych.

Skoro jest nieczekająca, to może się zdarzyć, że n - 2 wątki umrą i zostaną tylko dwa wątki. Ale z wykładu wiemy, że nie istnieje taka implementacja dla 2 wątków - sprzeczność.

## Zadanie 3
:::success
Autor: Wojciech Pokój
:::

konsensus m-wartościowy

Pseudokod:

class MValuedConsensus<T> {
  private BinaryConsensus cons[];
  private AtomicRegister<T> values[];
  
  public MValuedConsensus() {
    values = new AtomicRegister<T>[N]; // N - liczba wątków
    threads = new BinaryConsensus[N];
  }
  
  public T decide(T value) {
    int self = ThreadID.get();
    
    values[self] = value;
    
    cons[self].decide(true);
    
    for(int i = 0; i < N; i++) {
      if(cons[i].decide(false)) {
        return value[i];
      }
    }
  }
}

Algorytm ma następujące własności:

### Jest wait free

Wynika z faktu że używamy konsensusu który jest wait-free

### Zawsze zwróci wartość

Przynajmniej jednemu wątkowi uda się ustawić wartość swojego konsensusu na prawdę.

Gdyby żadnemu się nie udało oznaczałoby że każdy musiałby być poprzedzony przez któregoś innego, ale to jest sprzeczne, musi istnieć jeden któremu jako pierwszemu udało się zakończyć wywoływanie swojego konsensusu

### Zwróci tylko jedną wartość

Wynika to z prostego faktu że gdy w pętli (18) dochodzimy do consensusu z wartością prawda wszystkie pozostałye mają już ustaloną wartość. Żaden ze wcześniejszych nie może zmienić swojej wartości, więc możemy conajwyżej zmienić stan tych późniejszych, jednak to nie wpłynie na zwracaną wartość

## Zadanie 4
:::success
Autor: Mikołaj Depta
:::

Załóżmy nie wprost, że da się taki konsensus osiągnąć dla wątków `A`, `B`, `C`. Taki protokół ma stan krytyczny `S`. Załóżmy bez straty ogólności, że następny ruch `A` przeniesie nas do wierzchołka 0 walentnego a `B` do 1 walentnego. Rozpatrzmy możliwe scenariusze.

1. `A deq`, `B deq`

Niech `S'` będzie stanem pamięci po tym jak `A` wykonał się pierwszy a `B` wykonał się po nim a `S''` stanem gdzie te operacje wykonały się w odwrotnej kolejności.


Rozważmy teraz możliwe ruchy `C`, który wykonałby się z tych stanów w sposób nieprzerwany. Ze stanu `S'` dowolna sekwencja ruchów spowoduje, że `C` osiągnie konsensus 0, a dla stanu `S''` byłoby to 1. Otrzymalibyśmy różne wartości konsensusu mimo tego, że stan pamięci z perspektywy wątku `C` jest taki sam dla stanów `S'` i `S''`. Co jest niemożliwe podczas wykonywania deterministycznej sekwencji ruchów.

2. `A enq(a), B enq(b)`

Ponownie chcielibyśmy znaleźć sekwencję ruchów, która dałaby nam dwa identyczne stany o różnej walentności.

Dwa symetryczne scenariusze:

`A` woła `deq` pierwszy a następnie `B` - kolejka `[a, b]`.

Aby osiągnąć konsensus wątki muszą odczytać wartości z kolejki. Wykonajmy więc teraz `A` nieprzerwanie aż wykona `deq -> a`, po czym wstrzymajmy jego wykonanie i zróbmy to samo dla `B`. Otrzymamy w ten sposób stan `S'`, w którym kolejka jest pusta.

Analogicznie możemy stworzyć stan `S''`, gdzie kolejność wątków `A` i `B` jest odwrócona.

Ostatecznie ponownie otrzymamy dwa stany o różnych walentnościach, które dla wątku `C` są identyczne a mimo tego mają prowadzić do różnych wartości konsensusu, co ponownie znaczy sprzeczność.


2. `A enq(a), B deq`

Gdy kolejka jest niepusta kolejność wykonania `A` i `B` nie ma znaczenia - stan będzie taki sam ponieważ `A` doda element na koniec a `B` zdejmie jakiś inny element `x` z początku, który będzie inny niż `a` i nie zależnie od kolejności wykonania taki sam za każdym razem.

Gdy kolejka jest pusta z perspektywy wątku `C` stan kolejki będzie taki sam niezależnie od tego czy wykona się pierwszy wątek `B` a następnie `A` od samego wykonania `A`, ponieważ wykonanie `dec` na pustej kolejce z perspektywy `C` ma taki sam efekt jak nie wykonanie go wcale. Co znaczy, że można osiągnąć ten sam stan kolejki poprzez ruchy przenoszące nas odpowiednio do 0 walentnego stanu i 1 walentnego stanu.

## Zadanie 5
:::success
Autor: Marcin Sarnecki
:::

* Załóżmy nie wprost, że zwrócono wartość różną od zaproponowanych przez dwa wątki. Zauważmy, że aby do tego doszło, wątek pierwszy musiałby wykonać $return\space proposed[j];$ na niezainicjowanej $proposed[j]$. Dochodzimy do sprzeczności, ponieważ wtedy musiało zajść $position[i] < position[j]$, co implikuje przypisanie wartości $proposed[j]$

* Załóżmy nie wprost, że dwa wątki zwróciły różne wartości.

Rozważmy przypadek wykonania

if (position[i] < position[j]) // I am behind you
return proposed[j];

Jeden z wątków musiał wykonać tego ifa jako pierwszy, wartości $position[]$ mogą się tylko zwiększać, zatem niemożliwe jest, że drugi wątek następnie odczytał swoje position jako mniejsze

Rozważmy przypadek wykonania

if (position[i] > position[j] + speed[j]) // I am far ahead of you
return proposed[i];

Jeden z wątków musiał wykonać tego ifa jako pierwszy, drugi z wątków na pewno wykona drugiego ifa zwracającego $proposed[j]$

* To rozwiązanie nie jest $wait-free$, jeśli wartości $position[]$ są takie same, to wolniejszy wątek może wykonać trzy razy pętlę $while$, następnie szybszy wątek wykona raz pętle i wracamy so sytuacji z równymi $position[]$

## Zadanie 6
:::success
Autor: Julia Matuszewska
:::


---

---

### 1. Pojedyńczy obiekt klasy StickyBit wystarczy, by rozwiązać problem nieczekającego konsensusu binarnego dla dowolnej liczby wątków

Weźmy $n$ wątków. Niech zapisują one jednocześnie do obiektu klasy **StickyBit**

**Możliwe przypadki:**
1. Jeżeli wszystkie zapisywały $A$ to **StickyBit** zwróci $A$
2. Jeżeli część zapisywała $A$, a drugie $B$ ($B$ może być równe lub różne od $A$), to wtedy wszystkie zapisane wartości poza pierwszą zostaną zignorowane.
Wtedy stanem obiektu będzie wartość zapisana jako pierwsza.

### 2. Przy pomocy tablicy zawierającej $log_2m$ obiektów StickyBit i pewnej liczby atomowych rejestrów można podać nieczekającą implementację protokołu konsensusu dla dowolnej liczby wątków, gdy istnieje $m$ możliwych wartości wejściowych

pseudokod działania

m <- ilosc mozliwych wartosci wejsciowych
N <- ilosc watkow
// tworzymy tablice obiektow StickyBit o wielkosci log2m
StickyBit wynik[log2m] 
MRSW[N] // dla kazdego watku tworzymy rejestr MRSW

dla kazdego watku wykonujemy:
    dla i w 0..log2m:
        // bit niezapisany lub zgodny
        jezeli wynik[i] == ⊥ || wynik[i] == MRSW[ID]: 
            // i-ty bit wartosci z rejestru tmp watku ID
            b_i = MRSW[ID][i] 
            wynik[i] = b_i // zapisujemy i-ty bit wyniku
        wpp:
            //przeszukujemy inne watki w poszukiwaniu
            //wartosci ktora zgadza sie z prefiksem dotychczasowym wyniku
            dla ID2 w 0..N: 
                jezeli wynik[0..i] == MRSW[ID2][0..i] 
                    //podmieniamy wartosc naszego watku w rejestrze na
                    //zgodna wartosc w innym watku
                    MRSW[ID] = MRSW[ID2] 
    zwroc wynik
                    
         

**Pomysł:**
Niech każdy bit liczby będzie obiektem klasy **StickyBit**, oraz weźmy tablicę T atomowych komórek MRSW, po jednej dla każdego wątku.
Na początku każdy wątek wpisze swoją wartość do swojej komórki, a potem dla każdego wątku będziemy iterować się po kolejnych bitach.

Dla bitu $b_i$ robimy `write(b_i)` do $i$-tego StickyBity, a potem zczytujemy z tego bitu wartość.

Jeżeli jest taka sama, to kontynuujemy.
Jeżeli jest różna, iterujemy się po T i znajdujemy wartość $v$ innego wątku, którą prefiksem jest aktualnie przeczytany stan ze StickyBitów, i kontynuujemy algorytm dla wartości $v$. Po zakończeniu iteracji zwracamy tę liczbę.

W ten sposób każdy wątek zwróci tę samą wartość.

Zatem algorytm rozwiązuje problem konsensusu dla $M$ wartości i $n$ wątków

## Zadanie 7
:::success
Autor: Wiktor Bukowski
:::


Pokażemy implementację protokołu przybliżonej zgody używającej jedynie rejestrów atomowych. Tym samym udowodnimy, że poziom konsensusu obiektów przybliżonej zgody jest równy 1.

Protokół:

1. Oba rejestry ustawiamy początkowo na wartości -1.
2. Każdy wątek zapisuje swoją wartość do własnego rejestru.
3. Jeśli drugi rejestr ma wciąż wartość -1 - zwracamy swoją wartość.
4. Każdy wątek uaktualnia swój rejestr w następujący sposób:
    a) jeśli wartość rejestru drugiego wątku jest oddalona o co najwyżej eps, to zwraca wynik
    b) jeśli nie, to do swojego rejestru zapisuje średnią z wartości rejestrów i powtarza krok 4

Protokół jest `wait-free`, ponieważ każdy z wątków skończy swoje działanie niezależnie od stanu drugiego.

## Zadanie 8
:::success
Autor: Marcin Wróbel
:::

public class FIFOwithPeekConsensus<T> extends ConsensusProtocol<T> {
    FIFOQueue fifoQueue;
    T[] propose;
    
    public FIFOwithPeekConsensus(int n) {
        fifoQueue = new FIFOQueue();
        propose = new T[n];
    }
    
    T decide (T value) {
        int me = ThreadID.get();
        propose[me] = value;
        fifoQueue.enq(me);
        return propose[fifoQueue.peek()];
    }
    
}

1. Powyższa implementacja jest wait-free.
2. Wartość zwracana przez decide() jest jedną z wartości zaproponowanych przez wątki, ponieważ kolejka q zawiera tylko id tych wątków, które już wpisały swoją propozycję do propose[];
3. Metoda ta zwraca dla każdego wątku tą samą wartość. Jest to wartość, którą zaproponował wątek, którego id jest pierwsze w kolejce.

Powyższe właściwości zachodzą dla dowolnej liczby wątków, więc poziom konsensusu wynosi ∞.

## Zadanie 9
:::success
Autor: Maksymilian Komarnicki
:::

_Czyste podwójne zbieranie_ - tablice zwracane przez dwa kolejne wywołania metody collect() są równe.

_Lemat 1_
Jeśli wątek skanujący A wykonał czyste podwójne zbieranie, to wartości które zwrócił były prawdziwymi wartościami rejestrów.

Załóżmy, że wątek A wykonał czyste podwójne zbieranie, ale wartości które zwrócił nigdy nie były wartościami rejestrów. Skoro wykonał czyste podwójne zbieranie, to znaczy, że wszystkie wartości _stamp_ z pierwszego zbierania odpowiadały wszystkim wartością _stamp_ z drugiego zbierania. Oznacza to, że pomiędzy odczytami i-tego rejestru nie było żadnej zmiany, zatem pomiędzy ostatnim odczytem pierwszego zbierania, a pierwszym odczytem drugiego zbierania nie miała miejsca żadna zmiana rejestrów. Zatem zwrócone wartości istniały w przerwie między zbieraniami.

_Lemat 2_
Jeśli wątek skanujący A zaobserwował zmiany w rejestrze modyfikownym przez wątek B podczas dwóch różnych podwójnych zbierań, to wartość rejestru wątku B przeczytana podczas ostatniego zbierania była zapisana przez wywołanie update() rozpoczęte po pierwszym rozpoczętym zbieraniu.

Załóżmy, że wątek skanujący A zaobserwował zmiany w rejestrze modyfikownym przez wątek B podczas dwóch różnych podwójnych zbierań. Przypuśćmy, że wartość rejestru wątku B przeczytana podczas ostatniego zbierania była zapisane przez wywołania update() rozpoczęte przed rozpoczęciem pierwszego zbierania. W takiej sytuacji ten update() byłby jedynym wykonanym przez wątek B w czasie wykonywania skanu przez wątek A, co przeczy temu co zaobserwował wątek A.

_Lemat 3_
Wartości zwrócone przez scan() były wartościami rejestrów pomiędzy wywołaniem metody, a zwróceniem wyniku.

Jeśli miało miejsce czyste podwójne zbieranie, to twierdzenie wynika z _Lematu 1_. Jeśli scan() zwrócił wartości rejestrów z rejestru jakiegoś wątku B, to z _Lematu 2_ wynika, że wartości te były uzyskane podczas wywołania scan(). Indukcyjnie wątek B wywołujący scan() w metodzie update() uzyskał rzeczywiste wartości rejestrów. Indukcje możemy zastosować maksymalnie n-1 razu, gdzie n to liczba wątków. Ostatecznie jakiś zagnieżdżony scan() wykona podwójne czyste zbieranie.

_Lemat 4_
Każde wywołanie scan() oraz update() są wolne od czekania.

Mamy dane n wątków. Dla pierwszego wywołania scan() może istnieć co najwyżej n-1 innych wątków modyfikujących rejestry. Po n+1 operacji podwójnego zbierania, albo któreś będzie czyste, albo jakiś wątek zmienił drugi raz wartość swojego rejestru. Oznacza to, że w ciągu tego wywołania scan() maksymalnie będzie mieć miejsce n wywołań update(). Każdy update() wywołuje scan(), z tym, że liczba wątków, które mogą modyfikować rejestry zmniejsza się. Z tego wynika, że scan() oraz update() są wolne od czekania.