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

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

## Zadanie 1
:::success
Autor: Jakub Krzyżowski
:::

Załóżmy, że istnieje nieczekająca implementacja protokołu binarnego konsensusu używająca rejestrów MRSW: XA, XB, XC oraz rejestrów RMW: RAB, RBC, RAC.
Rozważmy stan krytyczny. Wiemy, że do takiego stanu dojdziemy z tego, że implementacja jest nieczekająca.
Załóżmy, że następna instrukcja wątku A przeniesie nas do poddrzewa 0-walentnego, a B do poddrzewa 1-walentnego.

Zauważmy, że jeśli A i B odczytają wartość dowolnego rejestru MRSW, to nie zmieni stanu programu, więc nie może być to sekcja krytyczna:

       < Stan krytyczny >
 A read /              \ B read
       < >             < >
 C solo |               | C solo
      < 0 >           < 1 >

Jeśli A wykona write, a B odczyta, to sytuacja wygląda podobnie:

       < Stan krytyczny >
 A write /              \ B read
       < >             < >
 B read |               | A write
       < >             < >
 C solo |               | C solo
      < 0 >           < 1 >

Jeśli A i B wykonają `compareAndSet` na RAB, to C nie może używać tego rejestru, więc stan wygląda dla niego dokładnie tak samo jak przed operacjami.

       < Stan krytyczny >
 A cAS  /              \ B cAS
       < >             < >
 B cAS  |               | A cAS
       < >             < >
 C solo |               | C solo
      < 0 >           < 1 >

Zauważmy, że jak wątki A i B piszą do różnych rejestrów to mogą to zrobić w dowolnej kolejności, a z perspektywy C stan będzie identyczny. Zatem, żeby C zauważył zmianę stanu jeden wątek musi nadpisać pracę drugiego, a więc muszą pisać do jednego rejestru widocznego dla C. Wykluczamy więc od razu rejestry MRSW, bo do nich może pisać jedynie pojedynczy wątek. A jedynym rejestrem RMW do którego jednocześnie może pisać i A i B jest niedostępny dla C, zatem C nie zobaczy jego stanu.

## Zadanie 2
:::success
Autor: Konrad Kowalczyk
:::


Weźmy rejestry typu RMW przypisane do wątków z poprzedniego zadania (RAB, RAC, RBC) i zainicjalizujmy je wartościami, których nie będą proponowały wątki, np. `-1`. Wartości proponowane przez wątki będą trzymane w rejestrach atomowych przypisanych do wątków.

Stwórzmy hipotetyczną funkcję `decide()` (bez straty ogólności dla wątku A):
- funkcja wywołuje `double_cAS(RAB, RAC, -1, A)` w warunku `if`
- jeśli zwróci `true`, to zwraca wartość z własnego rejestru atomowego
- jeśli zwróci `false`, to przeszukuje dwa przypisane rejestry RMW w poszukiwaniu wartości różnej od `-1` (naszej wartości startowej). Skoro każdy wątek próbuje zapisać do obydwu rejestrów, to pozostałe wątki będą mogły zobaczyć czy coś zostało zapisane. Następnie funkcja bierze wartość z rejestru atomowego przypisanego do wątku, który został wskazany w znalezionym rejestrze RMW

Implementacja jest nieczekająca:
Funkcja `decide()` w żadnym miejscu na nic nie oczekuje (oprócz operacji atomowych), nie ma żadnych pętli.

Metoda `decide()` zwraca tę samą wartość wszystkim wątkom:
Funkcja `decide()` zwraca albo wartość własną (jeżeli udało się zapisać do rejestrów RMW) albo wartość wątku, który zapisał do rejestrów RMW. To oznacza, że dla każdego wątku wartość zwracana będzie taka sama.

Wartość zwracana przez metodę `decide()` jest jedną z wartości zaproponowanych przez wątki:
Zwracana wartość jest zawsze z rejestrów atomowych przypisanych do wątków, które zostają wypełnione przed uruchomieniem funkcji `decide()` i pozostają niezmienne.

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

We need to prove two statements:

1. There exists a consensus protocol for n threads using (arbitrarily many objects of) n-bounded CAS and (arbitrarily many) registers.

Proof: use the same protocol as on slides (PRW-5.pdf, slide 178)
We know that the standard compareAndSet() has an infinite consensus value. This modified conmpareAndSet() behaves exactly the same way for n threads, this means at least it has n level of consensus.

2. There exists no consensus protocol for n+1 thread with the same assumptions.

Using protocol trees, critical states etc. we need to prove that there is no protocol for n+1 threads.
Let’s consider that n-bounded compareAndSet() has a consensus level of n+1 for n threads and that we have a protocol that uses this function in a critical state. Using protocol tree, when thread n+1 runs solo in the end it will return either 1 or 0 making said critical state bi-valent.
Calls from 0 to n will return true or false depending on their proposed and change this proposed value or not accordingly with compareAndSet, however call n+1 will return a faulty state always, regardless of the order of the previous calls. This is a contradiction, as it shows the critical state wasn't bivalent.

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


### Kod

class Assign23{
    AtomicInt [] arr = new AtomicInt[3];
    public void assign ( int idx1, int val1, int idx2, int val2 ) {
        int temp1 = arr[ idx1 ].get();
        int temp2 = arr[ idx2 ].get();
        
        arr[ idx1 ].compareAndSet( temp1, val1 );
        arr[ idx2 ].compareAndSet( temp2, val2 );
    }
    public int get ( int idx ) {
        return arr[ idx ].get();
    }
}

### Dowód działania

Aby pokazać poprawność powyższej implementacji rozważmy trzy przypadki - kombinacje operacji jakie mogą zajść.

#### Żadna operacja się nie wykonała
#### Jakaś operacja się wykonała
#### Obie operacje zostały wykonane

## Zadanie 5
:::success
Autor: Konrad Kowalczyk
:::


Rozwiązanie ma zadanie 2.

Załóżmy nie wprost, że istnieje protokół konsensusu używający obiektu `QuasiConsensus` dla 2 wątków. Wiemy, że taki protokół musi mieć stan krytyczny oraz, że każdy wątek musi się po nim wykonać chociaż raz. Załóżmy bez straty ogólności, że jeśli wątek A wykona się jako pierwszy, to przejdziemy do stanu 0-walentnego, a jeśli jako pierwszy wykona się wątek B, to przejdziemy do stanu 1-walentnego.
Rozważmy przypadki:
- A i B proponują tę samą wartość (sytuacje są analogiczne) - funkcja `decide()` zwróci wtedy wartość zaproponowaną przez A i B. Jednakże w takiej sytuacji nie ma znaczenia, który wątek wykonał się jako pierwszy. Wartość zwracana przez funkcję `decide()` będzie taka sama niezależnie od tego czy pierwszy wykonał się wątek A czy wątek B. Otrzymujemy więc różne stany, a taką samą sytuację końcową - sprzeczność.
- A i B proponują różne wartości - funkcja `decide()` albo uzgodni wartość (wtedy przechodzimy do sytuacji z pierwszego przypadku) albo zwróci 1 dla A oraz 0 dla B. Zauważmy, że również nie ma znaczenia, który wątek wykonał się jako pierwszy, ponieważ zawsze funkcja zwróci 1 dla A oraz 0 dla B lub uzgodni wartość. Otrzymujemy więc różne stany, a taką samą sytuację końcową - sprzeczność.

W takim razie obiekt `QuasiConsensus` nie spełnia warunków koniecznych do posiadania poziomu konsensusu równego lub wyższego od 2, a zatem ma poziom konsensusu równy 1.

## Zadanie 6
:::success
Autor: Jakub Krzyżowski
:::

Z własności nieczekania algorytmu korzystamy jedynie, aby zapewnić, że dojdziemy do stanu krytycznego. Własność niewstrzymywania również nam to zapewnia.
Załóżmy, że nie dotarliśmy do stanu krytycznego. Oznacza to, że utknęliśmy w jakimś wcześniejszym stanie. A z definicji algorytmu niewstrzymującego jeśli znajdujemy się w jakimś stanie dostatecznie długo, to któryś z wątków wykona swoją akcję, więc doszlibyśmy do stanu krytycznego.
Reszta dowodu niemożliwości skonstruowania obiektu dwuwątkowego konsensusu przy pomocy atomowych rejestrów jest taka sama jak używając algorytmu nieczekającego.

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


### Obserwacja

Zauważmy, że spotkaliśmy się już z taką metodą. [Lista 7 zadanie 6](https://hackmd.io/2HJ2Kb27TYaS5-jSG-lB3g?view#Zadanie-6)


### Dowód
Aby pokazać niehamowalność powyższego algorytmu chcemy pokazać, że oba wątki muszą skończyć wykonanie.

Załóżmy bez straty ogólności, że mając dwa wątki (**x**, **y**), wątek **x** zakończy wykonanie jako pierwszy. Wiemy, że wątek **y** będzie wówczas wykonywał się w izolacji

Zostaje nam zatem pokazanie, że wątek **y** zakończy swoje wykonanie.

Przeanalizujmy działanie metody `decide`, a dokładniej **porównianie z warunku if**.

#### `position[ x ]` $\lt$ `position[ y ]`

Wykonuje się pierwszy if, zwracamy `proposed[ x ]`

#### `position[ x ]` $\geq$ `position[ y ]`

Wiemy, że wątek **x** zakończył wykonanie, zatem jego wartość **nie zmieni się**.
Możemy zatem zignorować równość, bo sprowadza się ona do nierówności $\geq$ w kolejnej iteracji.

Wykonuje się drugi if, zwracamy `proposed[ y ]`