Από DistrSys
- 1o Πρόβλημα
- Χρησιμοποιείστε το μοντέλο αυτόματων εισόδου/εξόδου για να μοντελοποιήσετε την εκτέλεση (σε ασύγχρονα κατανεμημένα συστήματα) των ακόλουθων αλγόριθμων:
- 2o Πρόβλημα
- Θεωρείστε ένα ασύγχρονο κατανεμημένο σύστημα με n διεργασίες συνδεδεμένες μέσω ενός γενικού, μη-κατευθυνόμενου δικτύου με m κανάλια επικοινωνίας, όπου κάθε διεργασία έχει μια μοναδική ταυτότητα αλλά δεν γνωρίζει το σύνολο των διεργασιών, ούτε την τοπολογία του δικτύου. Σχεδιάστε έναν κατανεμημένο αλγόριθμο που επιτρέπει σε όλες τις διεργασίες να κατασκευάσουν ένα επικαλυπτικό δέντρο. Υποθέτουμε μια διεργασία u0 η οποία ξεκινάει την εκτέλεση του αλγορίθμου. Έστω ότι κατά την εκτέλεση του αλγόριθμου προκύπτουν σ σφάλματα τερματισμού. Περιγράψτε τον αλγόριθμό σας (δώστε ψευδο-κώδικα), αναλύστε την ορθότητα του αλγόριθμου, την χρονική πολυπλοκότητα και την πολυπλοκότητα μηνυμάτων. Αποδείξτε τους ισχυρισμούς σας.
- 3o Πρόβλημα
- Θεωρείστε ένα ασύγχρονο κατανεμημένο σύστημα με n διεργασίες συνδεδεμένες μέσω ενός γενικού, μη-κατευθυνόμενου δικτύου, όπου κάθε διεργασία γνωρίζει τη διάμετρο του δικτύου. Για την εκπομπή ενός μηνύματος M από μια διεργασία-πομπό σε όλες τις άλλες διεργασίες του δικτύου, εκτελείται ο ακόλουθος αλγόριθμος: Η διεργασία-πομπός επιλέγει μια τιμή T μεγαλύτερη ή ίση με τη διάμετρο του δικτύου και στέλνει <M,T> σε όλους τους γείτονες της. Όταν μια διεργασία λάβει ένα μήνυμα <M,t>, αν t>0, στέλνει το μήνυμα <M,t-1> σε όλους τους γείτονες της. Απαντήστε στα παρακάτω ερωτήματα:
- Δείξτε ότι κάθε διεργασία λαμβάνει το M σε χρόνο ανάλογο της απόστασής της από τη διεργασία-πομπό.
- Έστω ότι ο μέσος βαθμός του δικτύου επικοινωνίας είναι k (δηλ.~μέσος αριθμός γειτόνων). Αναλύστε την πολυπλοκότητα μηνυμάτων για μια εκπομπή, σαν συνάρτηση των T και k.
- Μοντελοποιείστε την εκτέλεση του αλγόριθμου χρησιμοποιώντας το μοντέλο αυτόματων εισόδου/εξόδου.
|
Παράδοση:
- Η άσκηση είναι ατομική
- Η παράδοση γίνεται μέσω ηλεκτρονικού ταχυδρομείου στον Γιώργο Μυλωνά
- Η προθεσμία υποβολής είναι η Τρίτη 13 Φεβρουαρίου, ώρα 23:59
- Το όνομα του αρχείου με τις απαντήσεις να είναι της μορφής: ex2_AM_Epitheto_Onoma.zip
- Σε περίπτωση που η άσκηση παραδοθεί με καθυστέρηση θα υπάρξει μείωση βαθμού
- Σε περίπτωση που εντοπιστεί αντιγραφή, η άσκηση θα μηδενιστεί
Σχετικό υλικό:
Απαντήσεις:
Βαθμολογία:
| ΑΜ |
Ονοματεπώνυμο |
Βαθμός |
| 2724 | Σιδέρης Κυριάκος | 7 |
| 2737 | Τσαμπουκάς Πέτρος | 10 |
| 2807 | Αθανασάκης Χρήστος | 0 |
| 2812 | Αντωνέλλης Δημήτριος | 7 |
| 2813 | Αποστόλου Παναγιώτης | 6.5 |
| 2817 | Βαλσόματζης Εμμανουήλ | 8 |
| 2827 | Γεωργάς Βαγγέλης | 0 |
| 2830 | Γκατζέλης Βασίλης | 10 |
| 2844 | Ζάμπου Ελένη | 5 |
| 2846 | Ζούζιας Αναστάσιος | 9.5 |
| 2864 | Κουκόπουλος Ζώης | 10 |
| 2873 | Κωστάκης Θύμιος | 0 |
| 2889 | Μιχαήλ Όθωνας | 5 |
| 2893 | Μόσχος Βασίλειος | 10 |
| 2913 | Παπακηρύκου Ευάγγελος | 7.5 |
| 2916 | Παπουτσάκης Κων/νος | 10 |
| 2917 | Παπουτσιδάκης Μάρκος | 8 |
| 2932 | Ραμαντά Ιωάννα | 10 |
| 2939 | Σαλτού Αναστασία | 5 |
| 2952 | Σπύρου Αναστασία | 10 |
| 2954 | Στεργιανέλη Ειρήνη | 5 |
| 3046 | Δημητρός Κωνσταντίνος | 9.5 |
| 3053 | Αλτάνης Αλέξανδρος | 7.5 |
| 3077 | Γιαννοπούλου Γεωργία | 8 |
| 3078 | Γιαννούλης Γιώργος | 10 |
| 3097 | Θεοδωρίδης Ιωάννης-Βασίλειος | 7 |
| 3112 | Καραμπίνας Δημήτρης | 9.5 |
| 3118 | Κιούφτης Βασίλειος | 10 |
| 3125 | Κοντοτάσιου Ιωάννα | 10 |
| 3130 | Κούστα Μαρία | 10 |
| 3171 | Μπέσσας Απόστολος | 10 |
| 3173 | Μποχρίνη Σταυρούλα | 10 |
| 3206 | Ρεσβάνης Μιχάλης | 10 |
| 3207 | Ρίνης Ηλίας | 10 |
| 3220 | Σταθόπουλος Αναστάσιος | 10 |
| 3249 | Χριστοφοράκη Μαρία | 10 |
