# Ćwiczenia 7, grupa cz. 10-12, 2. grudnia 2021

###### tags: `PRW21` `ćwiczenia` `pwit`

## Zadanie 1

:::success
Autor: Mateusz Sidło
:::

:::info
Pokaż, że nie istnieje nieczekająca (ang. wait-free) implementacja protokołu binarnego$^1$ konsensusu dla $n$ wątków $(𝑛 > 2)$, używająca jedynie rejestrów atomowych. Skorzystaj z faktu, że taka implementacja nie istnieje dla dwóch wątków oraz z tego, że rozważane implementacje muszą być nieczekające.
:::

Weźmy dowolne $n > 2$ i załóżmy, że istnieje taka nieczekająca implementacja protokołu binarnego konsensusu dla tego $n$. Rozważmy następujące wykonanie.

Wątki $1$ i $2$ rozpoczynają i kończą wykonanie protokołu przed rozpoczęciem jego wykonania przez pozostałe wątki. Jest to możliwe ze względu na to, że implementacja jest nieczekająca. Wątek $1$ zaczyna z wartością $a$, a wątek $2$ z wartością $b$, gdzie $a,b\in\{0,1\}$. Wartością konsensusu jest $a$ lub $b$.

Powyższe wykonanie jest równoważne z rozwązaniem problemu konsensusu binarnego dla dwóch wątków, przy użyciu nieblokującego protokołu używającego jedynie rejestrów atomowych. Ale taka implementacja nie istnieje.

A zatem sprzeczność.
## Zadanie 2

:::success
Autor: Przemysław Hoszowski
:::

class Cons{
    T values[];
    BinaryConsensus[] binaryConsensus;
    
    Cons(int n){
        // tworzmy po n obiektów odpowiedniego typu
        this.values = new T[n]();
        this.binaryConsensus = new BinaryConsensus[n]();
    }
    // id wątków są od 0 do n-1
    T decide(T value){
        values[thread.id] = value
        binaryConsensus[thread.id].decide(true);
        for (int i=0; i<n; i++){
            if(binaryConsensus[i].decide(false))
                return values[i]
        }
    }
}

#### Zauważmy, że istnieje wątek który wygrał swój konsensus:
Załóżmy, że każdy konsensus jest albo nie rozstrzygnięty albo ma wartość false oraz że istnieje jakiś konsensus z wartością false.
Wtedy konsensus z wartością false musiał zostać wygrany przez inny wątek i przegrany nie mógł uniemożliwić mu zdobycia wygranemu konsensusu wygranego. Z racji ograniczonej ilości wątków jakiś wątek musiał nie mieć konkurencji, więc musi mieć wartość true.

#### Jeśli jakaś wartość została zwrócona to żadna inna nie została zwrócona
Oznaczałoby to, że dowolne 2 wątki otrzymałyby 2 różne wartości konsensusu odpowiadającego wcześniejszej wartości co jest sprzeczne z ich działaniem.

#### Zostanie tylko zwrócona wartość, która została wprowadzona przez jeden z wątków
Ustawienie konsensusu na true poprzedza ustawienie wartości, więc niemożliwe jest zwrócenie niepoprawnej wartości.

## Zadanie 3

:::success
Autor: Dominik Komła
:::


Lemat: "jeśli A wykonało enq to A musi wykonać deq."

> [name=Piotr Witkowski] Musimy udowodnić ten lemat.

## Zadanie 4

:::success
Autor: Antoni Pokusiński
:::
:::info
Pokaż, że poniższy obiekt implementuje protokół binarnego konsensusu dla dwóch wątków (wartość zwracana przez ```decide()``` jest jedną z wartości zaproponowanych przez wątki oraz metoda ta zwraca tę samą wartość obydwu wątkom). Załóż, że wszystkie komórki pamięci są atomowymi rejestrami. Dlaczego ten wynik nie jest sprzeczny z faktem, że poziom konsensusu dla rejestrów atomowych wynosi 1?
:::

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];
        }
    }
}

1. "wartość zwracana przez ```decide()``` jest jedną z wartości zaproponowanych przez wątki" - oczywiste, bo zawsze zwracamy wartość z tablicy ```proposed```
2. "metoda ta zwraca tę samą wartość obydwu wątkom", czyli innymi słowy jeden wątek zwrócił z ```if```, a drugi z ```else if```. Rozważmy sytuację, w której oba wątki zwróciły swoją wartość z ```if```, załóżmy bez straty ogólności że to B skończył wykonywać funkcję jako pierwszy:

A: -------------------------------------<ret pro[i]==A>---
B: <p[i]>p[j]+s[j]>-<ret pro[i]==B>-----------------------

Pomiędzy dwiema operacjami ```return``` mamy maksymalnie jedno zwiększenie ```position[i]``` przez wątek A, co nie wystarcza, żeby spełnić warunek z ```if``` - sprzeczność.

Może się jednak zdarzyć sytuacja, że będziemy czekać nieskończoność. Jeśli wystartuje wątek B i 3 razy zwiększy swoje *position* o 1, potem 1 raz się wykona A i zwiększy swoje *position* o 3 itd., to zawsze żaden z warunków nie będzie spełniony
## Zadanie 5

:::success
Autor: Mateusz Opala
:::
1. Algorytm decide, który dla każdego wątku najpierw robi write(value) do StickyBit, a później czyta z tego bitu i zwracana przeczytaną wartość, w oczywisty sposób rozwiązuje problem konsensusu.
2. Dla każdego bitu weźmy sobie obiekt klasy StickyBit. Oprócz tego weźmy tablicę T atomowych komórek MRSW, po jednej dla każdego wątku. Na początku każdy wątek wpisze, do swojej komórki własną wartość. Następnie dla każdego wątku będziemy się iterować po kolejnych jego bitach. Dla bitu b_i robimy write(b_i) do i-tego StickyBitu, a następnie zczytujemy wartość z tego bitu, jeśli jest ona taka sama jak b_i to kontynuujemy. Jesli jest różna to iterujemy się po T i znajdujemy wartość v, którą prefiksem jest aktualnie przeczytany stan ze StickyBitów. Następnie kontynuujemy algorytm dla wartości v. Po przeiterowanie się po wszystkich bitach zwracamy aktualną liczbę. W ten sposób każdy wątek zwróci tą samą wartość czyli podany algorytm rozwiązuje problem konsensusu dla M wartości i n wątków.

## Zadanie 6

:::success
Autor: Jan Wańkowicz
:::

Spróbujmy zbudować algorytm przy pomocy obiektów przybliżonej zgody dla konsensusu dla dwóch wątków. Zauważmy jednak, że tak naprawdę dwuwątkowy protokół przybliżonej zgody nic nam nie daje - może on zwrócić nam każdą liczbę z przedziału $[min(x_a,x_b) , max(x_a,x_b)]$, o ile druga liczba będzie poprawna. W szczególności dalej możliwe by to było, żeby $decide(x_a)$ zwróciło $y_b$ i odwrotnie. Z tego powodu niemożliwe jest rozbicie symetryczności przy pomocy tego obiektu. Stąd poziom jego konsensusu jest równy $1$.

## Zadanie 7

:::success
Autor: Łukasz Pluta
:::

Możemy najpierw połączyć wartość 2 pierwszych wątków, używając danego obiektu, potem dołączyć do nich 3-ci i tak dalej. Przy każdym "łączeniu" zbiór wartości argumentów wątków jest co najwyżej dwuelementowy, więc wszystko działa.

## Zadanie 8

:::success
Autor: Michał Zieliński
:::

### Treść
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 $\infty$ .

### Rozwiązanie
#### Protokół konsensusu

class FIFOConsensus<T>
{
    FIFO f;
    T[] props;
    T decide(T val)
    {
        props[thr_id] = val;
        f.enq(thr_id);
        return props[f.peek()];
    }
}

#### Uzasadnienie
##### Nieczekający
Nasz konsensus korzysta z nieczekającej kolejki FIFO i "skończonych" odczytów i zapisów, nie występuje natomiast żadna pętla. Konsensus jest zatem nieczekający.
##### Spójny
Nie wprost. Jeżeli dwa wątki wskazały rózne wartości to f.peek() musiało zwrócić różne wartości. Jest to jednak niemożliwe, ponieważ metoda ta zwraca pierwszy element kolejki, który był w obu momentach ten sam, bo nigdy nie został usunięty, ani "zepchnięty" przez innego (ze względu na działanie enq w FIFO). Sprzeczność, wszystkie wątki wskażą tą samą wartość.
##### Poprawny
W linii 9 wskazywana jest wartość z tablicy props o indeksie odpowiadającym pewnemu wątkowi. W tej samej tablicy wątek ten zapisał w tym indeksie wartość, którą proponował. Ustalona zatem będzie wartość zaproponowana przez któryś z wątków.
##### Dla $\infty$ wątków
Wszystkie powyższe obserwacje zostały dokonane bez założeń co do liczby wątków, są słuszne dla $1,2,...$ wątków. Poziom konsensusu wynosi zatem $\infty$.