# Ćwiczenia 7, grupa śr. 10-12, 6 grudnia 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 |
| ----------------------:| --- | --- | --- | --- | --- | --- | --- | --- | --- |
Mikołaj Balwicki | | | | | | | | | |
Konrad Kowalczyk | X | | X | X | X | X | | | X |
Jakub Krzyżowski | | | | | | | | | |
Łukasz Magnuszewski | | | | | | | | | |
Marcin Majchrzyk | X | | | X | | X | X | X | X |
Jan Marek | X | X | X | | X | X | | | |
Marcin Mierzejewski | | | | | | | | | |
Juan Jose Nieto Ruiz | | | | | | | x | x | x |
Konrad Oleksy | | | | | | | | | |
Javier Rábago Montero | X | X | X | | X | X | X | X | X |
Michał Mękarski | X | X | X | | X | X | | | X |
:::

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

## Zadanie 1
:::success
Autor: Marcin Majchrzyk
:::

public class SimpleSnapshot<T> implements Snapshot<T> {
    private StampedValue<T>[] a_table; // array of atomic MRSW registers
    
    public SimpleSnapshot(int capacity, T init) {
        a_table = (StampedValue<T>[]) new StampedValue[capacity];
        for (int i = 0; i < capacity; i++) {
            a_table[i] = new StampedValue<T>(init);
        }
    }
    
    public void update(T value) {
        int me = ThreadID.get();
        StampedValue<T> oldValue = a_table[me];
        StampedValue<T> newValue = new StampedValue<T>((oldValue.stamp)+1, value);
        a_table[me] = newValue;
    }
    
    private StampedValue<T>[] collect() {
        StampedValue<T>[] copy = (StampedValue<T>[]) new StampedValue[a_table.length];
        
        for (int j = 0; j < a_table.length; j++)
            copy[j] = a_table[j];
        
        return copy;
    }
    
    public T[] scan() {
        StampedValue<T>[] oldCopy, newCopy;
        oldCopy = collect();
        
        collect: while (true) {
            newCopy = collect();
            if (! Arrays.equals(oldCopy, newCopy)) {
                oldCopy = newCopy;
                continue collect;
            }
            
            T[] result = (T[]) new Object[a_table.length];
            for (int j = 0; j < a_table.length; j++)
                result[j] = newCopy[j].value;
            
            return result;
        }
    }
}

1. Dowód poprawności
Załóżmy nie wprost, że migawka nie działa prawidłowo i zwróciła błędny wynik. Aby do tego doszło, musiało wykonać się ```Arrays.equals(oldCopy, newCopy)``` i zwrócić wartość ```true```. Może do tego dojść tylko wtedy, gdy nie doszło do zmiany żadnej sygnatury, co oznacza, że nie doszło do zmiany wartości w czasie kopiowania. Tym samym tablica jest poprawnym snapshotem, sprzeczność.

2. Metoda scan
W najgorszym przypadku metoda scan może zapętlić się w nieskończoność, jednak w przypadku zatrzymania pozostałych wątków metoda na pewno zakończy się, zatem jest obstruction-free.

3. Metoda update
W metodzie nie ma pętli zatem wywołanie zawsze dokonuje postęp, co oznacza, że metoda jest lock-free.

## Zadanie 2
:::success
Autor: Jan Marek
:::

- Atomowa migawka - atomowy odczyt wielu wartości rejestru. Atomowa migawka buduje momentalny widok tablicy atomowych rejestrów.
- Migawka nieczekająca - oznacza, że wątek będzie mógł wykonać momentalną migawkę pamięci, nie opóźniając innych wątków
- collect (przegląd) - nieatomowa 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, więc znacznikiem przeglądu jest migawka stanu systemu natychmiast po zakończeniu pierwszego przeglądu. Taką parę przeglądów nazywamy `zgodnym przeglądem podwójnym (clean double collect)`.

Naszym celem jest zmiana metody scan(), tak aby była nieczekająca (zamiast niehamowana).
Aby scan() była nieczekająca, każde wywołanie update() może pomóc wywołaniu scan(), któremu wejdzie w drogę, wykonując migawkę przed zmodyfikowaniem jej rejestru. Jeśli scan() nie uda się wykonać podwójnego przeglądu, to może użyć jako własnej migawki jednego z przeszkadzających jej w działaniu wywołania metody update().
Problem w tym, aby upewnić się, że migawka uzyskana od pomagającego wywołania update() jest linearyzowalna w obrębie przedziału wywołania metody scan().

Mówimy, że wątek `wykonuje ruch`, jeśli zakończy wywołanie metody update(). Jeśli wątkowi A nie uda się zrobić zgodnego przeglądu, ponieważ wątek B wykonał ruch, to czy wtedy wątek A może sobie po prostu wziąć najświeższą migawkę wątku B jak własną? NIE - na poniższym rysunku widzimy, że możliwa jest taka sytuacja, że wątek A zobaczy ruch wątku B, choć migawka wątku B została wykonana, zanim rozpoczęło się wywołanie metody scan() wątku A, a więc migawka ta nie została wykonana w przedziale skanowania przez wątek A.


**Konstrukcja nieczekająca opiera się na następującym spostrzeżeniu:**
Jeśli skanujący wątek A wykonując swoje wielokrotne przeglądy zobaczy 2 razy, że wątek B wykonuje ruch, to oznacza, że wątek B wykonał pełne wywołanie metody update() w przedziale metody skan wątku A, więc migawka wątku B dla wątku A jest prawidłowa.

**ALGORYTM MIGAWKI NIECZEKAJĄCEJ:**


Każde wywołanie update() wywołuje scan() i dołącza wynik do pola snap.

Każda wartość zapisana w rejestrze ma strukturę:
- `stamp` - wartość ta rośnie za każdym razem, gdy wątek aktualizuje swoją wartość
- `value` - faktyczna wartość rejestru
- `snap` - ostatni skan tego wątku

Metoda scan() tworzy boolowską tablicę `moved[]` zawierającą informacje o wątkach, których ruchy zostały zauważone w trakcie skanowania.
Tak jak w przypadku migawki 'SimpleSnapshot', każdy wątek wykonuje dwa przeglądy (wiersze 14, 16) i sprawdza, czy zmieniła się etykieta któregoś wątku. Jeśli się nie zmieniła, to przegląd jest zgodny, a skanowanie zwraca wynik tego przeglądu. Jeśli jednak zmieniła się etykieta któregoś wątku (wiersz 18), to wątek skanujący sprawdza w tablicy `moved[]`, czy dany wątek wykonałruch po raz drugi (wiersz 19). Jeżeli tak jest, to zwraca wynik skanowania tego wątku (wiersz 20), a w przeciwnym wypadku aktualizuje tablicę `moved[]` i wznawia zewnętrzną pętlę (wiersz 21).

**Poprawność**

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

Dowód.
Popatrzmy na przedział między ostatnim odczytem przeglądu 1, a pierwszym odczytem przeglądu 2. Jeśli w tym przedziale został zaaktualizowany jakiś rejestr, to etykiety nie będą się zgadzały, a podwójny przegląd nie będzie zgodny.

Lemat 2.
Jeśli skanujący wątek A zauważy zmiany w etykiecie innego wątku B w trakcie dwóch różnych podwójnych przeglądów, to wartość rejestru B odczytana w trakcie ostatniego przeglądu została zapisana przez wywołanie metody update(), które rozpoczęło się po rozpoczęciu pierwszego z czterech przeglądów.

Dowód.
Jeżeli w trakcie metody scan() dwie kolejne operacje odczytu przez wątek A rejestru wątku B zwracają różne wartości etykiet, to przynajmniej jedna operacja zapisu przez wątek B miała miejsce między tymi dwiema operacjami odczytu. Wątek B zapisuje w swoim rejestrze na ostatnim etapie wywoływania metody update(), dlatego wywołanie update() przez wątek B zakończyło się w jakimś momencie po pierwszej operacji odczytu przez A, a zapis innej operacji wydarzył się między ostatnią parą operacji odczytu przez A. Skoro tylko wątek B zapisuje w swoim rejestrze, to z tego wynika, że powyższe twierdzenie jest prawdziwe.

Lemat 3.
Wartości zwrócone przez scan() znajdowały się w rejestrach w pewnym stanie między inwokacją a odpowiedzią wykonania.

Dowód.
Jeśli:

- wywołanie scan() wykonało zgodny przegląd podwójny, to twierdzenie wynika z Lematu 1.

- wywołanie pobrało wartość skanowania z rejestru innego wątku B, to - zgodnie z Lematem 2 - wartość skanowania znalezioną w rejestrze B uzyskało wywołanie metody scan() przez wątek B, którego przedział jest położony między pierwszą a drugą operacją odczytu rejestru B przez wątek A.

- wywołanie scan() wątku B wykonało zgodny przegląd podwójny i rezultat wynika z Lematu 1.

- istnieje osadzone wywołanie scan() przez wątek C, mające miejsce w przedziale wywołania scan() wątku B. Ten argument można zastosować indukcyjnie gdy zauważymy, że zanim skończą się dostępne wątki, może być max. n-1 zagnieżdzonych wywołań, przy czym n to max. liczba wątków. A więc w końcu jakieś zagnieżdzone wywołanie scan() musi wykonać zgodny przegląd podwójny. [poniższy rysunek]


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

Dowód.
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 2-krotnie wykonał ruch. Wynika z tego, że wywołania scan() są NIECZEKAJĄCE, podobnie jak wywołania update().

Zgodnie z Lematem 3, wartości zwracane przez scan() tworzą migawkę, ponieważ wszystkie znajdują się w rejestrze w jakimś stanie w trakcie wywołania: w tym momencie wywołanie jest linearyzowalne. Podobnie można zlinearyzować wywołania metody update() w momencie zapisywania w rejestrze.

## Zadanie 3
:::success
Autor: Javier Rábago Montero
:::

Let’s assume that there is a wait-free implementation of consensus protocol for n threads (n>2).
Let's consider we have 5 threads. Now, out of this 5 threads, only 2 are fast enough to reach the consensus protocol and they agree with a value. This is a contradiction because as we know consensus for 2 threads is impossible.
So there’s no wait-free implementation of the binary consensus protocol for 𝑛 threads (𝑛 > 2) using only atomic registers, qed.

## Zadanie 4
:::success
Autor: Konrad Kowalczyk
:::


Każdą liczbę możemy przedstawić w postaci binarnej. Aby zaimplementować strukturę dla ogólnego konsensusu dla n wątków za pomocą jakiejś liczby struktur dla binarnych konsensusów, możemy dla każdego bitu naszych liczb wykonywać binarny konsensus.

Będziemy potrzebować n-elementowej tablicy rejestrów atomowych (`proposed`) oraz tablicy m-elementowej (gdzie m jest liczbą bitów liczby (zakładam, że każda liczba ma jest przedstawiona w takiej samej liczbie bitów, można zawsze dodać zera wiodące)) struktur dla konsensu binarnego (`binary_consensus`).

Stwórzmy hipotetyczną funkcję `decide()`:
- funkcja tworzy m-elementowy rejestr wynikowy
- funkcja bierze ID wątku, w którym jest wykonywana
- do tablicy rejestrów pod indeksem równym ID wątku zapisuje proponowaną wartość (`proposed[ID] = proposed_value`)
- dla każdego bitu po kolei wykonuje (pętla `for (int i = 0; i < m; i++)`):
- bierze i-ty bit (`current_bit`) swojej proponowanej wartości (`proposed_value`)
- wykonuje funkcję `decide(current_bit)` na i-tym elemencie tablicy `binary_consensus`
- do rejestru wynikowego na pozycji i-tej zapisuje wynik
- jeżeli wynik funkcji `decide(current_bit)` był różny od `current_bit` (tzn. wątek przegrał binarny konsensus w i-tej pętli), to wątek przeszukuje tablicę `proposed` w poszukiwaniu takiej liczby, której bity od 0 do i-tego zgadzają się z bitami w rejestrze wynikowym, a następnie tę liczbę ustawia jako jako swoją proponowaną wartość (`proposed_value = new_proper_value`)

Implementacja jest nieczekająca:
Funkcja `decide()` na nic nie czeka, każdy z elementów tablicy `binary_consensus` jest również nieczekający, a liczba bitów (m) w liczbie jest skończona.

Metoda `decide()` zwraca tę samą wartość wszystkim wątkom:
W rejestrze wynikowym dla każdego wątku na pozycji i-tej znajduje się wartość zwrócona przez i-ty element `binary_consensus`, a on jest taki sam dla każdego wątku, ponieważ struktury w `binary_consensus` poprawnie implementują binarny konsensus.

Wartość zwracana przez metodę `decide()` jest jedną z wartości zaproponowanych przez wątki:
Możemy to pokazać indukcyjnie. Chcemy pokazać, że w m-tej iteracji pętli pierwsze `m` bitów z rejestru wynikowego i pierwsze `m` bitów wartości `proposed_value` są sobie równe (czyli w całości te liczby są sobie równe), a wartość `proposed_value` jest jedną z wartości początkowych (tzn. zaproponowanych przez wątki na wejściu).

Baza indukcji:
Przed wywołaniem pętli `for` (0-owa iteracja) `proposed_value` jest wartością początkową, bo dopiero co została przypisana po raz pierwszy. Rejestr wynikowy jest pusty, a zatem pierwsze 0 bitów "jest sobie równe".

Założenie indukcyjne:
Załóżmy, że w i-tej iteracji pętli pierwsze `i` bitów z rejestru wynikowego i pierwsze `i` bitów wartości `proposed_value` są sobie równe, a wartość `proposed_value` jest jedną z wartości początkowych (tzn. zaproponowanych przez wątki na wejściu). Chcemy pokazać, że wtedy taka sama własność zajdzie dla (i+1)-szej iteracji pętli.

Krok indukcyjny:
Wartość `current_bit` to (i+1)-szy bit `proposed_value` dla danego wątku.
- Jeżeli wynik funkcji `decide(current_bit)` na `binary_consensus[i+1]` był równy `current_bit`, to znaczy, że w rejestrze wynikowym jako bit (i+1)-szy zapisze się `current_bit`. Skoro rejestr wynikowy był zgodny z `proposed_value` dla pierwszych `i` bitów oraz (i+1)-sze bity są sobie równe, to rejestr wynikowy i `proposed_value` są zgodne dla pierwszych `i+1` bitów. Wartość `proposed_value` nie zmienia się, więc naturalnie jest jedną z wartości początkowych.
- Jeżeli wynik funkcji `decide(current_bit)` na `binary_consensus[i+1]` był różny od `current_bit`, to wartość `proposed_value` zmieniamy na pewną wartość z tablicy rejestrów `proposed`, która zawiera tylko wartości początkowe (ponieważ nie jest ona zmieniana w pętli `for`). Ta wartość, zgodnie z implementacją, musi być zgodna z rejestrem wynikowym na `i+1` pierwszych bitach. Możemy zauważyć, że taka wartość zawsze istnieje:
- Załóżmy, że taka wartość nie istnieje. `binary_consensus[i+1]` w każdym wątku dostał (i+1)-szy bit liczby, która na pewno jest zgodna z rejestrem wynikowym na `i` pierwszych bitach. Skoro w tablicy `proposed` (zawierającej `proposed_value` każdego wątku) nie ma wartości zgodnej na pierwszych `i+1` bitach, to `binary_consensus[i+1]` musiał zwrócić bit, który nie jest (i+1)-szym bitem żadnej z `proposed_value`, co jest sprzeczne z jego własnościami.

Skoro tablica `proposed` zawiera tylko wartości początkowe, to nowa wartość `proposed_value` będzie jedną z wartości początkowych.

W takim razie po dojściu do m-tej iteracji pętli `proposed_value` dalej będzie jedną z wartości początkowych, a rejestr wynikowy oraz `proposed_value` będą sobie równe.

## Zadanie 5
:::success
Autor: Michał Mękarski
:::


## Zadanie 6
:::success
Autor: Javier Rábago Montero
:::


The returned value is always one of the proposed by the two threads. If proposed[j] was returned without being initialized it would return a value no one had proposed, but this can’t happen because if j hasn’t been initialized proposed[i] is the value returned always.
Both threads will return the same value: For 2 threads (we will call them A and B, being A the first to call decide()) to return different values they would return both statement in the if case at the same time or the one in the else if.
If the first thread returns first proposed[A], then position[A] > position[B] + speed [B] is true in that moment. From this point, B can only do at most one more loop where the if condition will always be false because of the speed difference and the else if condition will be true, because before B’s last loop, position[A] is always at least 2 units greater.
The other case would be A to return proposed[B], this would mean that at that point position[A] < position [B]. After A has returned the value it’s position won’t increase any more, but B’s position yes. B will loop until position[B] > position[A] + speed [A] is met and return proposed[B] too. While B loops position[B] < position[A] can’t happen, because the opposite was already true before position[A] stopped increasing.
Finally, consensus numbers refer to wait-free algorithms, but this isn’t wait-free as the while loop could run forever, so it doesn´t contradict that the consensus level for atomic registers is 1.

## Zadanie 7
:::success
Autor: Juan Jose Nieto Ruiz
:::
The StickyBit class describes objects that can have one of three possible states: ⊥, 0, 1. The initial state of the object is ⊥. The invocation of the write(v) method, where v is 0 or 1, has the following effects:

- If the object's state is ⊥, it changes to v.
- Otherwise, the state remains unchanged.

The read() method returns the current state of the object. Now, let's show how a single object of the StickyBit class can be used to solve the binary consensus problem without waiting for any number of threads:

1. **For a Single StickyBit Object:**
- Each thread proposes a value (0 or 1) and writes it to the StickyBit object.
- After writing, each thread reads the current value of the StickyBit object.
- All threads agree on the read value as the consensus.

This works because, according to the rules of the StickyBit class, once the object has a value other than ⊥, it will not change. Therefore, all threads will agree on the value set by the first thread that writes.

2. **Using an Array of StickyBit Objects and Atomic Registers:**
- Each thread is assigned a StickyBit object and an atomic MRSW register.
- Each thread proposes a value (0 or 1) and writes that value to its StickyBit object.
- Then, each thread reads the value of the StickyBit object and writes that value to its atomic MRSW register.
- Finally, each thread reads all values from the MRSW atomic registers of other threads and takes the value that appears most frequently.

This works because each thread, in addition to proposing its value, also communicates its proposal through its atomic MRSW register. Then, each thread can see all proposals and make a decision based on the value that is most common.

These solutions are possible due to the properties of the StickyBit class and the appropriate use of atomic registers. The logic behind these solutions is that each thread proposes its value and communicates with others to reach a consensus.

## Zadanie 8
:::success
Autor:Marcin Majchrzyk
:::

public class ApproxAgree
{
    AtomicInteger[] values = new AtomicInteger()[2];
    int epsilon;
    
    public ApproxAgree(int e) {
        values[0].set(-1);
        values[1].set(-1);
        
        epsilon = e;
    }
    
    public int decide(int x) {
        int id = ThreadID.get();
        
        values[id].set(x);
        if (values[1 - id].get() == -1) {
            return x;
        } 
        
        while (true) {
            int diff = Math.abs(values[id].get() - values[1 - id].get());
            if (diff <= epsilon) {
                return values[id].get();
            } else {
                values[id].set(diff / 2);
            }
        }
    }
};

## Zadanie 9
:::success
Autor: Konrad Kowalczyk
:::


Będziemy potrzebować kolejki FIFO implementującej `enq()`, `deq()` oraz `peek()`, a także tablicy rejestrów atomowych.

Stwórzmy hipotetyczną funkcję `decide()`:
- funkcja bierze ID wątku, w którym jest wykonywana
- do tablicy rejestrów pod indeksem równym ID wątku zapisuje proponowaną wartość
- używa funkcji `enq()`, żeby swoje ID wrzucić na koniec kolejki FIFO
- używa funkcji `peek()`, aby sprawdzić, jaki element znajduje się na początku kolejki
- zwraca element, który w tablicy rejestrów znajduje się pod indeksem o wartości ID, które zwróciła funkcja `peek()`

Zauważmy, że:
- funkcja `decide()` w żadnym momencie na nic nie czeka, a zatem implementacja ta jest nieczekająca
- funkcja `peek()` zwraca wartość dla ID z początku kolejki, a zatem którąś z wartości wrzuconych przez wątki (ponieważ wątki wrzucają swoje ID dopiero po ustawieniu wartości w tablicy rejestrów)
- początek kolejki pozostaje niezmienny (bo każde następne wywołanie `enq()` doda element na koniec kolejki), więc funkcja `peek()` dla każdego wątku zwróci tę samą wartość

Ilość wątków nie ma znaczenia, bo liczy się tylko ten wątek, który był pierwszy. Zatem poziom konsensusu wynosi ∞.