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

1^o Πρόβλημα

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

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

2^o Πρόβλημα

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

3^o Πρόβλημα

Ο αλγόριθμος FloodMax είναι σχεδιασμένος για γενικά δίκτυα, επομένως μπορεί να εφαρμοστεί και σε δίκτυα δακτυλίου.

1. Συγκρίνετε την συμπεριφορά του αλγόριθμου FloodMax με αυτή του αλγόριθμου LCR. Ποιά είναι η βασική διαφορά?
2. Θεωρείστε τον αλγόριθμο OptFloodMax όπου οι διεργασίες εκπέμπουν την μέγιστη_ταυτότητα μόνο αν έχει αλλάξει κατά τον προηγούμενο γύρο (δηλ. δεν στέλνουν τον ίδιο κωδικό δύο φορές). Τι επίπτωση έχει αυτό στην συμπεριφορά του αλγόριθμου σε δίκτυα δακτυλίου?

1^o Πρόβλημα

Αποδείξτε την ορθότητα του αλγόριθμου SyncBFS.

2^o Πρόβλημα

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

3^o Πρόβλημα

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

1^o Πρόβλημα

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

2^o Πρόβλημα

Θεωρείστε ένα σύγχρονο κατανεμημένο σύστημα με n διεργασίες συνδεδεμένες μέσω ενός γενικού, μη-κατευθυνόμενου, πλήρως συνδεδεμένου δικτύου, όπου κάθε διεργασία γνωρίζει τη δομή του δικτύου. Κάθε διεργασία u δέχεται ως είσοδο μία τιμή i_u από το σύνολο S, δηλ. i_u ∈ S. Σχεδιάστε έναν αλγόριθμο για το πρόβλημα της k-συναίνεσης, δηλ. ο αριθμός των διαφορετικών αποφάσεων είναι το πολύ k (|S|>k,|o|=k). Έστω ότι κατά την εκτέλεση του αλγόριθμου προκύπτουν σ σφάλματα τερματισμού. Αναλύστε την ορθότητα του αλγόριθμου, την χρονική πολυπλοκότητα και την πολυπλοκότητα μηνυμάτων. Αποδείξτε τους ισχυρισμούς σας.

3^o Πρόβλημα

Υλοποιείστε τον αλγόριθμο FloodMax στο σύστημα Shawn. Μελετήστε την συμπεριφορά του αλγόριθμου στις τοπολογίες που σας έχουν δωθεί. Μετρήστε την χρονική πολυπλοκότητα και πολυπλοκότητα επικοινωνίας του αλγορίθμου. Σχολιάστε την συμπεριφορά του αλγορίθμου.

1^o Πρόβλημα

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

1. Αν κάποια διεργασία βρίσκεται στην κατάσταση k₁ ή "έτοιμη", τότε οι αρχικές τιμές όλων των διεργασιών είναι "ναι",
2. Αν κάποια διεργασία βρίσκεται στην κατάσταση k₀, τότε καμία διεργασία δεν είναι στην κατάσταση k₁ και καμία ενεργή διεργασία δεν είναι στην κατάσταση "έτοιμη",
3. Αν κάποια διεργασία βρίσκεται στην κατάσταση k₁, τότε καμία διεργασία δεν είναι στην κατάσταση k₀, και καμία ενεργή διεργασία δεν είναι στην κατάσταση "άγνωστη".

2^o Πρόβλημα

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

3^o Πρόβλημα

Οι διεργασίες του συστήματος δέχονται σαν είσοδο μια τιμή (π.χ., έχουν πρόσβαση σε κάποιο αισθητήρα). Υλοποιείστε έναν αλγόριθμο που θα επιτρέπει στην διεργασία 0 να υπολογίσει την ελάχιστη τιμή που υπάρχει στο δίκτυο, την μέγιστη τιμη, τον μέσο όρο και το σύνολο. Η υλοποίηση του αλγορίθμου σας πρέπει να γίνει στο σύστημα Shawn. Μελετήστε την συμπεριφορά του αλγόριθμου στις τοπολογίες που σας έχουν δωθεί. Μετρήστε την χρονική πολυπλοκότητα και πολυπλοκότητα επικοινωνίας του αλγορίθμου. Σχολιάστε την συμπεριφορά του αλγορίθμου.

1^o Πρόβλημα

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

2^o Πρόβλημα

Οι διεργασίες του συστήματος δέχονται σαν είσοδο μια τιμή (π.χ., έχουν πρόσβαση σε κάποιο αισθητήρα). Στην συναίχεια επεξεργάζονται τοπικά την είσοδο και εξάγουν μια απόφαση (π.χ., για τους σκοπούς της άσκησης, i%AM, όπου i η τιμή εισόδου, AM τα 2 τελευταία ψηφία του ΑΜ σας). Χρησιμοποιήστε τον αλγόριθμο συναίνεσης FloodSet που εξετάστηκε στο εργαστήριο του μαθήματος. Μελετήστε τη συμπεριφορά του αλγορίθμου στο σύστημα Shawn όταν παρουσιάζονται σφάλματα επικοινωνίας. Τα σφάλματα επικοινωνίας ορίζονται με πιθανότητα σφάλματος ανά αποστολή μηνύματος p={0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9}. Μετρήστε την χρονική πολυπλοκότητα και πολυπλοκότητα επικοινωνίας του αλγορίθμου στις τοπολογίες που σας έχουν δοθεί έως ότου οι διεργασίες συμφωνήσουν σε μια κοινή τιμή. Σχολιάστε την συμπεριφορά του αλγορίθμου.

3^o Πρόβλημα

Οι διεργασίες του συστήματος έχουν πρόσβαση σε έναν κοινό πόρο. Υλοποιείστε έναν αλγόριθμο αμοιβαίου αποκλεισμού που θα επιτρέπει μόνο σε μια διεργασία να έχει πρόσβαση στον κοινό πόρο σε κάθε γύρο εκτέλεσης του συστήματος. Η υλοποίηση του αλγορίθμου σας πρέπει να γίνει στο σύστημα Shawn. Μελετήστε την συμπεριφορά του αλγόριθμου στις τοπολογίες που σας έχουν δωθεί. Κατά την εκτέλεση του συστήματος θεωρείστε ότι οι διεργασίες όπου id%AM==0 (όπου AM τα 2 τελευταία ψηφία του ΑΜ σας) ζητούν πρόσβαση στον κοινό πόρο τον γύρο που ορίζει η τιμή εισόδου, (π.χ., αν τα δύο τελευταία ψηφία του AM είναι 12, και η διεργασία 48 έχει ως τιμή εισόδου 496, τότε επιθυμεί να εισέλθει στο ΚΤ τον γύρο 496). Μετρήστε τον χρόνο απόκρισης και πολυπλοκότητα επικοινωνίας του αλγορίθμου στις τοπολογίες που σας έχουν δωθεί. Σχολιάστε την συμπεριφορά του αλγορίθμου.

1^o Πρόβλημα

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

2^o Πρόβλημα

Θεωρείστε ένα σύγχρονο κατανεμημένο σύστημα με n διεργασίες συνδεδεμένες μέσω ενός γενικού, μη-κατευθυνόμενου δικτύου με m κανάλια επικοινωνίας, όπου κάθε διεργασία έχει μια μοναδική ταυτότητα αλλά δεν γνωρίζει το σύνολο των διεργασιών, ούτε την τοπολογία του δικτύου. Κάθε διεργασία u δέχεται ως είσοδο μία τιμή i_u από το σύνολο N, δηλ. i_u ∈ N. Σχεδιάστε έναν αλγόριθμο που να αποτιμά τα καθολικά κατηγορήματα: (α) ∃q • i_q=15, (β) ∄q • i_q%2=0, (γ) ∀q • i_q%2=0 : ∃v • i_q+i_v>10. Περιγράψτε τον αλγόριθμό σας, αναλύστε την ορθότητα του αλγόριθμου, την χρονική πολυπλοκότητα και πολυπλοκότητα μηνυμάτων. Αποδείξτε τους ισχυρισμούς σας.

3^o Πρόβλημα

Υλοποιείστε τον σταθεροποιουμενο αλγόριθμο εκλογής αρχηγού που βασίζεται στην τεχνική power supply στο σύστημα Shawn. Μελετήστε την συμπεριφορά του αλγόριθμου στις τοπολογίες που σας έχουν δωθεί. Κατά την εκτέλεση του συστήματος θεωρείστε ότι οι διεργασίες όπου id%AM==0 (όπου AM τα 2 τελευταία ψηφία του ΑΜ σας, αν AM<50 τότε θέστε AM+50) λόγο σφαλμάτων τερματίζουν στον γύρο 3×δ. Μετρήστε τον χρόνο σταθεροποίησης τους αλγόριθμου, δηλ. τον αριθμό γύρων που απαιτείται για να βρεθεί 1 αρχηγός μετά τον γύρο 3×δ. Για την τοπολογία των 1000 κόμβων δώστε γράφημα που να μετράει το πλήθος των αρχηγών που υπάρχουν στο δίκτυο ώς προς τον γύρο εκτέλεσης. Σχολιάστε την συμπεριφορά του αλγορίθμου.

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

(Βαθμός 1ης άσκησης) + (Βαθμός 2ης άσκησης) + (Βαθμός 3ης άσκησης) + (Βαθμός 4ης άσκησης) + (Βαθμός 5ης άσκησης) + (Βαθμός 6ης άσκησης)

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