Από DistrSys
- 1o Πρόβλημα
- Θεωρείστε ένα ασύγχρονο κατανεμημένο σύστημα με n διεργασίες συνδεδεμένες μέσω ενός δικτύου μη-κατευθυνόμενου δακτυλίου, όπου κάθε διεργασία έχει μια μοναδική ταυτότητα αλλά δεν γνωρίζει το σύνολο των διεργασιών, ούτε την τοπολογία του δικτύου. Σχεδιάστε έναν κατανεμημένο αλγόριθμο που να ορίζει μια κοινή κατεύθυνση στο δίκτυο δακτυλίου (ring orientation). Περιγράψτε τον αλγόριθμό σας, αναλύστε την ορθότητα του αλγόριθμου, την χρονική πολυπλοκότητα και πολυπλοκότητα μηνυμάτων. Αποδείξτε τους ισχυρισμούς σας.
- 2o Πρόβλημα
- Θεωρείστε ένα σύγχρονο κατανεμημένο σύστημα με n διεργασίες συνδεδεμένες μέσω ενός πλήρως συνδεδεμένου δικτύου, όπου κάθε διεργασία έχει μια μοναδική ταυτότητα και γνωρίζει τη δομή του δικτύου. Κάθε διεργασία u δέχεται ως είσοδο έναν ακέραιο αριθμό iu από το σύνολο S, δηλ. iu∈S. Έστω μεταβατικό σφάλμα τερματισμού ένα σφάλμα που αντιμετωπίζει μια διεργασία σε κάποιο γύρο r κατά το οποίο η διεργασία στέλνει ακαθόριστα μηνύματα στις γειτονικές διεργασίες (η συνάρτηση παραγωγής μηνυμάτων έχει ακαθόριστη συμπεριφορά), δεν αλλάζει κατάσταση (η συνάρτηση αλλαγής κατάστασης δεν εφαρμόζεται) και στον επόμενο γύρο r+1 επανέρχεται σε κανονική λειτουργία. Υποθέτουμε ότι οποιαδήποτε διεργασία μπορεί να αντιμετωπίσει τέτοιου είδους σφάλματα, όμως το πολύ ένα σφάλμα κάθε γύρο μπορεί να συμβεί. Σχεδιάστε έναν κατανεμημένο αλγόριθμο για το πρόβλημα της συναίνεσης. Υπάρχει λύση για το πρόβλημα ή όχι? Αποδείξτε τους ισχυρισμούς σας.
- 3o Πρόβλημα
- Θεωρείστε ένα σύγχρονο κατανεμημένο σύστημα με n διεργασίες συνδεδεμένες μέσω ενός γενικού, μη-κατευθυνόμενου δικτύου με m κανάλια επικοινωνίας, όπου κάθε διεργασία έχει μια μοναδική ταυτότητα αλλά δεν γνωρίζει το σύνολο των διεργασιών, ούτε την τοπολογία του δικτύου. Οι διεργασίες εκτελούν τον αλγόριθμο BellmanFord για την εύρεση των ελάχιστου μήκους μονοπατιών με την διεργασία u. Υποθέστε ότι κατά την εκτέλεση του συστήματος, οι διεργασίες ξεκινούν από μια ακαθόριστη κατάσταση: οι εσωτερικές μεταβλητές γονέας και απόσταση μπορούν να έχουν οποιαδήποτε τιμή. Εξηγείστε γιατί ο αλγόριθμος θα αποτύχει να βρει τα συντομότερα μονοπάτια. Περιγράψτε μια παραλλαγή του αλγόριθμου που να λύνει το πρόβλημα υπό αυτές τις συνθήκες εκκίνησης. Μπορείτε να αποδείξετε τους ισχυρισμούς σας?
|
Παράδοση:
- Η άσκηση είναι ατομική
- Η παράδοση γίνεται με την χρήση του εργαλείου submit-ds
- Η προθεσμία υποβολής είναι η Δευτέρα 26 Ιανουαρίου, ώρα 23:59
- Σε περίπτωση που η άσκηση παραδοθεί με καθυστέρηση θα υπάρξει μείωση βαθμού (10% ανά 24 ώρες)
- Σε περίπτωση που εντοπιστεί αντιγραφή, η άσκηση θα μηδενιστεί
Σχετικό υλικό:
Βαθμολογία:
| ΑΜ |
Ονοματεπώνυμο |
Βαθμός |
| 3042 | Φερεντίνου Κωσταντίνα | 4 |
| 3085 | Γούλας Χαράλαμπος | 7 |
| 3335 | Ακασιάδης Χαρίλαος | 7 |
| 3337 | Αλεξανδρίδης Ζαχαρίας | 9 |
| 3366 | Δημητρακόπουλος Γεώργιος | 4.5 |
| 3367 | Διαλυνάς Νικόλαος | 7 |
| 3410 | Κύρτσης Νικόλαος | 9 |
| 3426 | Λουκέρης Μιχαήλ | 5 |
| 3440 | Μουρτζίκου Γιαννούλα | 7 |
| 3465 | Παπαδάτος Σπύρος | 5 |
| 3473 | Περλής Βασίλης | 6 |
| 3517 | Χριστιάς Δημήτριος | 4 |
| 3526 | Παπαδόπουλος Γιώργος | 5 |
| 3534 | Νιάσσος Παναγιώτης | 8 |
| 3539 | Τσιλιώνης Ευθύμιος | 10 |
| 3559 | Δραγουμάνος Σταμάτης | 7 |
| 3612 | Αγγελίδης Νίκος | 7 |
| 3620 | Αλεξίου Χρυσάνθη | 5 |
| 3628 | Αραβάνης Κωνσταντίνος | 8 |
| 3635 | Γαλανόπουλος Ηλίας | 7 |
| 3640 | Γιαννουδάκης Γιάννης | 9 |
| 3644 | Γκορτσίλας Δημήτριος | 7 |
| 3645 | Γόντικας Γεώργιος | 8.5 |
| 3662 | Καλαϊτζής Χρήστος | 7 |
| 3666 | Κανιούρης Γιώργος | 5 |
| 3688 | Λεβεντέας Δημήτρης | 10 |
| 3694 | Μαστόρης Απόστολος | 7 |
| 3707 | Νικολάου Σταύρος | 9 |
| 3708 | Νοδαράκης Νικόλαος | 8.5 |
| 3709 | Νταλιακούρας Νικόλαος | 7.5 |
| 3711 | Οικονομίδης Ιωάννης | 8 |
| 3718 | Παπαβασιλείου Ιωάννης | 10 |
| 3719 | Παπαγεωργίου Ανδρέας | 7 |
| 3721 | Παπαζαφειροπούλου Τάνια | 9 |
| 3727 | Παυλογιάννης Ανδρέας | 10 |
| 3751 | Στρατογιάννης Γεώργιος | 10 |
| 3753 | Σφακιανάκης Γεώργιος | 9 |
| 3771 | Χαντζής Φώτης | 10 |
| 3793 | Σταύρου Βασίλειος | 9 |
| 3805 | Μάρκου Νικόλας | 6 |
| 3807 | Βασιλείου Πέτρος | 4 |
| 3808 | Κουβάρος Παναγιώτης | 9 |
| 3866 | Βούλγαρης Κώστας | 5 |
| 3873 | Παπαρροδοπούλου Αναστασία | 8 |
