# Ćwiczenia 8, grupa śr. 16-18, 14 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 |
| ----------------------:| --- | --- | --- | --- | --- | --- | --- |
Daniel Boguszewski | X | | | | | | |
Marcin Dąbrowski | | | | | | | |
Jakub Gałecki | | | | | | | |
Kamila Goszcz | | X | | | | | |
Wiktor Hamberger | | | | | | | |
Jan Jankowicz | | X | | | | | |
Mikołaj Jaszcza | | | | | | | |
Zuzanna Kania | X | X | | | | X | |
Wiktoria Kuna | | | | | | | |
Patryk Mazur | X | X | X | | X | X | |
Hubert Obrzut | | | | | | | |
Magdalena Rzepka | X |==X==| | | | X | |
Joanna Stachowicz |==X==| X | X | | X | X | |
Rafał Starypan | X | X | | | | | |
Maria Szlasa | X | X | | | X | X | X |
Daniel Wiczołek | X | X | X | | | | X |
Adam Jarząbek | X | X | | | | | |
:::

**Poniżej można dodeklarować zad. 7 z listy 7:**
-
-
-

**Poniżej można dodeklarować zad. 9 z listy 7:**
- Daniel Wiczołek
-
-

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

## Zadanie 1
:::success
Autor: Joanna Stachowicz
:::

## Zadanie 2
:::success
Autor: Magdalena Rzepka
:::

Wątki **A,B,C** mają odpowiednio id **0,1,2**.
**R = {-1, -1, -1} // RAC RAB RBC**
Każdy wątek wykonuje:
**MRSW[ID] = x** // wartość do konsensusu wątku ID
**double_cAS(R[ID], R[(ID+1)%3],-1,ID)** //tylko pierwszy wątek zapisze swoje ID na 2 pozycjach
**if(R[ID].get() != -1) -> return MRSW[R[ID].get()]
else -> return MRSW[R[(ID+1)%3].get()]**

Tylko pierwszemu wątkowi uda się zapisać swoje ID w 2 miejscach.
Jeżeli na R[ID] nic nie zostało zapisane to wystarczy znaleźć rejestr, który na pewno będzie zawierał dane.


## Zadanie 3
:::success
Autor: Patryk Mazur
:::

Załóżmy nie wprost, ze n-ograniczona funkcja **compareAndSet()** ma poziom konsensusu $n+1$ dla $n$ wątków ($n>=2$)


Każdy wątek wykonuje jeden raz instrukcję **compareAndSet()**

Wątek $n+1$-szy przy wywołaniu **compareAndSet()** zwróci pinezkę. Zatem nie będzie mógł rozróżnić stanu (odtworzyć kolejności poprzednich instrukcji). Jeżeli teraz w obu przypadkach wątek $n+1$-szy pójdzie solo, to dostaniemy sprzeczność, ponieważ po wykonaniu tych samych instrukcji z identycznego stanu możemy dostać dwie wartości konsensusu (Lewa strona 0-walentna, prawa 1-walentna).

## Zadanie 4
:::danger
Autor: dodeklarować
:::

## Zadanie 5
:::success
Autor: Maria Szlasa
:::
:::info
Rozważmy następujący dwuwątkowy obiekt QuasiConsensus z metodą decide(v), gdzie v jest wartością binarną. Jeśli obydwa wątki, A i B, wywołały decide() z tą samą wartością v, to wspólnie uzgodnioną wartością jest v — decide() zwraca v. Jeśli wątki wywołały decide() z różnymi argumentami to albo muszą uzgodnić jedną z nich, albo B otrzyma wartość 0 i A otrzyma wartość 1 (ale nie na odwrót). Dokładnie jedno z poniższych zadań ma rozwiązanie. Wybierz odpowiednie i rozwiąż je.
1. Pokaż, że poziom konsensusu dla obiektów QuasiConsensus jest ≥ 2. Tzn. zaimplementuj dwuwątkowy protokół konsensusu używając obiektów QuasiConsensus i rejestrów atomowych.
2. Pokaż, że poziom konsensusu dla obiektów QuasiConsensus wynosi 1.
:::

Wybieram: 2. Pokaż, że poziom konsensusu dla obiektów QuasiConsensus wynosi 1.

Pokażę, że poziom konsensusu QuasiConsensus nie wynosi 2.

Załóżmy, że jesteśmy w stanie krytycznym. Rozważmy przypadki:

**A decide(0), B decide(0)**
Stan ten jest równoważny z wykonaniem operacji B decide(0) -> A decide(0). Ale te dwa wywołania są w innych poddrzewach. (jedno jest 1-walentne, a drugie jest 0-walentne).

**A decide(1), B decide(1)**
Analogicznie do poprzedniego.

**A decide(1), B decide(0)**
W tym przypadku wątki uzgadniają wartość albo zwracają A=1, B=0. Niezależnie od kolejności wykonania wątków możemy otrzymać te wartości. Zatem są to stany nierozróżnialne. Ale te dwa wywołania są w innych poddrzewach. (jedno jest 1-walentne, a drugie jest 0-walentne).

**A decide(0), B decide(1)**
Analogicznie do poprzedniego.

> Komentarz:
> istnieje jeszcze jeden przypadek, ale podobno nieciekawy: wywołują decide na różnych obiektach QuasiConsensus
> alternatywne rozwiązanie: można było podać implementację QuasiConsensus jako dowód
> ale przedstawione rozwiązanie jest ok

## Zadanie 6
:::success
Autor: Zuzanna Kania
:::



Konstrukcja drzewa decyzyjnego protokołu bazowała po pierwsze na tym, któremu z wątków uda się wykonać akcję na zadanym stanie jako pierwszemu. W przypadku warunku nieczekania wiedzieliśmy, że zarówno A i B będą postępować (bo muszą się zakończyć w skończonej liczbie kroków), więc któryś z nich wykona akcję jako pierwszy. Można jednak zauważyć, że według podanej definicji niewstrzymywanie działa praktycznie tak samo - dla pewnego stanu w końcu któryś z wątków wykona akcję (jako pierwszy), nawet jeśli pozostałe śpią.

Po drugie korzystaliśmy z faktu, że każdy protokół nieczekający ma stan krytyczny. Jest tak również w przypadku protokołu niewstrzymywanego, ponieważ zawsze znajdziemy przynajmniej jeden wątek, który zakończy swoje działanie w skończonej liczbie kroków. Skoro tak, to wątek ten działając solo trafi w końcu na jakiś stan krytyczny - w przeciwnym razie nie miałby skończonej liczby kroków.


Całość dowodu przebiega zatem analogicznie poza faktem, że wcześniej mogliśmy wybrać dowolny wątek działający solo, a teraz musimy go wybrać spośród tych, o których wiemy, że zakończą się w skończonej liczbie kroków (a jak zauważyliśmy powyżej, przynajmniej jeden taki wątek zawsze istnieje).

## Zadanie 7
:::success
Autor: Daniel Wiczołek
:::


Z zadania 5 listy 7:

W zad5 lista7 pokazalismy, że jest to impl. bin konsensusu.
Pokażemy, że jest obstruction free.
Załóżmy, że wątek B od pewnego momentu wykonuje ją w iolacji.
Musi więc powtarzać wykonywanie pętli while.

Zauważmy, że
- position[j] oraz speed[j] się nie zmieniają.
- speed[i] >= 1

Niech $position_n[i]$ będzie wartością position[i] po n-tej iteracji.
Dla dowolnego $n \in N$ zachodzi: $position_n[i] < position_{n+1}[i]$,
podstawa:
$position_1[i] >= 0+1 > 0 == position_0[i]$
krok:
position_{n+1}[i] >= position_n[i] + 1 > position_n[i]

Więc ciąg pozycji jest rozbieżny, czyli istnieje iteracja, w której
pozycja jest większa niż stała: $position[j] + speed[j]$.