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

1^o Πρόβλημα

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

2^o Πρόβλημα

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

3^o Πρόβλημα

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

1^o Πρόβλημα

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

2^o Πρόβλημα

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

3^o Πρόβλημα

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

1^o Πρόβλημα

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

2^o Πρόβλημα

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

3^o Πρόβλημα

Υλοποιείστε στο σύστημα Shawn έναν αλγόριθμο βασισμένο στον BFS ο οποίος να δέχεται δύο παραμέτρους: AM και MSGS. Οι διεργασίες για τις οποίες ισχύει id%AM==0 (όπου id η ταυτότητα της κάθε διεργασίας και AM το τελευταίο ψηφίο του ΑΜ σας + 1) πρέπει να στείλουν στην διεργασία 0 ένα πλήθος από MSGS μηνύματα. Κάθε μήνυμα περιέχει ένα τυχαίο ακέραιο. Η διεργασία 0 συλλέγει όλα τα μηνύματα και υπολογίζει το άθροισμα. Μελετήστε την συμπεριφορά του αλγόριθμου στις τοπολογίες που σας έχουν δωθεί. Μετρήστε την χρονική πολυπλοκότητα και πολυπλοκότητα επικοινωνίας του αλγορίθμου όταν MSGS=5. Σχολιάστε την συμπεριφορά του αλγορίθμου.

1^o Πρόβλημα

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

2^o Πρόβλημα

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

3^o Πρόβλημα

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

1^o Πρόβλημα

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

2^o Πρόβλημα

Υλοποιείστε στο σύστημα Shawn που να δέχεται μία παράμετρο: AM (το τελευταίο ψηφίο του ΑΜ σας + 1). Οι διεργασίες του συστήματος δέχονται σαν είσοδο μια τιμή i (π.χ., έχουν πρόσβαση σε κάποιο αισθητήρα). Ο αλγόριθμος που θα υλοποιήσετε θα πρέπει να μπορεί να αποτιμά τα καθολικά κατηγορήματα:

(α) ∃q • i_q%AM=9,

(β) ∄q • i_q%2=1,

(γ) ∀q • i_q%2=0 : ∃v • i_q+i_v>10.

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

1^o Πρόβλημα

Με βάση το μοντέλο πρωτόκολλων πλυθησμών, απαντήστε στα ακόλουθα ερωτήματα:

1. Έστω ο εξής εναλλακτικός ορισμός της δικαιοσύνης: "Όλες οι αλληλεπιδράσεις συμβαίνουν απέιρως συχνά". Επάγεται απο αυτόν τον ορισμό το ίδιο αποτέλεσμα με τον ορισμό της δικαιοσύνης που ορίσαμε? Αν ναι, εξηγείστε τους ισχυρισμούς σας. Αν όχι, δώστε αντιπαράδειγμα. Δώστε παράδειγμα δίκαιης εκτέλεσης όπου κάποια αλληλεπίδραση δεν συμβαίνει ποτέ. (Υπόδειξη: Χρησιμοποιείστε το leader election σε ένα πολύ απλό δίκτυο).
2. Δώστε πρωτόκολλο υπολογισμού του κατηγορήματος: "Υπάρχει ζυγός αριθμός κόμβων με είσοδο 1;" όταν το αλφάβητο εισόδου είναι Χ={0,1} -- δηλαδή κάθε πράκτορας να δίνει τελικά έξοδο '1' όταν ο αριθμός των '1' στην είσοδο είναι ζυγός και έξοδο '0' στην αντίθετη περίπτωση. (Υπόδειξη: Χρησιμοποιείστε την ιδέα του live bit όπως αυτή παρουσιάστηκε στην Διαφάνεια 49).

2^o Πρόβλημα

Υλοποιείστε στο σύστημα Shawn τον σταθεροποιούμενο αλγόριθμο αμοιβαίου αποκλεισμού του Dijkstra για τοπολογίες δακτυλίου. Κατά την εκτέλεση του συστήματος, στον γύρο 3×δ, οι διεργασίες όπου id%AM==0 (το τελευταίο ψηφίο του AM σας + 1) λόγο σφαλμάτων αποκτούν μια τυχαία τιμή στην εσωτερική μεταβλητή του αλγορίθμου (στο διάστημα 0...k). Μελετήστε την συμπεριφορά του αλγόριθμου στις τοπολογίες που σας έχουν δοθεί. Μετρήστε τον χρόνο σταθεροποίησης του αλγορίθμου. Σχολιάστε την συμπεριφορά του αλγορίθμου.

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

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

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