# L7 - zarys teoretyczny (bez wyprowadzenia wzorów)

* **Safe boolean MRSW**
nic tu się nie dzieje, zwykła tablica bitów srsw, każdy wątek własny indeks

* **Regular boolean MRSW**
zmieniamy value tylko wtedy, gdy jest różne od ostatniego

* **Regular M-valued MRSW**

* **Atomic SRSW**
write(x) polega na ustawieniu i-tego bitu i wyzerowaniu wszystkich mniejszych
read() szuka pierwszego zapalonego bitu i zwraca jego indeks
ThreadLocal własny, osobny obiekt dla każdego wątku
stamp to para wartośc-czas
zapisujemy stampa wykonanego przez ostatniego write'a (obiekt lastStamp)
jak wątek odczytuje, to bierze wartość na podstawie maxa ze swojego ostatnio przeczytanego stampa i ogólnego stampa, ale nie aktualizuje ogólnego stampa, tylko swoją ostatnio przeczytaną wartość
jak robi write to aktualizuje ogólnego stampa

* **Atomic MRSW** (plansza odjeżdża XD)

mamy 2d tablice srsw
- każdy wątek trzyma swój ostatni czas zapisu w lastStamp (lokalnie)
- read() najpierw liczy zwracane value na podstawie największego stampa (czasu) z wiersza, potem zapisuje w kolumnie (poza sobą) value, a na końcu zwraca value
- write() aktualizuje swój ostatni czas zapisu, a potem zapisuje po przekątnej nowe value
- rozwiązuje to problem w którym np write zapisywałby a[0], a następnie jest uśpiony i nie zapisze od razu a[1...n-1], a następnie wątek 0 przeczytałby nową wartość, a wątki 1...n-1 przeczytałyby starą wartość (tak nie może być, dalsze read() nie mogą przeczytać innej wartości niż poprzedni read() w trakcie trwania write())
- dlatego read() zanim zwróci wartość to najpierw aktualizuje swoją zwracaną wartość, a potem aktualizuje w kolumnie value dla innych readów, dzięki temu unikamy problemu opisanego punkt wyżej

* **Atomic MRMW** (plansza odjechała)
- bazujemy na tablicy MRSW, każdy wątek ma swój indeks
- read() czyta całą tablicę i zwraca najświezszy rezultat
- write() najpierw sprawdza maksymalny czas w całej tablicy, a potem aktualizuje na sowim indeksie nową wartość z czasem +1

* **Migawka (snapshot) obstruction-free**
- chcemy odczytać wiele wartości, ale tak, żeby w trakcie czytania żadna z nich się nie zmieniła
- bazujemy na tablicy MRSW (kazdy wątek ma swój indeks)
- pomysł polega na kręceniu się w kółko, podwójnym odczycie, i jeśli odczyty są takie same no to nic nie mogło się zmienić i sukces, wpp. kręć się dalej
* **Migawka (snapshot) wait-free**
- update zapisuje sobie ostatni stan całej tablicy
- jeśli w trakcie trwania scan() jakiś wątek zrobił update() dwukrotnie, to możemy skorzystać z jego zapisu ostatniego stanu

* ogólny konsensus dla N wątków na podstawie N binarnych konsensusów
każdy wątek próbuje wygrać konsensus dla swojego bitu i ustawić innym że przegrali