Algorytmy rozproszone

Zadania

• • Zestaw 1

    • Termin: 7 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

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

  • Zestaw 2

    • Termin: 12 grudnia, godzina 23:59

    • Napisz prosty program do symulacji synchronicznego systemu rozproszonego na jednym komputerze:

      • jest n procesów numerowanych od 0 do n-1

      • program wczytuje ich połączenia z pliku wejściowego

      • działa w rundach

      • programy pisane dla symulatora powinny mieć wspólny interfejs, na przykład:

        • wysłanie komunikatu do (wszystkich) sąsiadów

        • odebranie komunikatu od sąsiada

        • zgłoszenie przez program chęci zakończenia / braku zmian w danej rundzie (może być potrzebne, żeby symulator stwierdził zakończenie programu)

      • programy (bez symulatora) powinny być łatwe do przeniesienia do systemu rozproszonego

    • Przy użyciu symulatora oprogramuj problemy z wykładu:

      • najkrótsze ścieżki (od wierzchołka numer 0)

        • wyjście: odległość od wierzchołka 0 dla każdego wierzchołka (n liczb w jednym wierszu)

    • UWAGA: minimalne drzewo rozpinające zostało przeniesione do zestawu 3

      • maksymalny zbiór niezależny

        • wyjście: numery wierzchołków z policzonego zbioru (wymienione w jednym wierszu)

    • Format danych wejściowych: plik tekstowy o n+1 wierszach, w pierwszym wierszu liczba n wierzchołków, w kolejnych wierszach informacje dla danego wierzchołka od 0 do n-1: liczba sąsiadów, a następnie dwie liczby dla każdego sąsiada - jego numer oraz odległość (jako liczba rzeczywista). Przykładowy zestaw danych tutaj.

    • Przykładowy graf jest spójny i symetryczny. Inne dane wejściowe będą spójne, ale niekoniecznie symetryczne.

  • Zestaw 3

    • Termin: 23 stycznia, godzina 23:59

    • Minimalne drzewo rozpinające z zestawu 2

      • symulator ten sam, co w zestawie 2, format wejścia również

      • format wyjścia: dla każdego wierzchołka podać rodzica, zakładając, że korzeń to wierzchołek numer 0

      • algorytm ma być oparty na tym z książki Nancy Lynch

      • można uprościć, ale za uproszczenia potrącam(y) część punkta:

        • routing - w prostszej wersji można wysyłać wiadomość bezpośrednio do innego wierzchołka, nawet jeśli nie ma krawędzi

        • znajomość liczby wierzchołków - w prostszej wersji symulator może podać każdemu wierzchołkowi wielkość sieci; w standardowej wersji nie powinien

Zasady zaliczania

Na podstawie laboratorium, ścisłe terminy. Będą 3 zestawy zadań - mniej więcej na 5 laboratoriów każdy. 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 muszą być oddane wszystkie trzy zestawy

  • 50% - dst

  • 60% - dst+

  • 70% - db

  • 80% - db+

  • 90% - bdb

  • 100% - bdb+

Literatura

Nancy Lynch, "Distributed Algorithms"

Uwagi studentów