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

Από DistrSys

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
• Σε περίπτωση που εντοπιστεί αντιγραφή, η άσκηση θα μηδενιστεί

Σχετικό υλικό:

• Εκφώνηση άσκησης σε μορφή PDF
• Μοντέλο Σύγχρονων Συστημάτων απο τις σημειώσεις του μαθήματος
• Εκλογή Αρχηγού απο τις σημειώσεις του μαθήματος
• Κατανεμημένες Δομές απο τις σημειώσεις του μαθήματος
• Συναίνεση απο τις σημειώσεις του μαθήματος

Απαντήσεις:

ΑΜ   Βαθμός   1   2   3   4   5   3744   3   0.6   0.6   0.6   0.6   0.6   3897   3   0.6   0.6   0.6   0.6   0.6   3912   1.6   0.4   0.4      0.6   0.2   3936   1.8   0.6   0.6      0.6      3939   3   0.6   0.6   0.6   0.6   0.6   3948   2.8   0.6   0.6   0.6   0.6   0.4   4038   2.4   0.6   0.6   0.6   0.6      4101   1.5   0.5      0.1   0.5   0.4   4122   1.5   0.4   0.4      0.4   0.3   4152   2.2   0.6   0.6      0.6   0.4   4156   3   0.6   0.6   0.6   0.6   0.6   4159   0.8   0.2   0.2      0.2   0.2   4163   2.8   0.6   0.6   0.4   0.6   0.6   4165   3   0.6   0.6   0.6   0.6   0.6   4166   1.4   0.4   0.3      0.3   0.4   4181   2.3   0.6   0.6      0.6   0.5   4192   2.8   0.6   0.6   0.6   0.6   0.4   4209   2.2   0.6   0.6      0.6   0.4   4211   1   0.3   0.3      0.3   0.1   4235   2.4   0.6   0.6      0.6   0.6   4245   2.2   0.4   0.4   0.6   0.4   0.4   4249   2.7   0.5   0.5   0.6   0.5   0.6   4252   1.5   0.4   0.4      0.4   0.3   4260   3   0.6   0.6   0.6   0.6   0.6   4265   1.6   0.3   0.5   0.2   0.3   0.3   4266                     4287   2   0.6   0.6      0.6   0.2   4299   2.1   0.5   0.5   0.3   0.3   0.5   4308   3   0.6   0.6   0.6   0.6   0.6   4309   3   0.6   0.6   0.6   0.6   0.6   4310   2.5   0.6   0.5   0.6   0.6   0.2   4311   2.6   0.6   0.6   0.6   0.4   0.4   4314   3   0.6   0.6   0.6   0.6   0.6   4327   1.5   0.6   0.6         0.3   4334   2   0.5   0.5      0.5   0.5   4346   3   0.6   0.6   0.6   0.6   0.6   4352   3   0.6   0.6   0.6   0.6   0.6   4355   0.3   0.1            0.2   4363   3   0.6   0.6   0.6   0.6   0.6   4370   1   0.4   0.6            4381   3   0.6   0.6   0.6   0.6   0.6   4383   2   0.4   0.4      0.6   0.6   4390   2.7   0.6   0.6   0.5   0.6   0.4   4433   2   0.5   0.4   0.5   0.4   0.2   4503   2   0.6   0.4      0.6   0.4   4511   3   0.6   0.6   0.6   0.6   0.6   4512   1.8   0.5   0.5      0.5   0.3   4517   1.7   0.5   0.5      0.5   0.2   4525   0.3   0.1            0.2   4528   0.9   0.2   0.3   0.4         4552   1.6   0.6   0.6      0.4      4583   2.2   0.6   0.6      0.6   0.4   4585   1.2      0.5      0.4   0.3   4586   2.2   0.6   0.6      0.6   0.4   4592   2.1   0.5   0.6      0.6   0.4   4596   1.3   0.4   0.2   0.2   0.2   0.3   4605   2.5   0.5   0.5   0.6   0.6   0.3   4611   0.7   0.3      0.4         4620   2.8   0.6   0.6   0.6   0.6   0.4   4622   2.4   0.6   0.6   0.6      0.6   4625   1.4   0.2   0.2   0.2   0.2   0.6   4649   1.2   0.4         0.4   0.4   4657   0.5      0.3      0.2      4669   2.3   0.6   0.6   0.3   0.4   0.4