2005-2006:Κατανεμημένα Συστήματα Ι:Ασκήσεις:2η Άσκηση

Από DistrSys

1o Πρόβλημα Υλοποιήστε τον αλγόριθμο εκλογής αρχηγού PLE (ο αλγόριθμος του Peterson) για ασύγχρονα κατανεμημένα συστήματα (PLeader) στο περιβάλλον υλοποίησης κατανεμημένων αλγορίθμων DAP. 2o Πρόβλημα Υλοποιήστε τον αλγόριθμο κατασκευής επικαλυπτικού δέντρου για ασύγχρονα κατανεμημένα συστήματα (SpanningTree) στο περιβάλλον υλοποίησης κατανεμημένων αλγορίθμων DAP. 3o Πρόβλημα Υλοποιήστε τον αλγόριθμο αναζήτησης κατά εύρος για σύγχρονα κατανεμημένα συστήματα (SynchBFS) σε συνδυασμό με τον απλό συγχρονιστή (SimpleSynch) για ασύγχρονα κατανεμημένα συστήματα στο περιβάλλον υλοποίησης κατανεμημένων αλγορίθμων DAP (όνομα τελικού αλγόριθμου: SimpleSyncBFS) 4o Πρόβλημα Υλοποιήστε τον αλγόριθμο αναζήτησης κατά εύρος για ασύγχρονα κατανεμημένα συστήματα (AsynchBFS) στο περιβάλλον υλοποίησης κατανεμημένων αλγορίθμων DAP.

Παράδοση:

• Η άσκηση είναι ατομική
• Η παράδοση γίνεται μέσω ηλεκτρονικού ταχυδρομείου στον Γιώργο Μυλωνά
• Η προθεσμία υποβολής είναι η Δευτέρα 20 Φεβρουαρίου, ώρα 20:00

Παρατηρήσεις:

• Για την υλοποίηση των αλγόριθμων μπορείτε να χρησιμοποιήσετε όποιες δομές κρίνετε απαραίτητες από την βιβλιοθήκη της C++ (π.χ. vector) ή την LEDA.
• Το αρχείο που θα παραδώσετε πρέπει να είναι της μορφής AM#.tar.gz (όπου # είναι το ΑΜ) και να περιέχει
  1. ένα αρχείο README.TXT με το Ονοματεπώνυμο σας, Έτος και ΑΜ
  2. ένα αρχείο για κάθε πρόβλημα (η ονομασία προκύπτει από το όνομα του αλγορίθμου και την κατάληξη .c, π.χ. PLeader.C) -- προσοχή: οι ονομασίες είναι case-sensitive
  3. ένα αρχείο Makefile
• O κώδικας πρέπει να είναι καλά σχολιασμένος (με την χρήση σχολίων σε στρατηγικό και τακτικό επίπεδο). Δεν χρειάζεται να παραδώσετε αναφορά.
• Για τον έλεγχο της λειτουργίας των αλγόριθμων μπορείτε να χρησιμοποιήσετε τα αρχεία τοπολογίας του DAP:
  • Τοπολογία Δικτύου Κατευθυνόμενου Δακτυλίου 5 διεργασιών για τον αλγόριθμο PLeader
  • Τοπολογία Γενικού Δικτύου 7 διεργασιών για τον αλγόριθμο AsynchSpanningTree
  • Τοπολογία Γενικού Δικτύου 6 διεργασιών για τον αλγόριθμο SimpleSynchBFS
  • Τοπολογία Γενικού Δικτύου 9 διεργασιών για τον αλγόριθμο AsynchBFS

Σχετικό υλικό:

• Εκφώνηση άσκησης σε μορφή PDF
• LEDA Extension Package - Distributed Algorithms Platform
• Οδηγίες εγκατάστασης για το περιβάλλον υλοποίησης DAP
• Μοντέλο Ασύγχρονων Συστημάτων απο τις σημειώσεις του μαθήματος
• Βασικοί Αλγόριθμοι Ασύγχρονων Συστημάτων απο τις σημειώσεις του μαθήματος
• Συγχρονισμός στα Ασύγχρονα Συστήματα απο τις σημειώσεις του μαθήματος
• Διάταξη Γεγονότων και Λογικός Χρόνος απο τις σημειώσεις του μαθήματος
• Αμοιβαίος Αποκλεισμός σε Ασύγχρονα Συστήματα απο τις σημειώσεις του μαθήματος

Βαθμολογία:

ΑΜ	Ονοματεπώνυμο	Βαθμός
2370	Χριστόφορος-Λιβάνης Σπυρίδων	5
2694	Νιάβης Παναγιώτης	10
2818	Βεργούλης Αθανάσιος	6
2819	Βιέννας Εμμανουήλ	8
2847	Δάφνη-Σταυρούλα Ζώη	10
2853	Καντούνης Κάρολος	10
2856	Κατσάνος Ιωάννης	10
2863	Κοτρότσος Ιωάννης	2.5
2860	Κολαΐτη Ειρήνη	10
2862	Κοντάκης Απόστολος	10
2875	Λεδάκης Ιωάννης	5
2883	Μαζιώτης Αλέξανδρος	2.5
2885	Μαλή Γεωργία	10
2890	Μιχαήλ Παναγιώτης	10
2915	Παπαχαραλάμπους Λουκάς	8
2918	Παππά Αντιγόνη	9
2923	Πατρούμπα Δήμητρα	10
2926	Πετρόπουλος Αναστάσιος	6
2948	Σκούρα Αγγελική	10
2951	Σπυριδάκης Γεώργιος	7
2955	Στεφόπουλος Περικλής	2.5
2964	Τζελάτης Ιωάννης	8
2975	Φίλος - Ράτσικας Αλέξης	5
2979	Χαρίση Αμαλία	10
2982	Χέλμης Χαράλαμπος	10
3013	Καλλίγερος Ιωάννης-Χρήστος	2.5
3032	Οικονόμου Παναγιώτης	2.5