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

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

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

## Zadanie 1
:::success
Autor: Kamila Goszcz
:::



### Dowód nie wprost
Załóżmy, że funkcja scan() SimpleSnapshot zwróciła nam pewien stan pośredni pomiędzy spowodowany wywoływaniem współbieżnym update(). Skoro tak to musieliśy ominąć if-a, a zatem zaszło `Array.equals(oldCopy, newCopy) == true`. Jako, że w funkcji scan() porównujemy timestampy, oznacza to, że pomiędzy punktai linearyzacji (ktore wypadają na koniec tych funkcji) `oldCopy.collect()` a `newCopy.collect()` nie nastąpił żaden update. Porównywanie timestampów zamiast wartości gwarantuje nam, że nie nastąpiły dwa update(), które mogłyby wrzucić tą samą wartość w trakcie wywoływania obu collectów. Skoro tak to nie nastąpił żaden zapis w trakcie `newCopy.collect()`. Wynika z tego, że `newCopy` jest poprawnym snapshotem. A więc doszliśmy do sprzeczności

[c;c;c;c;c] -> oldCopy: [c;c;]
[a;c;c;c;c]
[a;c;c;c;a] -> oldCopy: [c;c;c;c;a]
[a;c;c;c;c]
[c;c;c;c;c] -> newCopy: [c;c;]
[a;c;c;c;c]
[a;c;c;c;a] -> newCopy: [c;c;c;c;a]

### Scan
Może się zdarzyć tak, że wielokrotnie`Array.equals(oldCopy, newCopy) == false`. Będzie tak, gdy update() będziemy wykonywać na tyle często, że scan nie będzie w stanie wykonać 2 collectów między nimi. Zauważmy jednak, że gdy odizolujemy wątek scan(), to nie zmienią się wartości w tablicy, zatem zajdzie `Array.equals(oldCopy, newCopy) == true`. Scan będzie miał własność obstruction-free.

### Update
Update jest lock-free. Nie ma możliwości, żeby się zapętliła, jeżeli tylko dostanie czas procesora to zrbi pewien postęp a co za tym idzie cały system jest lock-free

## Zadanie 2
:::success
Autor: Adam Jarząbek
:::

Aby pokazać, że nie istnieje implementacja protokołu binarnego konsensusu dla $n$ wątków używająca jedynie rejestrów atomowych załóżmy nie wprost, że istnieje.

Mamy skorzystać z tego, że dla dwóch wątków taka implementacja nie istnieje. Wiemy również, że ta implementacja jest nieczekająca. Skoro jest nieczekająca to znaczy, że każdy z jej $n$ wątków dokonuje postępu i kończy swoje działanie w skończonej liczbie kroków. W skończonym czasie dojdziemy więc do momentu, kiedy zostaną tylko dwa pracujące wątki.

Ale wiemy, że implementacja działająca na dwóch wątkach nie istnieje, więc mamy sprzeczność.

Nie wprost dowiedliśmy, że nie istnieje implementacja protokołu binarnego konsensusu dla $n$ wątków używająca jedynie rejestrów atomowych.

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

- idea: niech dogadają się bit po bicie
- mozemy zalozyc ze kazda ma tyle samo bitow, poprostu padding zerami
- problem: co jesli jakis dostał wartosc 2 inny wartosc 1, a wartosci 3 nie ma w zbiorze ale jest mozliwym wynikiem
- wniosek: musimy updetowac obecna wartosc - ta z ktorej bierzemy bity
- wez dowolna wartosc która ma bity zgodne już z tymi ustalonymi, wtedy nie moze być tak, że ustalimy inny bit niż dozwolony, bo binarny konsensus działa, a zawsze na wejsciu wrzucasz jedna z mozliwych wartosci do bin_decide(bit) Potrzbujemy decide obiektu dla każdego bitu.
- problem: powinnismy zwracac tylko wartosc ktora byla inputem a nie z calego zbioru
- więc dodajmy te wartosci na poczatku przed wykonaniem pętli i sprawdzajmy czy jest valid, czyli czy ta wartosc jest wartoscia wpisana przez jakis watek.

szkic:

// współdzielone zasoby:
BinConsensus[ILOSC_BITOW] // dla kazdego bitu osobny
(bool, T) candidates[n] // zb wartosci (tylko to co bylo inputem do jakiegos thread)
bit result[ILOSC_BITOW] // WYNIK KONSENSUSU ZAPISYWANY TUTAJ

decide(T val) 
    valid = true
    candidates[THREAD_id] = (valid, val); // zalozenie ze threads maja id po kolei...
    for (int i=0; i < ILOSC_BITOW; ++i) {
        bit = i_bit(val)
        // result moze byc wspolny bo wiemy ze decide zwraca zawsze to samo.
        result[i] = bin_consensus[i].decide(bit); 
        if(result[i] != bit) {
            val = get_random_valid_candidate_with_matching_bits(result[0 .. i])
        }
    }
    return result;

- consistent, bo result jest wypełniany wynikami funckcji decide, a skoro binary jest consistent, to zawsze będzie ta sama wartość. Więc każdy wątek zwraca tą samą wartość.
- valid, bo niezmiennikiem jest to, że każdy bit w input do bin_consensus, pochodzi z valid wartosci czyli wartosci ktora byla inputem jakiegos watku.
- wiat-free, skończona liczba instr - ograniczona max liczbą bitów potrzbną do reprezentacji wartości.

---

formalniej:
Lemat: Istnieje wątek, którego wartość wejściowa jest równa result (algorytm jest "valid").

Niezmiennik pętli:
- $i$ pierwszych bitów w $result$ oraz $val$ są równe.
- $val$ jest jedną z wartości wejściowych.

Przed pętlą:
$val$ jest wartością wejściową.
zero bitów jest zgodnych.

Załóżmy, że dla iteracji <= $i$-tej jest to prawda.
Pokażmy że po (i+1)-szej też jest.
1. jeśli wynik decide był taki sam jak ten zaproponowany, to:
- Funckja $bin\_consensus[i+1].decide$ dostaje jako wartość wejściowa (i+1)-szy bit z $val$ więc $result$ i $val$ się zgadzają w i+1 bitach.
- $val$ się nie zmienia więc z założenia jest jedną z wartości wejściowych.
2. wynik był inny niż zaproponowany
- Zgodnie z algorytmem do $val$ zapisujemy wartość, w której bity \[0; i+1\] są zgodne z tymi w $result$, więc się zgadzają.
- $val$: wybieramy jedną z wartości wejściowych (czyli takich, które mają ustawioną flagę valid).
- Pokażmy, że istnieje wartość, która jest jedną z wejściowych i ma zgodne bity \[0; i+1\]. Załóżmy niewprost, że nie istnieje taka, która ma do i+1-szego zgodne, wiemy z założenia, że decide dostało i+1-szy bit wartości zgodnej na [0; i] bitach z result. Ale skoro nie ma takiej, która ma i+1-szy zgodny to decide zwróciło wartość, która nie jest (i+1)-szym bitem żadnej wartości wejściowej, sprzeczność z tym, że $bin_consesus$ implementuje binarny konsensus (nie byłby valid).

Więc
- $i+1$-szy bit w $result$ oraz $val$ są równe.
- $val$ jest jedną z wartości wejściowych.

Wniosek: $result$ jest równy jednej z wartości wejściowych.

## Zadanie 4
:::success
Autor: Zuzanna Kania
:::


Chcemy udowodnić, że nie istnieje implementacja protokołu binarnego konsensusu dla trzech wątków korzystających tylko z kolejek FIFO i rejestrów atomowych.

Załóżmy więc niewprost, że taka implementacja istnieje. Wiemy, że w każdym protokole istnieje przynajmniej jeden stan krytyczny. Weźmy taki stan krytyczny $s$. Bez utraty ogólności załóżmy, że następny ruch wątku A prowadzi do stanu 0-walentnego, natomiast następny ruch wątku B prowadzi do stanu 1-walentnego.

Wiemy już, że A i B nie mogą czytać ani pisać jedynie do współdzielonych rejestrów (taki przypadek udowodniliśmy na wykładzie). Nie mogą także wykonywać operacji na różnych obiektach, ponieważ operacje te można w oczywisty sposób zamienić kolejnością i otrzymać nierozróżnialne stany. Będziemy zatem analizować jedynie operacje na jednej kolejce.

Rozważmy zatem następujące przypadki:
* oba wątki wykonują `deq()`
Niech $s'$ będzie stanem po wywołaniu `deq()` na stanie $s$ najpierw przez wątek A, a potem przez B, natomiast $s''$ będzie stanem po wywołaniu `deq()` na stanie $s$ najpierw przez wątek B, a potem przez A. Ponieważ $s'$ jest 0-walentny to wątek C działający na nim solo zwróci wartość 0. Z kolei działanie C solo na $s''$ zwróci 1. Jednak $s'$ i $s''$ są dla C nierozróżnialne (bo usunięto z kolejki te same elementy) i wątek ten powinien zwrócić taką samą wartość w obu przypadkach. Sprzeczność.

* wątek A wykonuje `enq(a)`, a wątek B `deq()`
Jeśli kolejka jest niepusta, to mamy sytuację analogiczną do poprzedniej - dostaniemy dwie różne wartości, mimo że wątek C nie widzi różnicy w kolejności wykonania tych operacji. Sprzeczność.
Z kolei jeśli kolejka jest pusta, to C nie jest w stanie rozróżnić $s'$ po wykonaniu tylko `enq(a)` przez A oraz $s''$ po wykonaniu najpierw `deq()` na pustej kolejce przez B, a następnie `enq(a)` przez A. Również mamy sprzeczność.
* wątek A wykonuje `enq(a)`, a wątek B `enq(b)`
Niech $s'$ będzie stanem po następującym wykonaniu:
1. A i B wkładają do kolejki kolejno elementy a i b
2. Wątek A działa nieprzerwanie dopóki nie wyjmie z kolejki a.
3. Wątek B działa nieprzerwanie dopóki nie wyjmie z kolejki b.

Niech $s''$ będzie stanem po następującym wykonaniu:
1. B i A wkładają do kolejki kolejno elementy b i a
2. Wątek A działa nieprzerwanie dopóki nie wyjmie z kolejki b.
3. Wątek B działa nieprzerwanie dopóki nie wyjmie z kolejki a.

$s'$ jest 0-walentny, a $s''$ 1-walentny, jednak są one nierozróżnialne dla C, ponieważ działanie A jest takie samo do momentu wyciągnięcia a lub b i tak samo dzieje się dla wątku B. Stąd mamy sprzeczność.

Zatem nie istnieje implementacja protokołu binarnego konsensusu dla trzech wątków korzystających tylko z kolejek FIFO i rejestrów atomowych.

## Zadanie 5
:::success
Autor: Mikołaj Jaszcza
:::


1) **"wartość zwracana przez decide() jest jedną z wartości zaproponowanych przez wątki"**
Ten warunek oczywiście jest spełniony, zauważmy że metoda decide zwraca wartość która została umieszczona w tablicy proposed. Jedyne miejsca w kodzie, które modyfikują wartości tej tablicy, to linijka "proposed[i] = value", czyli wartość propozycji od danego wątku.

Zauważmy też, że nigdy nie zwrócimy niezainicjalizowanej wartości, bo instrukcja "proposed[i] = value" w każdym przypadku poprzedza wykonanie "return proposed[...]". Tzn, oczywiście proposed[i] = ... poprzedza return proposed[i] w tym samym wątku. Natomiast gdy wykonujemy "return proposed[j]" musi zajść że position[i] < position[j]. To może zajść dopiero, gdy drugi wątek wykonałby position[i] = position[i] + speed[i] (na bazie warunków początkowych), a to następuje póżniej niż jego wykonanie proposed[i] = ... (jego i to nasze j, więc wszystko zostało spełnione).

2) **"metoda ta zwraca tę samą wartość obydwu wątkom"**
To stwierdzenie możemy sprowadzić do stwierdzenia, że jeden z wątków zwróci wartość będąc w przypadku "if" a drugi w przypadku "else if". Wtedy jeden z wątków zwraca "swoją" wartość a drugi wartość drugiego z wątków, tj. tą samą wartość.

Pokażę więc, że **2a) nie jest możliwe żeby oba wątki zwróciły wartość będąc w przypadku "else if"**
BSO wątek A zwrócił pierwszy. Jeżeli tak, to position[A] < position[B]. Zauważmy, że od tego momentu wartość position[A] pozostanie stała, a wartość position[B] może się jedynie zwiększać. Zatem nie może zajść odwrotne, tj position[B] < position[A], czyli wątek B na pewno nie zwróci wartości będąc w przypadku "else if".

oraz **2b) nie jest możliwe żeby oba wątki zwróciły wartość będąc w przypadku "if"**
BSO wątek A zwrócił pierwszy, tj. position[A] > position[B] + speed[B]. Zauważmy że w każdej sekwencji wykonań może nastąpić w wątku B co najwyżej jedno wykonanie position[B] = position[B] + speed[B], ponieważ jeśli nie wejdzie do "if", to na pewno wejdzie do "else if" (bo position[B] zwiększone o speed[B] wciąż jest mniejsze od position[A] - wiemy to z warunku wyjścia dla wątku A). Zauważmy też że nie wejdzie do "if'a" - stałoby to w sprzeczności z tym, że spełnia warunek z "else if'a". Zatem nie jest możliwe, aby oba wątki zwróciły będąc w "if" (bo pokazaliśmy, że drugi wątek na pewno wejdzie do "else if'a".

Łącząc a) oraz b) wiemy że jeden z wątków zwrócił wartość będąc w "if" a drugi będąc w "else if", zatem zwrócili tą samą wartość.

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

Zauważmy że prezentowane rozwiązanie nie jest wait-free. Jeżeli mamy sytuację, że position[A] = position[B] a procesy będą wykonywać się w taki sposób, że na każdy obrót while'a w A będą przypadały 3 obroty while'a w B to pętla nie zakończy się. Natomiast poziomy konsensusu są określane dla algorytmów wait-free. Nie stoi więc to w sprzeczności z określonym poziomem konsensusu dla rejestrów atomowych =1.

## Zadanie 6
:::success
Autor: Rafał Starypan
:::


A. Rozważmy n wątków zapisujących jednocześnie do obiektu klasy StickyBit. Mamy 2 przypadki:

a) Wszystkie wątki zapisały taką samą wartość X - wtedy zwrócona zostanie wartość X
b) Jeżeli wątek, który jako pierwszy wykonywał zapis, zapisał wartość X, a któryś z późniejszych Y, to wszystkie wartości poza pierwszą zostaną zignorowane, zatem stanem obiektu będzie wartość zapisana przez pierwszy wątek.

B. Każdy z ${log_2m}$ bitów naszego końcowego wyniku przechowujmy w obiekcie klasy StickyBit. Niech $i$-ty bit wyniku znajduje się w rejestrze $b_i$. Ponadto dla każdego z $n$ wątków przygotujmy pojedynczy rejestr atomowy MRSW $r_j$. Na początku zainicjujemy rejestry $r_j$ każdego wątku wartością tego wątku. Następnie w celu ustalenia wspólnej wartości będziemy iterować się po kolejnych bitach.

1. Niech zmienna lokalna $i$ (początkowo równa 0) oznacza numer bitu, który próbuje zapisać
wątek A.
2. Wątek A ustawi bit $b_i$ zgodnie z tym, co przechowuje w swoim rejestrze $r_A$.
3. Dopóki nie zapisaliśmy wszystkich bitów, tj. $i <= \log_2 M$
4. Wątek A zapisuje bit $b_i$.
5. Wątek A odczyta wartość bitu $b_i$ metodą read(). Jeśli odczytana wartość będzie zgodna z tym co A ma rejestrze (czyli będzie to wartość zapisana przez A), to inkrementujemy $i$, po czym przechodzimy do kroku 2.
6. W przeciwnym razie należy przeiterować się po rejestrach $r_j$ i znaleźć wartość $w$ innego wątku, której binarny prefiks [0...$i$] jest zgodny z bitami przechowywanymi
w obiektach [$b_0$...$b_i$].
7. Wykonujemy przypisanie $r_A$ = $w$, a następnie przechodzimy do kroku 2.

Każdy wątek zwróci taką samą wartość, która jest wartością wejściową pewnego z wątków, co dowodzi, że algorytm rozwiązuje problem konsensusu dla $M$ wartości i $n$ wątków.

## Zadanie 7
:::danger
Autor: dodeklarować
:::

> [name=PWit] Wskazówka: poziom konsensusu to 1. Zaimplementować protokół przybliżonej zgody używając jedynie zapisów/odczytów do rejestrów atomowych.

## Zadanie 8
:::success
Autor: Wiktor Hamberger
:::

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

* wartość zwracana przez decide() jest jedną z wartości zaproponowanych przez wątki
* peek() nie może zwrócić niczego, co nie zostało wrzucone na kolejkę
* metoda ta zwraca tę samą wartość wszystkim wątkom
* metoda zawsze zwraca pierwszego w kolejce i nigdy go nie ściąga, więca każdy dostnie tę samą wartość

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


<!-- 1. prostsza idea nie zadziala:
>Ta jest niepoprawna bo nawet jesli mozemy stwierdzic ze jakis watek sie ruszył, to nie mozemy byc pewni ze jego snap jest aktualny, bo inny mogl juz nadpisac, wiec musimy wziac pod uwage all threads.

2. poprawna -->
<!-- 

- poprostu atomowy rejestr MRSW, w ktoym mozemy zapisac
- trzy wartości: timestamp, wartosc, jakiś snapshot

^a to kod,
- ctor: mamy tablice atomic MRSW rejestrow
- update: robi scan, zapisuje w swoim (w nim jest writerem) MRSW rejestrze nowa wartosc z nowym timestamp'em wraz z outputem scan()
- collect: KOPIUJE CAŁĄ TABELĘ TYCH MRSW REJESTRÓW i zwraca kopię.

- scan:
- ma `bool moved[num_of_threads]` mowi czy dany thread sie ruszył podczas naszego skanowania.
- tak jak wczesniej robimy 2 scany
- idziemy po all wartosciach snapow:
- jak wyjdzie clean (czyli timestampy te same dla kazdej wartosci - kazdego rejestru - to return)
- wpp:
- jesli jakis ruszyl sie w przeszłości to zwracamy jego scan
- wpp oznacz ze sie ruszył, oldCopy = newCopy, i zaczynamy od nowa - collect znowu: `newCopy = collect()`
-->

<!--  -->
<!-- 4.3.1
Jasne, udowodnione w zad1.
Timestapmy się nie zmieniły więc żaden rejestr nie został aktualizowany pomiędzy collectami.

4.3.2
Czyli, że jak zrobilismy double collect,
a potem powtarzamy, to jesli timestampy sa znowu inne dla tego thread,
(pamiętajmy ze to sa rejestry t,ze kazdy ma jednego writera.)
to wtedy wartosc przeczytaana przez ostatnie wywolanie collect byla
napisana przez update ktory zaczął się po tym jak pierwszy collect sie zaczął.

więc faktycznie punkt linearyzacji jest na koncu wykonania metody
B updetowal swój rejestr pomiedzy 1 a 2 i 2 i 3. bo timestampy rosnął, a do B rejestru zapisuje tylko B
czyli były 2 diff double collect na tym samym rejestrze, oba nie clean
i oba z tego samego powodu. -->

<!-- 
 -->
<!-- 4.3.3.
czyli ze wartosc jest jedna z zapisanych - jest faktycznie snapshotem
Uwaga: skoro my robilismy scan, to nie zmienialismy swojej komorki, wiec nasza napewno ok.

Jeśli double collect to ok.
Jeśli snap innego, to wiemy z lematu 2, że $scan_B()$ był między pierwszym
i ostanim $read_A(rejestr_B)$ jego rejestru.
- itd. dla B, ktoś ostatecznie zwrobił clean_double collect -->
<!--
Czyli flaga moved[] mówi, że wątek się ruszył w trakcie naszego scan.
dlaczego jego snap jest ok? co znaczy ze sie nie zgadza? to ze jakis update
musial sie dokonac, kiedy sie dokonał? Z lematu 2 wiemy, że miedzy ostatnimi 2 readami.

ok. czyli on robiac ten update zrobil scan, skoro my robilismy scan,
to nie zmienialismy swojej komorki, wiec nasza napewno ok
wszystko sie powtarza az zostanie jeden
watek n-1: ten jeden ma taka sytuacje ze wszyscy robia scan, wiec jego scan
przed update musiał być clean double collectem, bo reszta robila scan wiec nie updateowała..
Więc ten ostani miał clean, ale skoro on miał clean i go zapisal,
to ten ktory wykryl dwa razy rozne mogl sobie zwrocic jego bo wiedzial, ze byl to clean scan itd. w górę.
Zwracamy więc poprawny snapshot. -->

<!-- 
 -->
<!-- 4.3.4
jasne

4.3.5
to wniosek z tego co udowodnilismy. -->
<!--  -->
<!--
Czyli rownowazne temu sequential, czyli, że faktycznie to jest stan z
zapisu. zapis ma ten punkt linearyzacji w:
 -->

---

- *wb* - współbierzny
* **Snapshot** : **atomowy** odczyt **wielu** komórek.
- Niepoprawny snapshot:
- 
- Nie jest to snapshot, bo odczyt nie był **atomowy**,
- A nie zwrócił wartośći z poprzedniego zapisu (update)
- A nie zwrócił wartości z żadnego zapisu (update), z którym był współbierzny (był jeden - $update_B$)
- Pytanie czy czerwony, a potem zielone jest poprawny?
- Tak, jest bo chodzi o taki odczyt, który istniał w pewnym momencie czasu, a nie o to, żeby traktować tablicę jak atomowy m-val rejestr.
- timestamp : ściśle rosnący licznik
- collect : kopiowanie rejestrów jeden po jednym, **nieatomowo**
- **CDC : clean double collect**
- Double collect jest clean gdy timestampy są równe dla każdego rejestru.
- oznacza to, że wartości w rejestrze R (dla każdego R) nie były aktualizowane pomiędzy pierwszym i drugim odczytem tego rejestru.
- bo jeśli były to licznik by się zmienił, bo jest ściśle rosnący
- wynik CDC to snapshot z momentu od razu po pierwszym collect.
- czyli pierwszy ma jakiś stan zapisany, a drugi potwierdza: skoro nic się nie zmieniło to jest to snapshot - nie zajdzie sytucja "zielone .. czerwony".
- Nas interesuje:
- 
- tylko jeden wątek może wykonywać funkcję na tym obiekcie w danym momencie czasu - jest sekwencyjny.
- linearyzowalność - czy instnieją punkty linearyzacji, dla których wywołanie jest równoważne sekwencyjnemu. Punkty linearyzacji - kiedy metoda 'ma efekt'. Dla zapisu/odczytu do rejestru jasne. Czasmi potrzebne jest więcej niż 1 punkt dla jednego wyołania metody. Zależy od metody.

---

## kod


- poprostu atomowy rejestr MRSW, w ktoym mozemy zapisac
- trzy wartości: timestamp, wartosc, jakiś snapshot

- ctor: mamy tablice atomic MRSW rejestrow
- update: robi scan, zapisuje w swoim (w nim jest writerem) MRSW rejestrze nowa wartosc z nowym timestamp'em wraz z outputem scan()
- collect: KOPIUJE CAŁĄ TABELĘ TYCH MRSW REJESTRÓW i zwraca kopię.

- scan:
- ma `bool moved[num_of_threads]` mowi czy dany thread sie ruszył podczas naszego skanowania.
- tak jak wczesniej robimy 2 scany
- idziemy po all wartosciach snapow:
- jak wyjdzie clean (czyli timestampy te same dla kazdej wartosci - kazdego rejestru - to return)
- wpp:
- jesli jakis ruszyl sie w przeszłości to zwracamy jego scan
- wpp oznacz ze sie ruszył, oldCopy = newCopy, i zaczynamy od nowa - collect znowu: `newCopy = collect()`

## dowód

Lemat 1: Jeśli wątek zwrócił wynik CDC to zwrócił snapshot.

- każdy wątek ma swój rejestr MRSW, do którego zapisuje.
- więc snapshot oznacza, że nikt nie zmienił swojego w trakcie robienia scan
>CleanDC oznacza, że żaden wątek nie zauktualizował swojego rejestru
w przedziale od jego odczytu w collect_1 do odczytu w collect_2, więc jest to snapshot. Jeśli wątek X by zauktualizował swój, to zmieniłby timestamp, więc nie byłby to **clean**DC.

Lemat 2: Jeśli robimy 2 razy double collect : $collect_1, collect_2$ oraz $collect_k collect_{k+1}$ i dwukrotnie obserujemy inne timestampy w collect wątku B, to pomiędzy każdą parą wywołań collect miało miejsce wywołanie $update_B()$

>Dla dowolnego DC: załóżmy, że nie było $update_B()$, skoro mamy rejestry MRSW i każdy wątek zapisuje do własnego to wartość w rejestrze B (czyli (timstamp, value, snap)) nie uległa zmianie, sprzeczność.

Lemat 3:
Pokażmy, że scan() zwraca poprawny snapshot.

- Przypomnienie: każdy wątek zapisuje do swojego rejestru 3 wartości: timestamp, value, snap.

- **Fakt 3.1**: Jeśli wątek jest trakcie wykonywania $scan() to jego rejestr się nie zmienia.
- wynika z faktu, że dany rejestr jest zmieniany tylko przez jeden wątek.
- oraz z tego, że w scan() nie zmieniamy rejestrów.

- **Fakt 3.2**: Jeśli wątek A zwraca $snap$ z rejestru wątku B to ostatnie wywołanie $update_B$ miało miejsce w całości podczas scanu A.
- jeśli A zwraca $snap$ to zrobiliśmy 2 DC w obu 2 różne timestampy
- więc z Lematu 2 wiemy, że w pomiędzy obiema parami $collect$ miał miejsce $update_B$ (bo jego rejestr B się zmienił, a tylko on tam zapisuje)
- więc drugi $update_B()$ miał miejsce po zakończeniu pierwszego, który miał efekt w trakcie $scan_A$, czyli drugi $update_B()$ był w całości wykonany podczas $scan_A()$.

- **Fakt 3.3**: Jeśli wątek A zwraca $snap$ z rejestru wątku B, to jest to $snap$ pochodzący ze scanu wywołanego w ramach ostatniego wywołania $update_B$.
- rejestr jest atomowy, tylko B tam zapisuje, i robi to w ramach ostatniej instrukcji $update_B$, tylko $update$ zmienia $snap$ w rejestrze.

- **Fakt 3.4**: Jeśli wątek A zwraca $snap$ z rejestru wątku B to jest wynik $scan_B$ wykonanego w trakcie $scan_A$ wew. ostatniego $update_B$.
- z faktów 3.2 i 3.3

Teraz lemat:
>Dla n wątków: $W_0, W_1, .. W_{n-1}$: załóżmy, że $W_0$ robi scan i, że nie zwrócił snapshota. Czyli zwrócił $snap$, który nie był wynikiem CDC, z faktu 3.4 wiemy, że to wynik scanu wb ze $scan_{W_0}()$.
Ale z faktu 3.1 wiemy, że rejestr wątku skanującego się nie zmienia, więc aplikując powyższe rozumowanie n-1 razy wnioskujemy, że był przedział czasowy w przeszłości w którym każdy wątek próbował wykonać scan, ze ściśłym zawieraniem przedziałów czasowych kolejnych skanów. Ale to oznacza, że ostatni w hierarchii musiał wykonać CDC, bo skoro reszta skanuje to nie zmienia swojego rejestru (fakt 3.1), sprzeczność.

Lemat 4: $O(n^2)$

>$scan$:
Możemy zrobić max n double collect (dla n wątków), potem albo zrobimy clean albo ktoś ruszył się 2 razy. Każdy collect to n odczytów, więc $O(n^2)$
$update$:
scan + $O(1)$

Tw 5: (wniosek)