Systemy rozproszone

Zadania

• • Zestaw 1

    • Termin: 2 listopada, godzina 23:59 (omówienie z prowadzącym na kolejnych zajęciach), sposób oddawania do uzgodnienia z prowadzącym pracownię

    • Oprogramuj komunikacje za pomocą protokołu TCP

    • Oprogramuj komunikacje za pomocą protokołu UDP

    • Użyj powyższych protokołów do oprogramowania prostego komunikatora tekstowego

    • Użyj powyższych protokołów do oprogramowania prostej gry zręcznościowej (któraś z poniższych):

      • węże

      • siatkówka

    • [Dodatkowo]: zilustruj złe zachowanie zastosowań przy złym dobraniu protokołu (może być konieczne równoległe przesyłanie dużych plików pomiędzy komputerami lub korzystanie przez inny program z tego samego portu, żeby utrudnić komunikację).

  • Zestaw 2

    • Termin: 2 grudnia, godzina 23:59 (omówienie z prowadzącym na kolejnych zajęciach), sposób oddawania do uzgodnienia z prowadzącym pracownię

    • Oprogramuj którąś z omówionych na wykładzie (12 grudnia, poprawka: listopada) rozproszonych tablic hashujących (Chord, CAN lub Kademlia)

    • Lepiej symulator (bo nie uruchomimy tego na kilku tysiącach komputerów)

      • w takim przypadku należy wypisywać jakiś debug - jaką funkcję wykonujemy i jak przebiega routing

    • Zakładamy dla uproszczenia że wierzchołki w sieci nie psują się

    • Funkcjonalności (wszystkie z hashem jako parametrem):

      • join - dołączanie

      • insert - wstaw dane do sieci

      • find - znajdź dane w sieci

      • leave - opuść sieć

Wykłady:

• 1. Wstęp

  2. Wybór lidera

  3. Ogólne algorytmy grafowe

  4. Consensus w systemie rozproszonym z uszkodzeniami połączeń

  5. Rozproszone tablice hashujące (DHTs): CAN, Chord

  6. Rozproszone tablice hashujące: Distance-Halving / Continuous-Discrete Approach, Kademlia

  7. Consensus z psuciem wierzchołków

  8. Consensus z wierzchołkami złośliwymi

  9. Algorytmy równoległe

Zasady zaliczania

Na podstawie laboratorium, ścisłe terminy. Będą 2 zestawy zadań. System i język programowania dowolny, do uzgodnienia z prowadzącym

Za kazdy zestaw zadań można dostać 1 punkt (dopuszczalne są ułamki)

• • tydzień spóźnienia powoduje obniżenie wyniku o 0.25, dwa tygodnie spóźnienia o 0.5, dłuższe spóźnienie dyskwalifikuje

  • na zaliczenie trzeba oddać oba zestawy

  • 50% - dst

  • 60% - dst+

  • 70% - db

  • 80% - db+

  • 90% - bdb

Zadania można oddawać w parach.

Literatura

Gerard Tel, "Introduction to Distributed Algorithms"

Nancy Lynch, "Distributed Algorithms"

George Coulouris et al, "Distributed Systems Concepts and design"