## Z1

Załóżmy, że funkcja scan() SimpleSnapshot zwróciła nam pewien stan pośredni pomiędzy spowodowany wywoływaniem współbieżnym update(). Zatem w pewnym momencie musiało zajść ```Array.equals(oldCopy, newCopy) == true```
Mogło to nastąpić tylko jeżeli nie zmienił się żaden timestamp, a skoro się nie zmienił to znaczy, że nie nastąpił update(). Zatem druga kopia tablicy jest prawidłowym snapshotem. A skoro pierwsza kopia jest równa drugiej to także jest prawidłowym snapshotem. Sprzeczność.

**Scan**
Gdy jest dużo updatów będziemy ponawiać scan w nieskończoność, jeżeli jednak zatrzymamy drugi wątek i pozwolimy pracować scan w odizolowaniu to nie zmienią się wartości w tablicy, zatem zajdzie ```Array.equals(oldCopy, newCopy) == true```

**Update**
Jest lock-free. Nie ma możliwości, żeby się zapętlił. Jeśli dostanie czas procesora to dokona postępu.

## Z2

Dlaczego A nie może wziąć snapshota B jako swój? (Dlaczego wątek musi 2 razy ruszyć, żeby wziąć jego snapshot)

**Lemat 1**
Jeśli wątek skanujący wykonał czyste podwójne zbieranie, to wartości które zwrócił były prawdziwymi wartościami rejestrów.

Rozważmy przerwę międze ostatnim odczytem 1 zbierania, a pierwszy odczytem 2 zbierania. Jeśli jakiś rejestr został zaaktualizowany podczas tej przerwy to timestamp nie będą równe, zatem nie będzie to czyste podwójne zbieranie.

**Lemat 2**
Jeśli wątek skanujący A zaobserwuje zmiany w znaczniku czasu innego wątku B podczas dwóch różnych podwójnych zbierań, wówczas wartość rejestru B odczytana podczas ostatniego zbierania została zapisana przez wywołanie update(), które rozpoczęło się po rozpoczęciu pierwszego zbierania.

Jeśli podczas skanowania() dwa kolejne odczyty rejestru B przez A zwrócą różne znaczniki czasu, wówczas pomiędzy tą parą odczytów nastąpi co najmniej jeden zapis przez B. Wątek B zapisuje do swojego rejestru w ostatnim kroku wywołania update(), zatem niektóre wywołania update() wykonywane przez B zakończyły się jakiś czas po pierwszym czytaniu przez A, a etap zapisu innego wywołania update() następuje pomiędzy ostatnią parą czyta A. Twierdzenie wynika z tego, że tylko B zapisuje do swojego rejestru.

**Lemat 3**
Wartości zwrócone przez scan() były wartościami rejestrów pomiędzy wywołaniem metody, a zwróceniem wyniku.

Jeśli miało miejsce czyste podwójne zbieranie, to twierdzenie wynika z Lematu 1. Jeśli scan() zwrócił wartości rejestrów z rejestru jakiegoś wątku B, to z Lematu 2 wynika, że wartości te były uzyskane podczas wywołania scan(). Indukcyjnie wątek B wywołujący scan() w metodzie update() uzyskał rzeczywiste wartości rejestrów. Indukcje możemy zastosować maksymalnie n-1 razu, gdzie n to liczba wątków. Ostatecznie jakiś zagnieżdżony scan() wykona podwójne czyste zbieranie.

**Lemat 4**
Każde wywołanie scan() oraz update() wykona się po conajwyżej $(n^2)$

Rozważ konkretny scan(). Jest tylko n - 1 innych wątków, więc po n podwójnych zebraniach albo jedno podwójne zebranie jest czyste, albo obserwuje się, że jakiś wątek porusza się dwukrotnie. Twierdzenie wynika z tego, że każde podwójne zbieranie powoduje O(n) odczytów.


## Z3

Załóżmy, że istnieje nieczekająca implementacja protokołu binarnego konsensusu dla n wątków, używająca jedynie rejestrów atomowych.

Skoro implementacja jest nie czekająca to oznacza, że każdy z jej n wątków dokonuje progresu zatem w skonczonej liczbie kroków zakończy swoje działanie. W skończonym czasie dojdziemy do sytuacji w której rozstaną nam 2 wątki (n - 2 wątki skończą swoje działanie). Z wykładu wiemy, że nie istnieje implementacja działają na 2 wątkach. Zatem mamy sprzeczność.

## 4

class MValuedConsensus<T> {
  private BinaryConsensus cons[];
  private AtomicRegister<T> propose[];
  
  public MValuedConsensus() {
    propose = new AtomicRegister<T>[N];
    cons = new BinaryConsensus[N];
  }
  
  public T decide(T value) {
    int self = ThreadID.get();
    propose[self] = value;
    cons[self].decide(true);
      
    for(int i = 0; i < N; i++)
        if(cons[i].decide(false))
            return propose[i];
  }
}

**Wartość zwracana przez decide() jest jedną z wartości zaproponowanych przez wątki**

Załóżmy, że żadnemu wątkowi nie udało się ustawić konsensusu na true, zatem każdy wątek musiał być poprzedzony przez inny wątek, ale żeby to zrobić musi najpierw zakończyć ustawienie swojego konsensusu na true. Sprzeczność

**Metoda ta zwraca tę samą wartość każdemu wątkowi**

Weźmy dowolne 2 wątki (A, B) i załóżmy, że zwróciły różne wartości oraz BSO A < B

Żeby wątki zwróciły różne wartości dla wątku A musi zajść ```cons[A].decide(false) == true```, a dla wątku B ```cons[A].decide(false) == false``` oraz ```cons[A].decide(true) == true```. Sprzeczność.

## 6

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

**Wartość zwracana przez decide() jest jedną z wartości zaproponowanych przez wątki**

Wątki zawsze zwracają propose po przypisaniu wartości. Zatem jeśli działają 2 wątki to zwrócą one zaproponowaną wartość.

Zauważmy też, że nie zwrócimy nigdy nie zainicjowanej wartości:

1. Działa tylko wątek 0

i = 0
j = 1
    
//W 1 wykonaniu while
position[i] = 3
    
if (position[i] > position[j] + speed[j]) // I am far ahead of you
    return proposed[i];

2. Działa tylko wątek 1

i = 1
j = 0
    
//W 4 wykonaniu while
position[i] = 4
    
if (position[i] > position[j] + speed[j]) // I am far ahead of you
    return proposed[i];

**Metoda ta zwraca tę samą wartość obydwu wątkom**

Załóżmy nie wprost, że dwa wątki zwróciły różne wartości

if (position[i] < position[j]) // I am behind you
return proposed[j];

Jeden z wątków musiał wykonać tego ifa jako pierwszy, wartości $position[]$ mogą się tylko zwiększać, zatem niemożliwe jest, że drugi wątek następnie odczytał swoje position jako mniejsze

if (position[i] > position[j] + speed[j]) // I am far ahead of you
return proposed[i];

Jeden z wątków musiał wykonać tego ifa jako pierwszy, drugi z wątków na pewno wykona drugiego ifa zwracającego $proposed[j]$

**Dlaczego ten wynik nie jest sprzeczny z faktem, że poziom konsensusu
dla rejestrów atomowych wynosi 1?**

To rozwiązanie nie jest $wait-free$, jeśli wartości $position[]$ są takie same, to wolniejszy wątek może wykonać trzy razy pętlę $while$, następnie szybszy wątek wykona raz pętle i wracamy so sytuacji z równymi $position[]$

## Z9

public class QueueConsensus<T> extends ConsensusProtocol<T> {
    Queue queue;

    public QueueConsensus() {
        queue = new Queue();
    }

    public T decide(T Value) {
        int i = ThreadID.get();
        propose(value);
        queue.enq(i);
        return proposed[queue.peek()];
    }
}

* Jest wait-free
* wartość zwracana przez decide() jest jedną z wartości zaproponowanych przez wątki

* metoda ta zwraca tę samą wartość wszystkim wątkom
Metoda zawsze zwraca propozycje pierwszego wątku i jej nie ściąga, zatem każdy wątek dostanie to samo