Από DistrSys
- 1o Πρόβλημα
- Θεωρείστε ένα σύγχρονο κατανεμημένο σύστημα με n διεργασίες συνδεδεμένες μέσω ενός γενικού, μη-κατευθυνόμενου δικτύου με m κανάλια επικοινωνίας, όπου κάθε διεργασία έχει μια μοναδική ταυτότητα αλλά δεν γνωρίζει το σύνολο των διεργασιών, ούτε την τοπολογία του δικτύου. Οι διεργασίες αντιμετωπίζουν σφάλματα τερματισμού. Σχεδιάστε έναν σταθεροποιούμενο αλγόριθμο εκλογής αρχηγού. Περιγράψτε τον αλγόριθμό σας, αναλύστε την ορθότητα του αλγόριθμου, την χρονική πολυπλοκότητα και πολυπλοκότητα μηνυμάτων. Αποδείξτε τους ισχυρισμούς σας.
- 2o Πρόβλημα
- Θεωρείστε ένα σύγχρονο κατανεμημένο σύστημα με n διεργασίες συνδεδεμένες μέσω ενός γενικού, μη-κατευθυνόμενου δικτύου με m κανάλια επικοινωνίας, όπου κάθε διεργασία έχει μια μοναδική ταυτότητα αλλά δεν γνωρίζει το σύνολο των διεργασιών, ούτε την τοπολογία του δικτύου. Κάθε διεργασία u δέχεται ως είσοδο μία τιμή iu από το σύνολο N, δηλ. iu ∈ N. Σχεδιάστε έναν αλγόριθμο που να αποτιμά τα καθολικά κατηγορήματα: (α) ∃q • iq=15, (β) ∄q • iq%2=0, (γ) ∀q • iq%2=0 : ∃v • iq+iv>10. Περιγράψτε τον αλγόριθμό σας, αναλύστε την ορθότητα του αλγόριθμου, την χρονική πολυπλοκότητα και πολυπλοκότητα μηνυμάτων. Αποδείξτε τους ισχυρισμούς σας.
- 3o Πρόβλημα
- Υλοποιείστε τον σταθεροποιουμενο αλγόριθμο εκλογής αρχηγού που βασίζεται στην τεχνική power supply στο σύστημα Shawn. Μελετήστε την συμπεριφορά του αλγόριθμου στις τοπολογίες που σας έχουν δωθεί. Κατά την εκτέλεση του συστήματος θεωρείστε ότι οι διεργασίες όπου id%AM==0 (όπου AM τα 2 τελευταία ψηφία του ΑΜ σας, αν AM<50 τότε θέστε AM+50) λόγο σφαλμάτων τερματίζουν στον γύρο 3×δ. Μετρήστε τον χρόνο σταθεροποίησης τους αλγόριθμου, δηλ. τον αριθμό γύρων που απαιτείται για να βρεθεί 1 αρχηγός μετά τον γύρο 3×δ. Για την τοπολογία των 1000 κόμβων δώστε γράφημα που να μετράει το πλήθος των αρχηγών που υπάρχουν στο δίκτυο ώς προς τον γύρο εκτέλεσης. Σχολιάστε την συμπεριφορά του αλγορίθμου.
|
Παράδοση:
- Η άσκηση είναι ατομική
- Απαντήστε σε 2 από τα 3 προβλήματα
- Η παράδοση γίνεται με την χρήση του εργαλείου submit-ds
- Η προθεσμία υποβολής είναι η Παρασκευή 19 Φεβρουαρίου, ώρα 23:59
- Σε περίπτωση που εντοπιστεί αντιγραφή, η άσκηση θα μηδενιστεί
Σχετικό υλικό:
Απαντήσεις:
| ΑΜ |
Ονοματεπώνυμο |
Βαθμός |
1 |
2 |
3 |
| 3101 | Καλλιαντάσης Χρήστος | 0.75 | ½ | ✓ | - |
| 3108 | Κανελλόπουλος Ανάργυρος | 0.5 | ½ | ½ | - |
| 3270 | Κωστογιάννης Αθανάσιος | 0.25 | ½ | - | - |
| 3384 | Καλόγηρος Γεώργιος | 0.5 | ½ | ½ | - |
| 3569 | Πισπιρίγκος Γεώργιος | 0.5 | ✓ | - | - |
| 3575 | Ντούμας Φώτιος | 0.5 | - | ✓ | - |
| 3615 | Αδάμ Γιώργος | 0.5 | ½ | ½ | - |
| 3618 | Αθανασόπουλος Κωνσταντίνος | 0.25 | - | ½ | - |
| 3714 | Παλαγγιάς Νίκος | 0.5 | ✓ | - | - |
| 3724 | Παπουτσής Γεώργιος | 0.5 | ✓ | - | - |
| 3730 | Πετράκης Εμμανουήλ | 0.25 | ½ | - | - |
| 3732 | Πέτσινας Ηλίας | 0.5 | ✓ | - | - |
| 3741 | Σούλας Αγησίλαος | 0.5 | ✓ | - | - |
| 3773 | Χαρπαντίδης Βασίλειος | 1 | ✓ | ✓ | - |
| 3790 | Νέννες Ιωάννης | 0.5 | - | ✓ | - |
| 3859 | Χουλιαρόπουλος Αναστάσιος | 0.75 | ✓ | ½ | - |
| 3865 | Γεωργοπούλου Αργυρούλα | 1 | ✓ | ✓ | - |
| 3872 | Νούλας Γεώργιος | 1 | ✓ | ✓ | - |
| 4008 | Ράπτη Μαρία | 0.75 | ½ | ✓ | - |
|
