- 1o Θέμα [20%]
- Θεωρείστε ένα κατανεμημένο σύστημα από n=16 διεργασίες, συνδεδεμένες μέσω ενός δικτύου κατευθυνόμενου δακτυλίου. Κάθε διεργασία έχει μια ταυτότητα u1, ..., u16 που είναι αντίστοιχα, 25,3,6,15,19,8,7,14,4,22,21,18,24,1,10,23
- Έστω ότι το κατανεμημένο σύστημα είναι σύγχρονο και οι διεργασίες εκτελούν τον αλγόριθμο εκλογής αρχηγού LCR (ο αλγόριθμος των LeLann, Chang και Roberts). Ποια διεργασία θα εκλεγεί αρχηγός? Πόσα μηνύματα θα ανταλλάξουν οι διεργασίες έως ότου εκλεγεί ο αρχηγός? Σε ποιόν γύρο θα εκλεγεί ο αρχηγός?
- Έστω ότι το κατανεμημένο σύστημα είναι ασύγχρονο και οι διεργασίες εκτελούν τον αλγόριθμο εκλογής αρχηγού AsynchPLE (ο αλγόριθμος του Peterson). Ποια διεργασία θα εκλεγεί αρχηγός? Πόσα μηνύματα θα ανταλλάξουν οι διεργασίες έως ότου εκλεγεί ο αρχηγός? Σε ποιόν γύρο θα εκλεγεί ο αρχηγός?
- 2o Θέμα [20%]
- Θεωρείστε ένα ασύγχρονο κατανεμημένο σύστημα με n διεργασίες συνδεδεμένες μέσω ενός γενικού δικτύου με m κανάλια επικοινωνίας. Οι διεργασίες εκτελούν τον αλγόριθμο αναζήτησης κατα εύρος AsynchBFS με ρίζα του δέντρου την διεργασία u0.
- Περιγράψτε μια εκτέλεση του αλγόριθμου που χρησιμοποιεί τον μέγιστο αριθμό μηνυμάτων.
- Περιγράψτε μια εκτέλεση του αλγόριθμου που απαιτεί τον μέγιστο χρόνο για να τερματίσει.
- 3o Θέμα [30%]
- Θεωρείστε ένα ασύγχρονο κατανεμημένο σύστημα με n διεργασίες συνδεδεμένες μέσω ενός γενικού, μη-κατευθυνόμενου δικτύου με m κανάλια επικοινωνίας. Κάθε διεργασία έχει μια μοναδική ταυτότητα και δεν γνωρίζει το σύνολο των διεργασιών, ούτε την τοπολογία του δικτύου. Σχεδιάστε έναν κατανεμημένο αλγόριθμο που να λύνει το "πρόβλημα της αναγνώρισης": κάθε διεργασία είναι ενήμερη για τις ταυτότητες όλων των άλλων διεργασιών. Δώστε την χρονική πολυπλοκότητα και την πολυπλοκότητα μηνυμάτων του αλγόριθμου σας.
- 4o Θέμα [30%]
- Θεωρείστε ένα σύγχρονο κατανεμημένο σύστημα με n διεργασίες συνδεδεμένες μέσω ενός γενικού, μη-κατευθυνόμενου δικτύου με m κανάλια επικοινωνίας, όπου κάθε διεργασία γνωρίζει τη δομή του δικτύου. Κάθε διεργασία u δέχεται ως είσοδο μία τιμή iu από το σύνολο S, δηλ. iu∈S. Οι διεργασίες πρέπει να συμφωνήσουν σε μια κοινή τιμή εκτελώντας τον αλγόριθμο συναίνεσης FloodSet. Έστω ότι κατά την εκτέλεση του αλγόριθμου προκύπτουν σ σφάλματα τερματισμού. Επιτρέπουμε στον αλγόριθμο να εκτελεστεί για σ γύρους αντί για σ+1 γύρους.
- Περιγράψτε ένα σενάριο όπου παραβιάζονται τα κριτήρια που διατυπώθηκαν για το πρόβλημα της συναίνεσης.
- Ποιος είναι ο μεγαλύτερος αριθμός από διαφορετικές αποφάσεις που μπορεί να πάρουν οι διεργασίες που δεν παρουσιάζουν σφάλμα?
- 5o Θέμα [bonus -- προαιρετικό για όσους παρέδωσαν ασκήσεις]
- Θεωρείστε ένα σύγχρονο κατανεμημένο σύστημα με n=3 μονάδες u1, u2, u3 συνδεδεμένες μέσω ενός μη-κατευθυνόμενου δικτύου με m=2 κανάλια επικοινωνίας, συγκεκριμένα u1u2 και u1u3. Κάθε διεργασία u έχει μοναδική ταυτότητα και πιο συγκεκριμένα, οι ταυτότητες των u2 και u3 είναι διαδοχικοί φυσικοί αριθμοί, δηλ. αν u2 = 50 τότε η ταυτότητα της u3 θα είναι είτε 49 είτε 51. Κάθε γύρο, η διεργασία u1 θέτει την εξής ερώτηση σε μια από τις u2 και u3: "Γνωρίζεις την ταυτότητα της άλλης διεργασίας?". Οι u2, u3 μπορούν μόνο να απαντήσουν θετικά ή αρνητικά στις ερωτήσεις της u1 και δεν επιτρέπεται να θέσουν δικές τους ερωτήσεις. Υπάρχει τρόπος η u2 ή η u3 να μπορέσει να απαντήσει στην ερώτηση της u1 θετικά? Αν ναι, πώς? Αν όχι, γιατί?
|
