Από DistrSys
Στη σελίδα αυτή θα αναρτηθεί το υλικό που αφορά τις ασκήσεις και την βαθμολογία του μαθήματος.
1η άσκηση (Δευτέρα, 12 Δεκεμβρίου 2011)
- 1o Πρόβλημα
- Θεωρείστε ένα σύγχρονο κατανεμημένο σύστημα με n διεργασίες συνδεδεμένες μέσω ενός δικτύου δακτυλίου διπλής κατεύθυνσης. Κάθε διεργασία έχει μια μοναδική ταυτότητα και δεν γνωρίζει το σύνολο των διεργασιών. Κατά την διάρκεια εκτέλεσης του συστήματος παρατηρούνται σφάλματά επικοινωνίας. Σε κάθε εκτέλεση το πολύ σ αποστολές μηνυμάτων μπορεί να αποτύχουν. Σχεδιάστε έναν αλγόριθμο εκλογής αρχηγού. Ορίστε τις ιδιότητες του αλγόριθμου σας και αναλύστε την ορθότητά του, καθώς και την χρονική πολυπλοκότητα και πολυπλοκότητα μηνυμάτων. Αποδείξτε τους ισχυρισμούς σας.
- 2o Πρόβλημα
- Θεωρείστε ένα σύγχρονο κατανεμημένο σύστημα με n διεργασίες συνδεδεμένες μέσω ενός γενικού δικτύου, όπου κάθε διεργασία έχει μια μοναδική ταυτότητα και γνωρίζει τη διάμετρο του δικτύου. Κάθε διεργασία u δέχεται ως είσοδο έναν ακέραιο αριθμό iu από το σύνολο S, δηλ. iu∈S. Κατά την διάρκεια εκτέλεσης του συστήματος παρατηρούνται σφάλματά τερματισμού. Σε κάθε εκτέλεση το πολύ σ διεργασίες μπορεί να αποτύχουν. Τροποποιήστε τον αλγόριθμο συναίνεσης FloodSet έτσι ώστε να λειτουργεί σωστά σε οποιαδήποτε τοπολογία. Αναλύστε την ορθότητα, χρονική πολυπλοκότητα και πολυπλοκότητα μηνυμάτων. Αποδείξτε τους ισχυρισμούς σας.
- 3o Πρόβλημα
- Θεωρείστε ένα σύγχρονο κατανεμημένο σύστημα με n διεργασίες συνδεδεμένες μέσω ενός γενικού δικτύου, όπου κάθε διεργασία έχει μια μοναδική ταυτότητα και δεν γνωρίζει τη δομή του δικτύου. Κάθε διεργασία u δέχεται ως είσοδο έναν ακέραιο αριθμό iu. Σχεδιάστε έναν κατανεμημένο αλγόριθμο που επιτρέπει σε κάθε διεργασία u να εντοπίσει την ux και uy, όπου ix≤iu και iy≥iu. Η διεργασία umax (δηλ. με max(i)) εντοπίζει ως uy την διεργασία umin (δηλ. με min(i)). Η διεργασία umin εντοπίζει ως ux την διεργασία umax. Αναλύστε την ορθότητα, χρονική πολυπλοκότητα και πολυπλοκότητα μηνυμάτων. Αποδείξτε τους ισχυρισμούς σας.
- 4o Πρόβλημα
- Θεωρείστε ένα σύγχρονο κατανεμημένο σύστημα με n διεργασίες συνδεδεμένες μέσω ενός γενικού δικτύου, όπου κάθε διεργασία έχει μια μοναδική ταυτότητα και δεν γνωρίζει τη δομή του δικτύου. Κάθε διεργασία u δέχεται ως είσοδο έναν ακέραιο αριθμό iu. Σχεδιάστε έναν κατανεμημένο αλγόριθμο που επιτρέπει στην διεργασία u0 να εντοπίσει την γειτονία διεργασιών με το μεγαλύτερο άθροισμα. Αναλύστε την ορθότητα, χρονική πολυπλοκότητα και πολυπλοκότητα μηνυμάτων. Αποδείξτε τους ισχυρισμούς σας.
|
Παράδοση:
- Η άσκηση είναι ατομική
- Η παράδοση γίνεται με την χρήση του εργαλείου submit-ds
- Η προθεσμία υποβολής είναι η
Δευτέρα 9 Ιανουαρίου, ώρα 13:00 Δευτέρα 16 Ιανουαρίου, ώρα 23:59
- Σε περίπτωση που εντοπιστεί αντιγραφή, η άσκηση θα μηδενιστεί
Σχετικό υλικό:
2η άσκηση (Δευτέρα, 9 Ιανουαρίου 2011)
- 1o Πρόβλημα
- Θεωρείστε ένα σύγχρονο κατανεμημένο σύστημα με n διεργασίες συνδεδεμένες διεργασίες συνδεδεμένες μέσω ενός γενικού, μη-κατευθυνόμενου δικτύου με m κανάλια επικοινωνίας. Κάθε διεργασία έχει μια μοναδική ταυτότητα και δεν γνωρίζει το σύνολο των διεργασιών, ούτε την τοπολογία του δικτύου. Σχεδιάστε έναν κατανεμημένο αλγόριθμο που επιτρέπει στη διεργασία u0 να υπολογίσει τη διάμετρο του δικτύου. Ορίστε τις ιδιότητες του αλγόριθμου σας και αναλύστε την ορθότητά του, καθώς και την χρονική πολυπλοκότητα και πολυπλοκότητα μηνυμάτων. Αποδείξτε τους ισχυρισμούς σας.
- 2o Πρόβλημα
- Θεωρείστε ένα σύγχρονο κατανεμημένο σύστημα με n διεργασίες συνδεδεμένες μέσω ενός γενικού, μη-κατευθυνόμενου δικτύου με m κανάλια επικοινωνίας, όπου κάθε διεργασία έχει μια μοναδική ταυτότητα αλλά δεν γνωρίζει το σύνολο των διεργασιών, ούτε την τοπολογία του δικτύου. Κάθε διεργασία u δέχεται ως είσοδο έναν ακέραιο αριθμό iu. Σχεδιάστε έναν κατανεμημένο αλγόριθμο που επιτρέπει σε όλες τις διεργασίες
- (α) να υπολογίσουν τον μέσο όρο όλων των αριθμών από αυτούς που έχουν δοθεί (Σu=1n iu / n) και
- (β) να υπολογίσουν την διάμεση τιμή (median) όλων των αριθμών από αυτούς που έχουν δοθεί.
- Αναλύστε την ορθότητα, χρονική πολυπλοκότητα και πολυπλοκότητα μηνυμάτων. Αποδείξτε τους ισχυρισμούς σας.
- 3o Πρόβλημα
- Θεωρείστε ένα σύγχρονο κατανεμημένο σύστημα με n διεργασίες συνδεδεμένες μέσω ενός πλήρως συνδεδεμένου δικτύου, όπου κάθε διεργασία έχει μια μοναδική ταυτότητα και γνωρίζει τη δομή του δικτύου. Έστω ότι κατά την εκτέλεση του συστήματος προκύπτουν ε σφάλματα επανεκκίνησης στις διεργασίες. Σχεδιάστε έναν αλγόριθμο για το πρόβλημα του k-αμοιβαίου αποκλεισμού (δηλ. το πολύ k διεργασίες μπορούν να εκτελούν ταυτόχρονα στο κρίσιμο τμήμα) που να είναι ανεκτικός στα σφάλματα επανεκκίνησης. Αναλύστε την ορθότητα, χρονική πολυπλοκότητα και πολυπλοκότητα μηνυμάτων. Αποδείξτε τους ισχυρισμούς σας.
- 4o Πρόβλημα
- Θεωρείστε ένα σύγχρονο κατανεμημένο σύστημα με n διεργασίες συνδεδεμένες μέσω ενός γενικού, μη-κατευθυνόμενου δικτύου με m κανάλια επικοινωνίας, όπου κάθε διεργασία έχει μια μοναδική ταυτότητα αλλά δεν γνωρίζει το σύνολο των διεργασιών, ούτε την τοπολογία του δικτύου. Κάθε διεργασία u δέχεται ως είσοδο έναν ακέραιο αριθμό iu. Σχεδιάστε έναν κατανεμημένο αλγόριθμο που επιτρέπει στη διεργασία u0 να εντοπίσει όλα τα ζεύγη γειτονικών διεργασίων uk, ul όπου ik + il = X (X είναι μια τιμή που έχει δοθεί κατα την εκκίνηση του συστήματος). Αναλύστε την χρονική πολυπλοκότητα και πολυπλοκότητα μηνυμάτων. Αποδείξτε τους ισχυρισμούς σας.
- 5o Πρόβλημα
- Θεωρείστε ένα σύγχρονο κατανεμημένο σύστημα με n διεργασίες συνδεδεμένες μέσω ενός γενικού, μη-κατευθυνόμενου δικτύου με m κανάλια επικοινωνίας.
- (α) Διατυπώστε το πρόβλημα της εκλογής αρχηγού.
- (β) Προτείνετε μια αλγοριθμική λύση που να ελαχιστοποιεί τον αριθμό μηνυμάτων που ανταλλάσσουν οι διεργασίες, στην περίπτωση όπου οι διεργασίες δεν έχουν μοναδική ταυτότητα και δεν έχουν πρόσβαση σε κάποια γεννήτρια τυχαίων αριθμών. Αναλύστε την ορθότητα του αλγόριθμου, την χρονική πολυπλοκότητα και την πολυπλοκότητα μηνυμάτων. Αποδείξτε τους ισχυρισμούς σας.
- (γ) Προτείνετε μια αλγοριθμική λύση που να επιτρέπει την εκλογή δύο αρχηγών, στην περίπτωση όπου οι διεργασίες έχουν μοναδική ταυτότητα. Αναλύστε την ορθότητα του αλγόριθμου, την χρονική πολυπλοκότητα και την πολυπλοκότητα μηνυμάτων. Αποδείξτε τους ισχυρισμούς σας.
|
Παράδοση:
- Η άσκηση είναι ατομική
- Η παράδοση γίνεται με την χρήση του εργαλείου submit-ds
- Η προθεσμία υποβολής είναι η Σάββατο 10 Μαρτίου, ώρα 23:59
- Σε περίπτωση που εντοπιστεί αντιγραφή, η άσκηση θα μηδενιστεί
Σχετικό υλικό:
