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

Από DistrSys

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


Παράδοση:

  • Η άσκηση είναι ατομική
  • Η παράδοση γίνεται με την χρήση του εργαλείου submit-ds
  • Η προθεσμία υποβολής είναι η Δευτέρα 21 Ιανουαρίου 2008, ώρα 23:59
  • Σε περίπτωση που η άσκηση παραδοθεί με καθυστέρηση θα υπάρξει μείωση βαθμού (10% ανά 24 ώρες)
  • Σε περίπτωση που εντοπιστεί αντιγραφή, η άσκηση θα μηδενιστεί


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


Απαντήσεις:


Βαθμολογία:

 ΑΜ   Ονοματεπώνυμο   Βαθμός 
 2803  Κανελλόπουλος Βασίλης  8 
 2861  Κόλιας Βασίλειος  9 
 2880  Λυκοκανέλλος Φιλοποίμην  9 
 2946  Σιώκης Απόστολος  10 
 2953  Σπυρώνης Ιωάννης  4.5 
 2980  Χαρίση Ευνομία  7.5 
 3000  Καναβός Ανδρέας  6 
 3003  Τόκης Θεόδωρος  5.5 
 3016  Κονδύλης Θεόδωρος – Στυλιανός  8 
 3027  Δημόπουλος Κωνσταντίνος  8 
 3033  Λαδάς Αλέξανδρος  3 
 3050  Ακριβόπουλος Ορέστης  7 
 3055  Αναστασίου Δημήτριος  6.5 
 3061  Βασιλάκης Νικόλαος  8.5 
 3067  Βλαχογιάννη Μαρία-Όλγα  10 
 3068  Βονιτσάνου Μαρία-Αλεξάνδρα  8 
 3072  Γερακιός Κώστας  10 
 3091  Δομένικου Αικατερίνη  8 
 3092  Δούβρης Αριστείδης  5 
 3095  Ζαγγανά Ελένη  8 
 3102  Καλοφωλιάς Γιάννης  8.5 
 3119  Κίσσα Μαρία  6 
 3126  Κόρδαρης Ιωάννης  9.5 
 3128  Κουκουλέτσος Δημήτρης  6 
 3132  Κουτσουπιά Μαργαρίτα  8 
 3149  Μαρίνος Ηλίας  7.5 
 3179  Ντάσιος Βαγγέλης  5 
 3186  Παπαπαναγιώτου Βασίλης  10 
 3202  Πουλημένος Προκόπιος  8 
 3204  Πυργέλης Απόστολος  10 
 3221  Σταμάτης Απόστολος  10 
 3223  Στάμου Σπύρος  9 
 3236  Τσώτας Σωτήριος  6.5 
 3248  Χατζηπρίμου Κλεοπάτρα  6.5 
 3251  Ανδρέου Ανδρέας  8 
 3253  Ηλιάδης Σωκράτης  9 
 3255  Σαββίδης Γρηγόρης  8.5 
 3256  Πασχαλίδης Χαράλαμπος  9 
 3257  Δημοσθένους Γιώργος  8 
 3275  Γεωργίου Δημήτριος  7.5 
 3278  Οικονόμου Γεώργιος  5.5 
 3280  Λογαράς Μάριος  6.5 
 3305  Πίκουλας Γρηγόριος  8 
 3312  Ιωαννίδης Ιωάννης  10 
 3316  Κουτσουρίδης Χάρης  8 
 3343  Αντωνίου Μαρία  7 
 3352  Γεροσταμούλος Αθανάσιος  6 
 3371  Ευσταθίου Διονύσης  9 
 3376  Θηραιού Μαρία-Ειρήνη  8.5 
 3385  Καλοφωλιάς Βασίλης  8 
 3408  Κουρνούτου Μαρία  8 
 3424  Λούκας Ανδρέας  9.5 
 3447  Μπούσης Δημήτρης  8 
 3451  Νάφας Αλέξανδρος  8 
 3471  Πατλάκας Ιωάννης  9 
 3476  Πουλοκέφαλος Νικόλαος  10 
 3488  Σπύρου Δήμητρα  7 
 3507  Τσολάκος Λάμπρος  10 
 3531  Μαλλιαρός Φραγκίσκος  8 
 3544  Βούρκος Ανδρέας  10 
 3545  Αντωνίου Αθανάσιος  10 
 3552  Μάρκου Μάριος  7 
 3555  Πιερής Χρίστος  7 
 3581  Σέχου Αουρέλα  9 
Ανακτήθηκε από το "http://www.ceid.upatras.gr/courses/katanemhmena/wiki/index.php/2007-2008:%CE%9A%CE%B1%CF%84%CE%B1%CE%BD%CE%B5%CE%BC%CE%B7%CE%BC%CE%AD%CE%BD%CE%B1_%CE%A3%CF%85%CF%83%CF%84%CE%AE%CE%BC%CE%B1%CF%84%CE%B1_%CE%99:%CE%91%CF%83%CE%BA%CE%AE%CF%83%CE%B5%CE%B9%CF%82:2%CE%B7_%CE%86%CF%83%CE%BA%CE%B7%CF%83%CE%B7".