Projekty zaliczeniowe¶

Propozycje projektów zaliczeniowych z bloku programowania funkcyjnego przedmiotu Metody Bezpiecznego Programowania.

Deliverable: kod źródłowy napisany w języku Scala z użyciem paradygmatu funkcyjnego (w wyłączności). Kod powinien być dostarczony przez gitlab na serwerze DSG.

Projeky mogą być wykonywane samodzielnie lub w grupach dwuosobowych. W wypadku grup dwuosobowych wymagany jest aktywny udział wszystkich człownków grupy w pracy koncepcyjnej i implementacyjnej w projekcie: aktywny udział poszczególnych członków grupy będzie potwierdzony przez historię projektu na gitlabie. Dodatkowo wszyscy członkowie grupy są odpowiedzialni nie tylko za “swoją część”, ale za całość: od wszystkich członków grupy wymagana jest dogłębna znajomość koncepcji i implementacji pozwalająca bronić zastosowanych podejść i technik i wprowadzać poprawki ad hoc.

Kod podlega ocenie przez obronę przez studenta/ów, która polega na krótkim przedstawieniu kodu prowadzącemu i dyskusji z prowadzącym na temat użytych mechanizmów.

Dostarczony kod będzie oceniany pod względem:

prawidłowego zastosowania mechanizmów paradygmatu funkcyjnego, ze szczególnym uwzględnieniem niezmienności stanu i struktur danych, zoptymalizowanej rekurencji, funkcji pierwszej klasy—programy napisane niefunkcyjnie nie będą przyjęte do oceny,

stosowania idiomatycznych mechanizmów języka Scala do programowania funkcyjnego (np. case classes, symbol literals, pattern matching, fold, Option),

poprawności (zapewnianych gwarancji) i wydajności przetwarzania współbieżnego/rozproszonego,

interesującego podejścia do problemu.

Dodatkowo kod powinien się kopilować i poprawnie wykonywać (t.j. spełaniać założenia projektu).

Istnieje możliwość zaproponowania własnego projektu. Istnieje także możliwość negocjacji projektów celem ich rozszerzenia lub ograniczenia: it doesn’t matter extacly what it does as long as it’s interesting.

Termin: przed egzaminem (... chyba, że dr Wojciechowski pozwoli po egzaminie)

2 Phase Commit

Zaimplementuj system transakcyjnej kontroli dostępu do rozproszonych zasobów obiektowych.

Model control flow: system zawiera n współdzielonych obiektów, s serwerów i c klientów. Każdy z obiektów jest unikalnie identyfikowalny i umieszczony na dokładnie jednym konkretnym i unikalnie identyfikolwalnym serwerze. Każdy obiekt współdzielony pozwala na wykonywanie dwóch operacji (np. za pomocą metod): odczytu i zapisu. Każdy z klientów może wywoływać dowolne dozwolone operacje na dowolnych obiektach współdzielonych.

Klienci używają obiektów współdzielonych w sposób transakcyjny. Transakcje stanowią sekcje krytyczne które mają początek i kończą się przez commit lub abort. Transakcja może zawierać dostępy do dowolnych obiektów współdzielonych w dowolnej liczbie i kolejności. Transakcja może także zawierać dowolny kod “lokalny,” nie kożystający z obiektów współdzielonych. Wszystkie dostępy do obiektów współdzielonych wewnątrz jednej transakcji są wykonywane atomowo. T.j. jesli transakcja wykonuje m operacji na k obiektach, to inne transakcje mogą zobaczyć wyniki wykonania albo wszystkich m operacji, albo żadnej operacji; każda transakcja odczytuje taki stan systemu, jak gdyby dana transakcja była jedyną operacją działającą w systemie.

Zachowanie atomowości jest zapewnione przez protokół two-phase commit. Transakcje używają logu lub bufora zamiast zapisywać dane bezpośrednio do rozproszonych obiektów. Kiedy transakcja wykonuje commit dwufazowo sprawdzane jest czy proponowane zmiany nie konfliktują ze zmianami wprowadzanymi przez inne transakcje (2PC Basic Algorithm). Jeśli nie występuje konflikt transakcja kończy commit, w przeciwnym wypadku transakcja wykonuje abort. Jeśli transakcja zakończyła się przez abort to zostaje wykonana ponownie, aż nie zakończy się przez commit.
3 Phase Commit

Zaimplementuj system transakcyjnej kontroli dostępu do rozproszonych zasobów obiektowych.

Model control flow: system zawiera n współdzielonych obiektów, s serwerów i c klientów. Każdy z obiektów jest unikalnie identyfikowalny i umieszczony na dokładnie jednym konkretnym i unikalnie identyfikolwalnym serwerze. Każdy obiekt współdzielony pozwala na wykonywanie dwóch operacji (np. za pomocą metod): odczytu i zapisu. Każdy z klientów może wywoływać dowolne dozwolone operacje na dowolnych obiektach współdzielonych.

Klienci używają obiektów współdzielonych w sposób transakcyjny. Transakcje stanowią sekcje krytyczne które mają początek i kończą się przez commit lub abort. Transakcja może zawierać dostępy do dowolnych obiektów współdzielonych w dowolnej liczbie i kolejności. Transakcja może także zawierać dowolny kod “lokalny,” nie kożystający z obiektów współdzielonych. Wszystkie dostępy do obiektów współdzielonych wewnątrz jednej transakcji są wykonywane atomowo. T.j. jesli transakcja wykonuje m operacji na k obiektach, to inne transakcje mogą zobaczyć wyniki wykonania albo wszystkich m operacji, albo żadnej operacji; każda transakcja odczytuje taki stan systemu, jak gdyby dana transakcja była jedyną operacją działającą w systemie.

Zachowanie atomowości jest zapewnione przez protokół three-phase commit. Transakcje używają logu lub bufora zamiast zapisywać dane bezpośrednio do rozproszonych obiektów. Kiedy transakcja wykonuje commit sprawdzane jest czy proponowane zmiany nie konfliktują ze zmianami wprowadzanymi przez inne transakcje (3PC Protocol Description). Jeśli nie występuje konflikt transakcja kończy commit, w przeciwnym wypadku transakcja wykonuje abort. Jeśli transakcja zakończyła się przez abort to zostaje wykonana ponownie, aż nie zakończy się przez commit.
Basic Versioning

Zaimplementuj system transakcyjnej kontroli dostępu do rozproszonych zasobów obiektowych.

Model control flow: system zawiera n współdzielonych obiektów, s serwerów i c klientów. Każdy z obiektów jest unikalnie identyfikowalny i umieszczony na dokładnie jednym konkretnym i unikalnie identyfikolwalnym serwerze. Każdy obiekt współdzielony pozwala na wykonywanie dwóch operacji (np. za pomocą metod): odczytu i zapisu. Każdy z klientów może wywoływać dowolne dozwolone operacje na dowolnych obiektach współdzielonych.

Klienci używają obiektów współdzielonych w sposób transakcyjny. Transakcje stanowią sekcje krytyczne które mają początek i kończą się przez commit lub abort. Transakcja może zawierać dostępy do dowolnych obiektów współdzielonych w dowolnej liczbie i kolejności. Transakcja może także zawierać dowolny kod “lokalny,” nie kożystający z obiektów współdzielonych. Wszystkie dostępy do obiektów współdzielonych wewnątrz jednej transakcji są wykonywane atomowo. T.j. jesli transakcja wykonuje m operacji na k obiektach, to inne transakcje mogą zobaczyć wyniki wykonania albo wszystkich m operacji, albo żadnej operacji; każda transakcja odczytuje taki stan systemu, jak gdyby dana transakcja była jedyną operacją działającą w systemie.

Zachowanie atomowości jest zapewnione przez protokół Basic Versioning Algorithm. Transakcje wykonują operacje bezpośrednio na obiektach (t.j. bez użycia buforów lub logu), ale operacja może być wstrzymana przez algorytm do czasu spełnienia odpowiedniego warunku (2.3.1 Basic verisoning). Transakcje wymagają podania wszystkich używanych obiektów a priori. Transakcja która rozpoczyna wykonywac commit zawsze kończy się przez commit.
Supremum Versioning

Zaimplementuj system transakcyjnej kontroli dostępu do rozproszonych zasobów obiektowych.

Model control flow: system zawiera n współdzielonych obiektów, s serwerów i c klientów. Każdy z obiektów jest unikalnie identyfikowalny i umieszczony na dokładnie jednym konkretnym i unikalnie identyfikolwalnym serwerze. Każdy obiekt współdzielony pozwala na wykonywanie dwóch operacji (np. za pomocą metod): odczytu i zapisu. Każdy z klientów może wywoływać dowolne dozwolone operacje na dowolnych obiektach współdzielonych.

Klienci używają obiektów współdzielonych w sposób transakcyjny. Transakcje stanowią sekcje krytyczne które mają początek i kończą się przez commit lub abort. Transakcja może zawierać dostępy do dowolnych obiektów współdzielonych w dowolnej liczbie i kolejności. Transakcja może także zawierać dowolny kod “lokalny,” nie kożystający z obiektów współdzielonych. Wszystkie dostępy do obiektów współdzielonych wewnątrz jednej transakcji są wykonywane atomowo. T.j. jesli transakcja wykonuje m operacji na k obiektach, to inne transakcje mogą zobaczyć wyniki wykonania albo wszystkich m operacji, albo żadnej operacji; każda transakcja odczytuje taki stan systemu, jak gdyby dana transakcja była jedyną operacją działającą w systemie.

Zachowanie atomowości jest zapewnione przez protokół Supremum Versioning Algorithm. Transakcje wykonują operacje bezpośrednio na obiektach (t.j. bez użycia buforów lub logu), ale operacja może być wstrzymana przez algorytm do czasu spełnienia odpowiedniego warunku (2.3.2 Supremum versioning, Transakcje Atomowe). Transakcje wymagają podania wszystkich używanych obiektów a priori. Dodatkowo dla każdego używanego obiektu należy dostarczyć supremum, t.j. górnej granicy liczby odwołań do każdgo z obiektu wewnątrz transakcji. Transakcja która rozpoczyna wykonywac commit zawsze kończy się przez commit.
Mesh Twitter

System zawiera n klientów połączonych siecią w topologii siatki. Siatka jest nietrwała i klienci mogą dynamicznie łączyć lub rozłączać się z siecią dynamicznie zmieniając jej topologię. Każdy unikalnie identyfikowalny klient c posiada chronologicznie uporządkowaną listę ogłoszeń lc do której może umieszczać ogłoszenia. Ogłoszenie to napis, który może zawierać odwołania do identyfikatorów konkretnych klientów. Każdy klient c1 może wyświetlić m najnowszych wiadomości związanych z dowolnym klientem c2 tworząc widok v(c1,c2), który jest tworzony z listy wszystkich ogłoszeń z lc1 i wszystkich ogłoszenia z list innych klientów które odwołują sie do c1.

System powinien pozwalać na propagacje informacji w systemie przez routing i flooding.
Peer-to-peer Scrabble

System zawiera n klientów połączonych siecią w topologii kliki. Klienci podlegają awariom powodujących rozłączenie. Klienci są unikalnie identyfikowalni i są symetryczni: żaden z klientów nie jest wyróżniony spośród pozostałych klientów (w szczególności, nie ma koordynatora). W konsekwencji klienci muszą uzgodnić między sobą stan systemu. Klienci prowadzą n osobową grę a la Scrabble.
File synchronization

System zawiera n klientów połączonych siecią z centralnym serwerem s. Każdy z klientów c posiada przestrzeń dyskową ds(c) która jest odzwierciedleniem przestrzeni dyskowej serwera ds(s). Każdy klient (współbieżnie) może dokonywać zmian w swojej przestrzeni dyskowej. Zmiany w ds(c) są odzwierciedlane w ds(s) i, w konsekwencji, zostają nastepnię odziweciedlone w ds(c’) dla każdego klienta c’ gdzie \(c' \neq c\). System minimalizuje ilość danych przesyłanych przez sieć.
Mesh drive

System zawiera n klientów połączonych siecią (być może, ale niekoniecznie kliką) bez centralnej koordynacji. Każdy z klientów c posiada przestrzeń dyskową ds(c) która jest odzwierciedleniem globalnej przestrzeni dyskowej ds(g). Każdy klient (współbieżnie) może dokonywać zmian w swojej przestrzeni dyskowej. Zmiany w ds(c) są odzwierciedlane w ds(g) i, w konsekwencji, zostają nastepnię (ostatecznie) odziweciedlone w ds(c’) dla każdego klienta c’ gdzie \(c' \neq c\). System minimalizuje ilość danych przesyłanych przez sieć.

Map-reduce concordancer

Konkordancja jest to słownik słów występujących w jakimś tekście, lub jakimś zbiorze tekstów, gdzie dla każdego słowa podana jest lista kontekstów w której to słowo występuje (kontekst to np. zdanie, albo z znaków przed i po słowie). Przykład.

System zawiera jednego klienta i n serwerów. Klient tworzy konkordancje na podstawie m plików tekstowych f1, f2, ... fm (pliki tekstowe np. z https://www.gutenberg.org/). Klient alokuje pliki do serwerów. Plik fi podlega dwóm etapom przetwarzania. Pierwszym jest przeformatowanie tekstu i oczyszczenie z niepotrzebnych elementów (np. numery stron) . Drugim jest wytworzenie na podstawie oczyszczonego tekstu konkordancji. Po zakończeniu przetwarzania wszystkich plików następuje agregacja cząstkowych konkordancji w jedną strukturę.
Peer-to-peer robocode (robot battle arena)

System zawiera k klientów połączonych w sieć w topologii kliki. Klienci uzgadniają wspólną logiczną planszę P w dwóch wymiarach. Rozgrywka prowadzona jest w rundach. W każdej rundzie dowolny klient uruchamia n robotów na planszy P, gdzie każdy z robotów ri jest zaprogramowamy przez użytkownika klienta za pomocą algorytmu A(ri). Po rozpoczęciu rundy roboty mogą w czasie rzeczywistym poruszać się po planszy, obracać się, prowadzić ogień, zderzać się, itp. (dokładne warunki pozostawione w kwestii osoby wkonującej projekt). Ostatni robot który żyje na P wygrywa rundę.

Wymagane jest, żeby system był zdecentralizowany: tj. żeby nie posiadał wyszczególnionych klientów którzy pełnią funkcję koordynatora systemu. System powinien utrzymywać właściwy (consistent) stan przez consensus.
Space battle sim

System zawiera k klientów połączonych w sieć w topologii kliki. Klienci uzgadniają wspólną logiczną planszę P w trzech wymiarach. Każdy z klientów ci posiada statek kosmiczny si położony na planszy P określony przez jego lokalizację, skierowanie, prędkość i wytrzymałość. Statki moga poruszać się po planszy przykładając do siebie wektor siły o zwrocie przeciwnym do zwrotu statku. Statki klientów prowadzą ze sobą walkę. Statki są wyposażone w dwa typy uzbrojenia: wiązkowe (beam) i kinetyczne. Uzbrojenie wiązkowe trafia w cel natychmiastowo. Uzbrojenie kinetyczne powoduje utworzenie obiektu na P o okreslonym skierowaniu i prędkości które przemieszcza się w przestrzeni aż do zderzenia się ze statkiem lub osiągnięcia granicy P.

Wymagane jest, żeby system był zdecentralizowany: tj. żeby nie posiadał wyszczególnionych klientów którzy pełnią funkcję koordynatora systemu. System powinien utrzymywać właściwy (consistent) stan przez consensus.
Evaluation deployment framework

System zawiera klaster składający się s serwerów w topologii kliki. System dostarcza usługę uruchamiania, monitorowania i zbierania wyników testów wydajnościowych korzystających z s serwerów (lub ich podzbioru). Zewnętrzny klient może zlecić wykonanie kodu benchmarku (np. plik jar napisany wg ustalonego API) na klastrze z konkretną konfiguracją. Powoduje to, że kod zostaje przepropagowany do odpowiednich serwerów w klastrze. Następnie kod jest wykonywany na t wątkach na każdym z serwerów (z konfiguracji). System sprawdza czeka obserwuje postęp każdego z wątków (np. przez API) i czeka aż wszystkie wątki się zakończą. Po zakończeniu wykonania system zbiera wyniki zapisywane przez benchmark lokalnie na każdym z serwerów i zwraca je klientowi w postaci zagregowanej.

Wymagane jest, żeby system był zdecentralizowany: tj. żeby nie posiadał wyszczególnionych klientów którzy pełnią funkcję koordynatora systemu. System powinien utrzymywać właściwy (consistent) stan przez consensus.
Mesh cell-phone FPS

System zawiera n klientów połączonych siecią w topologii siatki. Siatka jest nietrwała i klienci mogą dynamicznie łączyć lub rozłączać się z siecią dynamicznie zmieniając jej topologię. Każdy klient c jest unikalnie identyfikowalny i działa na urządzeniu mobilnym. Klient ma informacje o swoim fizycznym położeniu swojego urządzenia i swoim skierowaniu (w 3D). Klient ma także informacje o pozycji i kształcie fizycznych przeszkód. Klienty dają użytkownikom swoich urządzeń symulować strzelanie do innych osób skierowując urządzenie w ich kierunku i wywołując funkcję strzału. System informuje użytkownika o trafieniu i utrzymuje zagregowaną tablicę wyników.

Wymagane jest, żeby system był zdecentralizowany: tj. żeby nie posiadał wyszczególnionych klientów którzy pełnią funkcję koordynatora systemu. System powinien utrzymywać właściwy (consistent) stan przez consensus. System powinien pozwalać dynamicznie podłączać lub rozłączać klientów z sieci.
Circuit simulator

Zdarzeniowy symulator obwodów elektronicznych (cyfrowych lub analogowych). System składa się z n elementów, każdy element e1, e2, ..., en posiada (potencjalnie pusty) wektor wejść I(ei) i wyjść O(ei). Wejścia poszczególnych elementów połączane są z wyjściami innych elementów. Stan każdego wyjścia każdego elementu ei jest wyznaczone przez jakąś transmitancję. Jeśli stan wyjść ei się zmienia, ei przesyła informację o zmianie stanu do innych elementów których wejścia są połączone z wyjściami ei. Konfiguracja topologii elementów jest wyspecyfikowana przez użytkownika i system pozwala na dynamiczną rekonfigurację.
Actor-based toy languange REPL FP-ception (dla odważnych)

Parser i pętla read-execute-print dla własnego języka-zabawki, który wspiera przynajmniej następujące cechy: definicję etykiet/symboli, arytmetykę na liczbach całkowitych i symbolach, definicję i aplikację funkcji, funkcje pierwszej klasy i wyższego rzędu, oraz prostych aktorów.

Ankieta