# Ćwiczenia 7, grupa cz. 16-18, 30 listopada 2023

###### tags: `PRW23` `ć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 |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- | --- | --- |
Dominik Baziuk | X | X | X | | | | | | ==X== |
Paweł Borek | | | X | | X | X | | | |
Arti Brzozowski | X | X | | | | | | | |
Mateusz Golisz | | | | | | | | | |
Kacper Jóźwiak | X | | X | | X | X | | | X |
Julia Konefał | | | | | | | | | |
Adam Korta | x | x | x | | x | | | | |
Jakub Mikołajczyk | ==X== | X | X | | | X | | | X |
Bartosz Morasz | X | X | | | | | | | |
Andrzej Morawski | | | | | | | | | |
Aleksandra Nicpoń | ==x== | x | x | | x | | | | |
Mateusz Reis | X | X | | | | | | | |
Tomasz Stachurski | x | | ==x== | | | x | | x | x |
Marcel Szelwiga | | | | | | | | | |
Volha Tsekalo | x | |==x==| | x | x | | | x |
Martyna Wybraniec | x | x | x | | | | | | |
Denys Zinoviev | | | | | | | | | |
Dominik Olejarz | | | | | | | | | |
:::

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

## Zadanie 1
:::success
Autor: Aleksandra Nicpoń
:::

### Zadanie 1
Implementacja:

Update() jest metodą nieczekającą, zwiększającą wartość znacznika czasu.
Scan() jest metodą niehamowaną.

Przegląd (collect) to czynność kopiowania wartości rejestru jedna po drugiej do tablicy.
Jeśli wykonamy dwa przeglądy jeden po drugim i w obu odczytany zostanie ten sam zbiór znaczników czasu to wiemy że był taki przedział czasu w którym żaden wątek nie aktualizował rejestru, a zatem wynikiem jest migawka stanu systemu po zakończeniu pierwszego przeglądu.

Pokażmy że konstrukcja zawsze zwraca poprawne wartości.
*Dowód*
Załóżmy, że funkcja scan() zwróciła nam pewien stan tablicy z pomiędzy współbieżnych wywołań update(). A zatem musiał zajść warunek ```Array.equals(oldCopy, newCopy) == true```. Ponieważ porównujemy znaczniki czasu i są one takie same w obu kopiach to oznacza że pomiędzy ```oldCopy = collect``` a ```newCopy = collect``` nie nastąpił żaden update. Skoro dwie kopie są sobie równe to oznacza że są prawidłową migawką. Sprzeczność.

Możemy zauważyć że gdy wielokrotnie wywołamy metode update i scan nie będzie mógł wykonac dwóch przeglądów między nimi to cały czas będzie zachodził warunek ```Array.equals(oldCopy, newCopy) == false```. Ale wiemy że scan() jest metodą niehamowaną tzn. ze gdy odizolujemy scan() od innych wątków to na pewno się on zakończy.

Metoda update() jest metodą lock-free to znaczy nie ma jak się zapętlić, zawsze robi pewien postęp.

## Zadanie 2
:::success
Autor: Adam Korta
:::

W poprzednim zadaniu metoda scan() była tylko metodą niehamowaną. W tym zadaniu rozważymy jak zamienić ją w metodę nieczekającą.

* Lemat 1
Jeżeli wątek skanujący zrobi zgodny przegląd podwójny, wówczas zwróci wartości które istniały w rejestrze w pewnym stanie wykonania.

* D-d
Jeśli w przedziale między ostatnim odczytem przeglądu nr. 1 a pierwszym odczytem nr. 2 został zaktualizowany jakiś rejestr etykiety się nie zgadzają i podwójny przegląd nie będzie zgodny.

Każde wywołanie update() może pomóc wywołaniu scan() któremu wejdzie w drogę wykonująć migawkę przed zmodyfikowaniem jej rejestru. Jeżeli scan() nie uda się wykonać podwójnego przeglądu to może użyć wtedy migawki jednego z wywołania metody update().

Możemy jednak zauważyć pewien problem. Jeżeli wątek A nie zrobi zgodnego przeglądu ponieważ inny wątek B wykonał ruch (zakończył wywoływanie metody update()), to niestety wątek A nie może wziąć najświeższej migawki wątku B.

Jak widzimy możliwa jest taka sytuacja, że wątek A zobaczy ruch wątku B, ale migawka wątku B została wykonana zanim rozpoczęło się wywołanie metody scan() wątku A.

A zatem możemy zastosować takie podejście: jeżeli skanujący wątek A wykonując swoje przeglądy zobaczy dwa razy że wątek B wykonuje ruch, oznacza to że wątek B wykonał pełne wywołanie metody update() w przedziale metody scan() wątku A. Wtedy migawka wątku B dla A będzie prawidłowa.
* Lemat 2
Jeżeli wątek skanujący A zauważy zmiany w etykiecie innego wątku B podczas dwóch różnych podwójnych przeglądów, wtedy wartość B odczytana w trakcie ostatniego przeglądu została zapisana przez update() które rozpoczęło się po rozpoczęciu pierwszego z czterech przeglądów.

* D-d
Podczas wywołania scan() dwie kolejne operacje odczytu przez A rejestru wątku B zwracają różne wartości etykiet, wtedy przynajmniej jedna operacja zapisu przez wątek B miała miejsce między tymi dwiema operacjami odczytu. Skoro wątek B zapisuje w swoim rejestrze w ostatnim etapie wywołania metody update() dlatego wywolanie tej metody zakonczylo sie w jakims momencie po pierwszej operacji odczytu przez wątek A, a zapis innej operacji miał miejsce między ostatnią parą operacji odczytu przez wątek A.



Każda wartość zapisana w rejestrze ma trzy pola: znacznik czasu, value, oraz snap.
Jak widzimy w implementacji każde wywołanie metody update() wywołuje metodę scan() i dołącza go do pola snap.
Wątek skanujący tworzy tablicę moved[], gdzie zapisuje informacje o wątkach których ruchy zostały zauważone w trakcie skanowania. Przydaje się to gdy zajdzie warunek ```oldCopy[j].stamp != newCopy[j].stamp``` (zmieniła się etykieta któregoś z wątków). Wtedy sprawdzamy w tablicy moved[] czy wątek wykonał ruch po raz drugi. Jeśli tak to zwracamy wynik w innym przypadku aktualizujemy tablice i kontynuujemy pętle.

*Przeprowadźmy dowód migawki nieczekającej.*

* Lemat 3
Wartości zwrócone przez metodę scan() znajdowały się w rejestrach w pewnym stanie

* D-d
a) Wywołanie scan() wykonało zgody przegląd podwójny - Lemat 1

b) Wywołanie pobrało wartość skanowania z rejestru innego wątku B - Lemat 2

c) Wywołanie metody scan() wątku B wykonało zgodny przegląd podwójny - Lemat 1

d) Istnieje osadzone wywołanie metody scan() przez wątek C, mające miejsce w przedziale wywołania metody scan() wątku B.

* Lemat 4
Każde wywołanie metody scan() lub update() wraca po maksymalnie O(n^2) operacjach odczytu lub zapisu

Dla danej metody scan() ponieważ istnieje tylko n-1 innych wątków po n+1 podwójnych przeglądach jeden jest zgodny albo zauważono, że jakiś inny wątek dwukrotnie wykonał ruch (zasada szufladkowa).

## Zadanie 3
:::success
Autor: Volha Tsekalo
:::
Załóżmy nie wprost, że istnieje nieczekająca implementacja protokołu binarnego konsensusu dla n wątków, używająca jedynie rejestrów atomowych.
Pokażemy, że przy takim założeniu istnieje nieczekająca implementacja protokołu binarnego konsensusu, używająca jedynie rejestrów atomowych dla n = 2.

Na początku mamy 2 wątki, które ustalają miedzy sobą wartość. Nastepnie uruchamiają się pozostałe n-2 i ich rozwiazaniem jest to, które ustaliły pierwsze 2.
Ale wiemy z wykładu, że implementacja dla dwóch wątków nie istnieje. Zatem nie mamy rozwiązania też dla n wątków. Mamy sprzeczność.

Zatem można wywnioskować, że nie istnieje nieczekająca implementacja protokołu binarnego konsensusu dla n wątków używająca jedynie rejestrów atomowych.

## Zadanie 4
:::success
Autor: Jakub Mikołajczyk
:::

class NValuedConsensus<T> {
  private BinaryConsensus cons[];
  private AtomicRegister<T> propose[];
  
  public NValuedConsensus() {
    propose = new AtomicRegister<T>[N];
    cons = new BinaryConsensus[N];
  }
  
  public T decide(T value) {
    int self = ThreadID.get();
    propose[self] = value;
    cons[self].decide(true);
      
    for(int i = 0; i < N; i++)
        if(cons[i].decide(false))
            return propose[i];
  }
}

**Wartość zwracana przez decide() jest jedną z wartości zaproponowanych przez wątki**

Załóżmy, że żadnemu wątkowi nie udało się ustawić konsensusu na true, zatem każdy wątek musiał być poprzedzony przez inny wątek, ale żeby to zrobić musi najpierw zakończyć ustawienie swojego konsensusu na true. Sprzeczność

**Metoda ta zwraca tę samą wartość każdemu wątkowi**

Weźmy dowolne 2 wątki (A, B) i załóżmy, że zwróciły różne wartości oraz BSO A < B

Żeby wątki zwróciły różne wartości dla wątku A musi zajść ```cons[A].decide(false) == true```, a dla wątku B ```cons[A].decide(false) == false``` oraz ```cons[B].decide(false) == true```. Sprzeczność.

## Zadanie 5
:::success
Autor: Paweł Borek
:::

Załóżmy nie wprost, że istnieje algorytm implementujący protokół konsensusu dla wątków A, B i C. Wiem z wykładu, że protokół ma stan krytyczny $s$. Bez straty ogólności zakładamy, że następny krok A przenosi protokół do stanu 0-walencyjnego a następny krok B do stanu 1-walencyjnego.

A i B będą wywoływać metodę współdzielonego obiektu, bo inaczej otrzymamy ten sam stan w obu przypadkach. Wiemy, też że nie będą czytać ani pisać do atomowego rejestru bo z wykładu wiemy, że taka sytuacja nie może być stanem krytycznym.

1° Załóżmy, że A i B oba wywołują `deq()`. Niech $s'$ oznacza stan w którym najpierw A a potem B wykonał `deq()` a $s''$ stan w którym kolejność wywołań była odwrotna. Pierwszy jest 0-walencyjny a drugi 1-walencyjny. Jeśli C będzie działał solo od $s'$ to wybierze 0 a jeśli od $s''$ to 1. Ale $s'$ i $s''$ są dla C nierozróżnialne więc otrzymujemy sprzeczność.


2° Załóżmy, że jeden wątek wykonuje `enq(a)` a drugi `deq()`. Bez straty ogólności przyjmijmy, że A wykonuje `enq(a)` a B `deq()`. Jeśli kolejka jest niepusta to mamy sprzeczność bo C nie potrafi rozróżnić kolejności wykonania tych metod. Jeśli kolejka jest niepusta to C nie będzie potrafił rozróżnić sytuacji w której B wykonuje `deq()` na pustej kolejce a następnie A wykonuje `enq()` od sytuacji w której tylko A wykonuje swoją operację, czyli wstawia na kolejkę. Zatem również otrzymujemy sprzeczność.

3° Załóżmy, że A wywołuje `enq(a)` a B `enq(b)`.
Niech $s'$ oznacza stan na końcu poniższego wywołania:
1. Najpierw A wstawia a, a potem B b.
2. Tylko A działa dopóki nie zdejmie a.
3. Tylko B działa dopóki nie zdejmie b.

Niech $a''$ oznacza alternatywne wywołanie:
1. Najpierw B wstawia b, a potem A a.
2. Tylko A działa dopóki nie zdejmie b.
3. Tylko B działa dopóki nie zdejmie a.
$s'$ jest 0-walencyjne a $s''$ 1-walencyjne. Wywołania A są identyczne aż do momentu gdy zdejmie a lub b, później nie wykonuje już żadnych kroków. To samo można powiedzieć o B. Zatem $s'$ i $s''$ są nierozróżnialne dla C, czyli otrzymujemy sprzeczność.


## Zadanie 6
:::success
Autor: Jakub Mikołajczyk
:::

public class ConsensusProposal {
    Boolean proposed[] = new Boolean[2];
    Integer[] speed = new Integer[2];
    Integer[] position = new Integer[2];
    public ConsensusProposal(){
        position[0] = 0;
        position[1] = 0;
        speed[0] = 3;
        speed[1] = 1;
    }
    public Boolean decide(Boolean value) {
        int i = ThreadID.get(); //0 or 1
        int j = 1 - i;
        proposed[i] = value;
        while (true) {
            position[i] = position[i] + speed[i];
            if (position[i] > position[j] + speed[j]) // I am far ahead of you
                return proposed[i];
            else if (position[i] < position[j]) // I am behind you
                return proposed[j];
        } 
    }
}

**Wartość zwracana przez decide() jest jedną z wartości zaproponowanych przez wątki**

Wątki zawsze zwracają propose po przypisaniu wartości. Zatem jeśli działają 2 wątki to zwrócą one zaproponowaną wartość.

Zauważmy też, że nie zwrócimy nigdy nie zainicjowanej wartości:

1. Działa tylko wątek 0

i = 0
j = 1
    
//W 1 wykonaniu while
position[i] = 3
    
if (position[i] > position[j] + speed[j]) // I am far ahead of you
    return proposed[i];

2. Działa tylko wątek 1

i = 1
j = 0
    
//W 4 wykonaniu while
position[i] = 4
    
if (position[i] > position[j] + speed[j]) // I am far ahead of you
    return proposed[i];

**Metoda ta zwraca tę samą wartość obydwu wątkom**

Załóżmy nie wprost, że dwa wątki zwróciły różne wartości. (Wykonały tego samego ifa)

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

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]$, ponieważ nie wyprzedzi pierwszego wątku.

**Dlaczego ten wynik nie jest sprzeczny z faktem, że poziom konsensusu
dla rejestrów atomowych wynosi 1?**

To rozwiązanie nie jest $wait-free$. Jeżeli mamy sytuację, że ```position[A] = position[B]``` procesy mogą wykonywać się w taki sposób, że na każdy obrót while w A będą przypadały 3 obroty while w B to pętla nie zakończy się. Natomiast poziomy konsensusu są określane dla algorytmów wait-free.

## Zadanie 7
:::success
Autor: Tomasz Stachurski
:::

#### pojedyńczy obiekt klasy StickyBit

Każdy wątek zapisuje swoją wartość. StickyBit zapamięta pierwszą zapisaną wartość, więc jak wątki zaczną ją czytać to wszystkie się zgodzą (bo mają to samo).

#### tablica log(m) obiektów StickyBit

Niech i-ty bit wyniku będzie obiektem klasy StickyBit zapisanym w rejestrze `wynik[i]`.
Każdy z `n` wątków dostanie śwój rejestr MRSW `R`.

Algorytm:
1. Dla każdego wątku `R[i] = wartość i-tego wątku`
2. Dla każdego wątku wykonujemy:
2.1. Dla każdego `i = 0...log(m)`:
2.1.1. Jeśli `wynik[i]` jest niezapisany lub zgodny z `R[i]` to zapisujemy `wynik[i] = R[ID][i]`
2.1.2. Wpp. szukamy innego wątku, którego wartość zgadza się z prefiksem dotychczasowego wyniku
2.1.2. czyli dla każdego `ID2 = 0...n` jeśli `wynik[0...i] == R[ID2][0...i]` to `R[ID] = R[ID2]`

Zatem każdy wątek zwróci tę samą wartość.

## Zadanie 8
:::success
Autor: Tomasz Stachurski
:::

Pokażemy, że poziom konsensusu dla obiektów przybliżonej zgodny jest równy 1. Skonstruujemy protokół używając jedynie rejestrów atomowych.

1. Ustaw rejestry na -1
2. Każdy wątek zapisuje swoją wartość do swojego rejestru
3. Jeśli drugi wątek ma wciąż wartosć -1, to zwracamy swoją wartość
4. Każdy wątek aktualizuje swoją wartość:
    4.1. Jeśli |ya - yb| <= epsilon, to zwraca swoją wartość
    4.2. Wpp. zapisuje |ya - yb|/2 do swojego rejestru i wraca do kroku 4

Powyższy protokół jest `wait-free`, bo każdy wątek działa niezależnie od stanu drugiego wątku.

## Zadanie 9
:::success
Autor: Dominik Baziuk
:::

:::info
Zadanie 9. Mamy dane wielowątkowe nieczekające kolejki FIFO,
które oprócz metod enq(x) i deq() mają jeszcze metodę peek(),
która zwraca pierwszy element kolejki, ale w odróżnieniu od
deq(), nie usuwa go stamtąd. Pokaż, że takie kolejki mają
poziom konsensusu równy ∞.
:::


### Propozycja protokołu
- Kolejka Q
- Tablica T (tyle miejsc ile wątków)

Funkcja Decide dla wątków:
- Sprawdź swoje ID za pomocą ThreadID
- przypisz swoją wartość do swojej komórki (stwierdź która komórka za pomocą swojego ID)
- wrzuć swoje ID do kolejki
- weź ID z początku kolejki za pomocą peek()
- odczytaj Tablice T pod wartością tego ID z kolejki

### Poprawność
1. Jest wait-free, ponieważ operacje wykonują się jedna po drugiej i się nie zatrzymują.
2. Decide zwróci wartość zaproponowaną przez jakiś wątek.Jeśli jakieś ID jest w kolejce to znaczy że wątek już coś zapisał do tablicy T jako swoją propozycje.
3. Wszystkie wątki zwrócą tą samą wartość. A dokładniej zwrócą wartość, którą zaproponował wątek, który jako pierwszy wrzucił swoje id do kolejki. (wyższość operacji peek nad deq).

### poziom konsensusu
Jest on równy nieskończoność, ponieważ ten protokół działa dla dowolnej liczby wątków.