# PW - Lista 8

# Zadanie 1

Załóżmy, że mamy nieczekającą implementację protokołu binarnego konsensusu dla trzech wątków, używająca wyłącznie wymienionych wyżej zasobów. Rozważmy punkt krytyczny. Bez utraty ogólności załóżmy, że następna wykonana przez A instrukcja wprowadza nas w stan 0-walentny, a następna wykonana przez B wprowadza nas w stan 1-walentny. Punktem krytycznym może być jedynie sytuacja w której dwa wątki wykonują operację na tym samym obiekcie.

1. 2x read() na obiekcie rejestru MRSW. Nie może być stanem krytycznym.

2. write() i read() na obiekcie rejestru MRSW. Nie może być stanem krytycznym.


3. compareAndSet() na obiekcie rejestru RMW.

Rozpatrzmy następujący stan krytyczny. Weźmy wątki A i B, oraz rejestr RAB. A i B wykonują operację cAS. Nie może być stanem krytycznym.


:::success
# Zadanie 2
:::

/*W tym kodzie wątek A ma numer 0, B ma 1, C ma 2. Indeksujemy tablice MRSW i r numerami wątków*/
public class Consensus{
    boolean proposed[] = new boolean[3];
    double[] r = new double[3]{-1,-1,-1} /*RAC RAB RBC*/
    public boolean decide(boolean x){
        proposed[ID] = x; /* tablica wartości zaproponowanych 
                       * przez wątki (wartości na wejściu wątków)*/
        double_cAS(r[ID],r[(ID+1)%3],-1,ID) /*tu próbujemy ustawić wartości obydwu rejestów RMW przypisanych do wątku (np RAB i RAC dla wątku A)*/
        if(r[ID].get() != -1) /* (*) */
            return proposed[r[ID].get()];
        else 
            return proposed[r[(ID+1)%3]].get()];
    }
}

:::success
# Zadanie 3
:::

public class CASConsensus extends ConsensusProtocol {
   private AtomicInteger r = new AtomicInteger(-1);
       
   public T decide(T value) {
       propose(value);
       r.compareAndSet(-1, threadId);
       return proposed[r.get()];
   }
}

Zauważmy, że n wątków może użyć funkcji compareAndSet, dla nich nie ma żadnego ograniczenia, więc konsensus będzie działać prawidłowo. N+1szy wątek nie może jej już wykorzystać ten funkcji. Trzebaby zatem dla niego oraz reszty wątków stworzyć konsensus za pomocą tylko rejestrów atomowych.

Możemy teraz zauważyć, że mamy n wątków, które wykonały compare_and_set i jeden, który nie może tego wykonać. Ta sytuacja jest analogiczna, do próby wykonania konsensusu dla 2 wątków jedynie za pomocą rejestrów atomowych. A jak wiadomo, nie da się tego zrobić.

Z perspektywy wątku n+1 stan jest w obu gałęziach taki sam, więc wątek ten zwróci tę samą wartość. Sprzeczność.