Από DistrSys
- 1o Θέμα [20%]
- Θεωρείστε ένα ασύγχρονο κατανεμημένο σύστημα με n διεργασίες συνδεδεμένες μέσω ενός γενικού, μη-κατευθυνόμενου δικτύου με m κανάλια επικοινωνίας.
- Για το πρόβλημα της εύρεσης συντομότερων μονοπατιών, προτείνετε μια αλγοριθμική λύση που να ελαχιστοποιεί την χρονική καθυστέρηση.
- Για το πρόβλημα της εύρεσης συντομότερων μονοπατιών, προτείνετε μια αλγοριθμική λύση που να ελαχιστοποιεί τον αριθμό μηνυμάτων που ανταλλάσουν οι διεργασίες. Σε αυτή την περίπτωση, μπορούμε να υποθέσουμε ότι γνωρίζουμε άνω όρια για τον χρόνο εκτέλεσης κάθε διεργασίας και για τον χρόνο παράδοσης του παλαιότερου μηνύματος που βρίσκεται σε κάποιο κανάλι επικοινωνίας.
- Για το πρόβλημα της αναζήτησης κατα εύρος, προτείνετε μια αλγοριθμική λύση που να λύνει το πρόβλημα ελαχιστοποιώντας τον αριθμό μηνυμάτων που ανταλλάσουν οι διεργασίες.
- Για το πρόβλημα της αναζήτησης κατα εύρος, προτείνετε μια αλγοριθμική λύση που να λύνει το πρόβλημα ελαχιστοποιώντας την χρονική καθυστέρηση.
- Ως αλγοριθμική λύση θεωρούμε είτε έναν αλγόριθμο (από την βιβλιογραφία) είτε μια συλλογή αλγορίθμων (από την βιβλιογραφία). Κατα την περιγραφή της πρότασης σας, αναφέρετε ξεκάθαρα όποιες επιπλέον υποθέσεις πρέπει να γίνουν ως προς τον τρόπο λειτουργίας του συστήματος πέρα από αυτές που αναφέρονται σε κάθε ερώτημα.
- 2o Θέμα [25%]
- Θεωρείστε ένα σύγχρονο κατανεμημένο σύστημα με n διεργασίες συνδεδεμένες μέσω ενός γενικού, μη-κατευθυνόμενου δικτύου με m κανάλια επικοινωνίας. Οι διεργασίες του συστήματος, συμμετέχουν στην διεκπεραίωση μιας δοσοληψίας εκτελόντας τον αλγόριθμο ThreePhaseCommit. Αποδείξτε ότι μετά απο τρεις γύρους εκτέλεσης του αλγόριθμου τα ακόλουθα ισχύουν στο δίκτυο:
- Αν κάποια διεργασία βρίσκεται στην κατάσταση k1 ή "έτοιμη", τότε οι αρχικές τιμές όλων των διεργασιών είναι "ναι"
- Αν κάποια διεργασία βρίσκεται στην κατάσταση k0, τότε καμία διεργασία δεν είναι στην κατάσταση k1 και καμία ενεργή διεργασία δεν είναι στην κατάσταση "έτοιμη"
- Αν κάποια διεργασία βρίσκεται στην κατάσταση k1, τότε καμία διεργασία δεν είναι στην κατάσταση k0, και καμία ενεργή διεργασία δεν είναι στην κατάσταση "άγνωστη"
- 3o Θέμα [25%]
- Θεωρείστε ένα ασύγχρονο κατανεμημένο σύστημα με n διεργασίες συνδεδεμένες μέσω ενός γενικού, μη-κατευθυνόμενου δικτύου με m κανάλια επικοινωνίας, όπου κάθε διεργασία έχει μια μοναδική ταυτότητα αλλά δεν γνωρίζει το σύνολο των διεργασιών, ούτε την τοπολογία του δικτύου. Σχεδιάστε έναν αλγόριθμο που να κατασκευάζει ένα εικονικό δακτύλιο. Υποθέτουμε μια διεργασία u0 η οποία ξεκινάει την εκτέλεση του αλγορίθμου. Στο τέλος της εκτέλεσης του αλγορίθμου όλες οι διεργασίες γνωρίζουν τους γειτονικούς κόμβους στο εικονικό δακτύλιο. Περιγράψτε τον αλγόριθμό σας (δώστε ψευδο-κώδικα), αναλύστε την ορθότητα του αλγόριθμου, την χρονική πολυπλοκότητα και πολυπλοκότητα μηνυμάτων. Αποδείξτε τους ισχυρισμούς σας.
- 4o Θέμα [30%]
- Θεωρείστε ένα σύγχρονο κατανεμημένο σύστημα με n διεργασίες συνδεδεμένες μέσω ενός γενικού, μη-κατευθυνόμενου δικτύου με m κανάλια επικοινωνίας, όπου κάθε διεργασία έχει μια μοναδική ταυτότητα αλλά δεν γνωρίζει το σύνολο των διεργασιών, ούτε την τοπολογία του δικτύου. Κάθε διεργασία u δέχεται ως είσοδο έναν ακέραιο αριθμό iu. Σχεδιάστε έναν κατανεμημένο αλγόριθμο που επιτρέπει σε μια διεργασία u0 να εντοπίσει το ζεύγος γειτονικών διεργασιών k,l με το μέγιστο άθροισμα ik + il. Περιγράψτε τον αλγόριθμό σας (δώστε ψευδο-κώδικα), αναλύστε την ορθότητα του αλγόριθμου, την χρονική πολυπλοκότητα και πολυπλοκότητα μηνυμάτων. Αποδείξτε τους ισχυρισμούς σας.
|
Σχετικό υλικό:
Βαθμολογία:
| ΑΜ |
Ονοματεπώνυμο |
Βαθμός |
| 2724 | Σιδέρης Κυριάκος | 8.5 |
| 2737 | Τσαμπουκάς Πέτρος | 8.5 |
| 2807 | Αθανασάκης Χρήστος | 9.5 |
| 2812 | Αντωνέλλης Δημήτριος | 10 |
| 2813 | Αποστόλου Παναγιώτης | 4.5 |
| 2817 | Βαλσόματζης Εμμανουήλ | 6 |
| 2827 | Γεωργάς Βαγγέλης | 9 |
| 2830 | Γκατζέλης Βασίλης | 7.5 |
| 2844 | Ζάμπου Ελένη | 9.5 |
| 2846 | Ζούζιας Αναστάσιος | 10 |
| 2864 | Κουκόπουλος Ζώης | 10 |
| 2873 | Κωστάκης Θύμιος | 9.5 |
| 2889 | Μιχαήλ Όθωνας | 8 |
| 2906 | Ξαγοράρης Μάρκος | 9 |
| 2913 | Παπακηρύκου Βαγγέλης | 7.5 |
| 2916 | Παπουτσάκης Κων/νος | 7.5 |
| 2917 | Παπουτσιδάκης Μάρκος | 5.5 |
| 2932 | Ραμαντά Ιωάννα | 8.5 |
| 2939 | Σαλτού Αναστασία | 10 |
| 2952 | Σπύρου Αναστασία | 9 |
| 2954 | Στεργιανέλη Ειρήνη | 10 |
| 3021 | Ασημακόπουλος Σωτήρης | 7 |
| 3053 | Αλτάνης Αλέξανδρος | 10 |
| 3077 | Γιαννοπούλου Γεωργία | 9.5 |
| 3078 | Γιαννούλης Γιώργος | 9.5 |
| 3097 | Θεοδωρίδης Ιωάννης-Βασίλειος | 9.5 |
| 3112 | Καραμπίνας Δημήτρης | 10 |
| 3125 | Κοντοτάσιου Ιωάννα | 9 |
| 3130 | Κούστα Μαρία | 7 |
| 3167 | Μπαιρακτάρης Κων/νος | 8.5 |
| 3171 | Μπέσσας Απόστολος | 10 |
| 3173 | Μποχρίνη Σταυρούλα | 4.5 |
| 3206 | Ρεσβάνης Μιχάλης | 10 |
| 3207 | Ρίνης Ηλίας | 10 |
| 3220 | Σταθόπουλος Αναστάσιος | 9 |
