2008-2009:Κατανεμημένα Συστήματα Ι:Ασκήσεις

1^o Πρόβλημα

Θεωρείστε ένα σύγχρονο κατανεμημένο σύστημα με n διεργασίες συνδεδεμένες μέσω ενός δικτύου κατευθυνόμενου δακτυλίου, όπου κάθε διεργασία έχει μια μοναδική ταυτότητα αλλά δεν γνωρίζει το σύνολο των διεργασιών, ούτε την τοπολογία του δικτύου. Σχεδιάστε έναν κατανεμημένο αλγόριθμο εκλογής αρχηγού που βασίζεται μόνο σε πράξεις σύγκρισης ταυτοτήτων (δηλ., δύο ταυτότητες είναι ίδιες ή όχι). Υπάρχει λύση για το πρόβλημα ή όχι; Αποδείξτε τους ισχυρισμούς σας.

2^o Πρόβλημα

Θεωρείστε ένα σύγχρονο κατανεμημένο σύστημα με n διεργασίες συνδεδεμένες μέσω ενός πλήρως συνδεδεμένου δικτύου, όπου κάθε διεργασία έχει μια μοναδική ταυτότητα και γνωρίζει τη δομή του δικτύου. Κάθε διεργασία u δέχεται ως είσοδο έναν ακέραιο αριθμό i_u. Σχεδιάστε έναν κατανεμημένο αλγόριθμο που επιτρέπει σε κάθε διεργασία u να εντοπίσει την u_x και u_y, όπου i_x ≤ i_u και i_y ≥ i_u. Η διεργασία u_max (δηλ. με max(i)) εντοπίζει ως u_y την διεργασία u_min (δηλ. με min(i)). Η διεργασία u_min εντοπίζει ως u_x την διεργασία u_max. Αναλύστε την ορθότητα, χρονική πολυπλοκότητα και πολυπλοκότητα μηνυμάτων. Αποδείξτε τους ισχυρισμούς σας.

3^o Πρόβλημα

Θεωρείστε ένα σύγχρονο κατανεμημένο σύστημα με n διεργασίες συνδεδεμένες μέσω ενός πλήρως συνδεδεμένου δικτύου, όπου κάθε διεργασία έχει μια μοναδική ταυτότητα και γνωρίζει τη δομή του δικτύου. Κάθε διεργασία u δέχεται ως είσοδο έναν ακέραιο αριθμό i_u από το σύνολο S, δηλ. i_u∈S. Τροποποιείστε τον αλγόριθμο συναίνεσης FloodSet έτσι ώστε αν προκύψουν σ' < σ σφάλματα, τότε όλες οι εν λειτουργία διεργασίες να αποφασίσουν (χωρίς απαραιτήτως να τερματίσουν) στο τέλος του γύρου σ'+2. Αναλύστε την ορθότητα, χρονική πολυπλοκότητα και πολυπλοκότητα μηνυμάτων. Αποδείξτε τους ισχυρισμούς σας.

1^o Πρόβλημα

Θεωρείστε ένα ασύγχρονο κατανεμημένο σύστημα με n διεργασίες συνδεδεμένες μέσω ενός δικτύου μη-κατευθυνόμενου δακτυλίου, όπου κάθε διεργασία έχει μια μοναδική ταυτότητα αλλά δεν γνωρίζει το σύνολο των διεργασιών, ούτε την τοπολογία του δικτύου. Σχεδιάστε έναν κατανεμημένο αλγόριθμο που να ορίζει μια κοινή κατεύθυνση στο δίκτυο δακτυλίου (ring orientation). Περιγράψτε τον αλγόριθμό σας, αναλύστε την ορθότητα του αλγόριθμου, την χρονική πολυπλοκότητα και πολυπλοκότητα μηνυμάτων. Αποδείξτε τους ισχυρισμούς σας.

2^o Πρόβλημα

Θεωρείστε ένα σύγχρονο κατανεμημένο σύστημα με n διεργασίες συνδεδεμένες μέσω ενός πλήρως συνδεδεμένου δικτύου, όπου κάθε διεργασία έχει μια μοναδική ταυτότητα και γνωρίζει τη δομή του δικτύου. Κάθε διεργασία u δέχεται ως είσοδο έναν ακέραιο αριθμό i_u από το σύνολο S, δηλ. i_u∈S. Έστω μεταβατικό σφάλμα τερματισμού ένα σφάλμα που αντιμετωπίζει μια διεργασία σε κάποιο γύρο r κατά το οποίο η διεργασία στέλνει ακαθόριστα μηνύματα στις γειτονικές διεργασίες (η συνάρτηση παραγωγής μηνυμάτων έχει ακαθόριστη συμπεριφορά), δεν αλλάζει κατάσταση (η συνάρτηση αλλαγής κατάστασης δεν εφαρμόζεται) και στον επόμενο γύρο r+1 επανέρχεται σε κανονική λειτουργία. Υποθέτουμε ότι οποιαδήποτε διεργασία μπορεί να αντιμετωπίσει τέτοιου είδους σφάλματα, όμως το πολύ ένα σφάλμα κάθε γύρο μπορεί να συμβεί. Σχεδιάστε έναν κατανεμημένο αλγόριθμο για το πρόβλημα της συναίνεσης. Υπάρχει λύση για το πρόβλημα ή όχι? Αποδείξτε τους ισχυρισμούς σας.

3^o Πρόβλημα

Θεωρείστε ένα σύγχρονο κατανεμημένο σύστημα με n διεργασίες συνδεδεμένες μέσω ενός γενικού, μη-κατευθυνόμενου δικτύου με m κανάλια επικοινωνίας, όπου κάθε διεργασία έχει μια μοναδική ταυτότητα αλλά δεν γνωρίζει το σύνολο των διεργασιών, ούτε την τοπολογία του δικτύου. Οι διεργασίες εκτελούν τον αλγόριθμο BellmanFord για την εύρεση των ελάχιστου μήκους μονοπατιών με την διεργασία u. Υποθέστε ότι κατά την εκτέλεση του συστήματος, οι διεργασίες ξεκινούν από μια ακαθόριστη κατάσταση: οι εσωτερικές μεταβλητές γονέας και απόσταση μπορούν να έχουν οποιαδήποτε τιμή. Εξηγείστε γιατί ο αλγόριθμος θα αποτύχει να βρει τα συντομότερα μονοπάτια. Περιγράψτε μια παραλλαγή του αλγόριθμου που να λύνει το πρόβλημα υπό αυτές τις συνθήκες εκκίνησης. Μπορείτε να αποδείξετε τους ισχυρισμούς σας?

1^o Θέμα [40%]

Θεωρείστε ένα σύγχρονο κατανεμημένο σύστημα με n διεργασίες συνδεδεμένες μέσω ενός γενικού, μη-κατευθυνόμενου δικτύου με m κανάλια επικοινωνίας. Για κάθε μια από τις παρακάτω προτάσεις απαντήστε στο κατά πόσο μπορούμε να δώσουμε μια ορθή αλγοριθμική λύση χωρίς να κάνουμε επιπλέον υποθέσεις για το μοντέλο υπολογισμού. Εξηγήστε την απάντηση σας.

1. Μπορούμε να καταμετρήσουμε τις διεργασίες του συστήματος αν οι διεργασίες δεν έχουν μοναδικές ταυτότητες και δεν έχουν πρόσβαση σε κάποια γεννήτρια τυχαίων αριθμών.
2. Μπορούμε να συγχρονίσουμε τα ρολόγια δυο διεργασιών ακόμα και αν σε οποιαδήποτε εκτέλεση του συστήματος μπορεί να συμβούν ε σφάλματα επικοινωνίας.
3. Μπορούμε να υπολογίσουμε τη διάμετρο του δικτύου ακόμα και αν σε οποιαδήποτε εκτέλεση του συστήματος το πολύ β διεργασίες μπορούν να παρουσιάσουν βυζαντινά σφάλματα.
4. Μπορούμε να μετατρέψουμε οποιοσδήποτε αλγόριθμο A σε σταθεροποιούμενο δεδομένου ενός ορθού αλγόριθμου συνεπών ολικών στιγμιοτύπων.

2^o Θέμα [30%]

Θεωρείστε ένα ασύγχρονο κατανεμημένο σύστημα με n διεργασίες συνδεδεμένες μέσω ενός γενικού, μη-κατευθυνόμενου δικτύου με m κανάλια επικοινωνίας, όπου κάθε διεργασία έχει μια μοναδική ταυτότητα αλλά δεν γνωρίζει το σύνολο των διεργασιών, ούτε την τοπολογία του δικτύου. Προτείνετε μια αλγοριθμική λύση που να υπολογίζει τον ολικό αριθμό των διεργασιών. Περιγράψτε τον αλγόριθμό σας, αναλύστε την ορθότητα του αλγόριθμου, την χρονική πολυπλοκότητα και πολυπλοκότητα μηνυμάτων. Αποδείξτε τους ισχυρισμούς σας.

3^o Θέμα [30%]

Θεωρείστε ένα σύγχρονο κατανεμημένο σύστημα με n διεργασίες συνδεδεμένες μέσω ενός γενικού δικτύου, μη-κατευθυνόμενου δικτύου με m κανάλια επικοινωνίας, όπου κάθε διεργασία έχει μια μοναδική ταυτότητα αλλά δεν γνωρίζει το σύνολο των διεργασιών, ούτε την τοπολογία του δικτύου. Προτείνετε μια αλγοριθμική λύση που να επιτρέπει σε μια διεργασία u₀ να εντοπίσει την διεργασία με τον μέγιστο αριθμό γειτόνων (αν είναι περισσότερες από μια, εντοπίζει αυτή με την μικρότερη ταυτότητα). Περιγράψτε τον αλγόριθμό σας, αναλύστε την ορθότητα του αλγόριθμου, την χρονική πολυπλοκότητα και πολυπλοκότητα μηνυμάτων. Αποδείξτε τους ισχυρισμούς σας.

Ως αλγοριθμική λύση θεωρούμε είτε έναν αλγόριθμο (από την βιβλιογραφία) είτε μια συλλογή αλγορίθμων (από την βιβλιογραφία) είτε έναν νέο αλγόριθμο. Κατά την περιγραφή της πρότασης σας, αναφέρετε ξεκάθαρα όποιες επιπλέον υποθέσεις πρέπει να γίνουν ως προς τον τρόπο λειτουργίας του συστήματος πέρα από αυτές που αναφέρονται σε κάθε ερώτημα.

1^o Θέμα [40%]

Θεωρείστε ένα σύγχρονο κατανεμημένο σύστημα με n διεργασίες συνδεδεμένες μέσω ενός γενικού, μη-κατευθυνόμενου δικτύου με m κανάλια επικοινωνίας. Οι διεργασίες έχουν μια μοναδική ταυτότητα, δεν γνωρίζουν το σύνολο των διεργασιών, ούτε την τοπολογία του δικτύου. Κάθε διεργασία u δέχεται ως είσοδο έναν ακέραιο αριθμό i_u. Προτείνετε μια αλγοριθμική λύση που να επιτρέπει στη διεργασία u₀ να υπολογίσει τον μέγιστο αριθμό από αυτούς που έχουν δοθεί στις διεργασίες. Ο αλγόριθμος πρέπει να χρησιμοποιεί σταθερού μεγέθους μνήμη (μερικά bit). Περιγράψτε τον αλγόριθμό σας, αναλύστε την ορθότητα του αλγόριθμου, την χρονική πολυπλοκότητα και πολυπλοκότητα μηνυμάτων. Αποδείξτε τους ισχυρισμούς σας.

2^o Θέμα [30%]

Για τον αλγόριθμο LCR

1. Ορίστε μια διάταξη ταυτοτήτων τέτοια ώστε η εκτέλεση του αλγορίθμου να προκαλέσει την ανταλλαγή Ω(n²) μηνυμάτων.
2. Ορίστε μια διάταξη ταυτοτήτων τέτοια ώστε η εκτέλεση του αλγορίθμου να προκαλέσει την ανταλλαγή O(n) μηνυμάτων.
3. Δείξετε ότι το πλήθος των μηνυμάτων που ανταλλάσσονται από την εκτέλεση του αλγορίθμου κατά μέση τιμή, είναι O(n log n), όπου η μέση τιμή προκύπτει από όλες τις πιθανές διατάξεις ταυτοτήτων, θεωρώντας τες ισοπίθανες.

3^o Θέμα [30%]

Θεωρείστε ένα ασύγχρονο κατανεμημένο σύστημα με n διεργασίες συνδεδεμένες μέσω ενός δικτύου γραμμής. Οι διεργασίες μπορούν να ξεχωρίσουν τον δεξιό γείτονα τους από τον αριστερό και γνωρίζουν αν είναι στις άκρες του δικτύου. Κάθε διεργασία u δέχεται ως είσοδο έναν ακέραιο αριθμό i_u και έχει σταθερού μεγέθους μνήμη. Προτείνετε μια αλγοριθμική λύση που να ταξινομεί τους αριθμούς μεταξύ των διεργασιών, όπου κάθε διεργασία u θα δίνει έξοδο έναν ακέραιο αριθμό $o_u$ και το σύνολο τιμών εξόδου είναι ίσο με το σύνολο τιμών εισόδου και o₁≤...≤o_n. Περιγράψτε τον αλγόριθμό σας, αναλύστε την ορθότητα του αλγόριθμου, την χρονική πολυπλοκότητα και πολυπλοκότητα μηνυμάτων. Αποδείξτε τους ισχυρισμούς σας.

Ως αλγοριθμική λύση θεωρούμε είτε έναν αλγόριθμο (από την βιβλιογραφία) είτε μια συλλογή αλγορίθμων (από την βιβλιογραφία) είτε έναν νέο αλγόριθμο. Κατά την περιγραφή της πρότασης σας, αναφέρετε ξεκάθαρα όποιες επιπλέον υποθέσεις πρέπει να γίνουν ως προς τον τρόπο λειτουργίας του συστήματος πέρα από αυτές που αναφέρονται σε κάθε ερώτημα.

Ο τελικός βαθμός υπολογίζεται με τον ακόλουθο τύπο:

(Βαθμός 1ης άσκησης) x 0.15 + (Βαθμός 2ης άσκησης) x 0.15 + (Σύνολο Σωστών Ερ. Διαλ.) x 0.2 + (Σύνολο Σωστών Εργαστ.) x 0.75 + (Βαθμός Εξέτασης) x 0.7

Η στρογγυλοποιήση γίνεται στο τέλος, στο πλησιέστερο (προς τα πάνω, δηλ. υπέρ του φοιτητή) μισό ή ολόκληρο βαθμό.