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

Από DistrSys

Πίνακας περιεχομένων

1η άσκηση (Δευτέρα, 5 Νοεμβρίου 2007)

1o Πρόβλημα
Ο αλγόριθμος FloodMax είναι σχεδιασμένος για γενικά δίκτυα, επομένως μπορεί να εφαρμοστεί και σε δίκτυα δακτυλίου.
  1. Συγκρίνετε την συμπεριφορά του αλγόριθμου FloodMax με αυτή του αλγόριθμου LCR. Ποιά είναι η βασική διαφορά?
  2. Θεωρείστε τον αλγόριθμο OptFloodMax όπου οι διεργασίες εκπέμπουν την μέγιστη_ταυτότητα μόνο αν έχει αλλάξει κατά τον προηγούμενο γύρο (δηλ. δεν στέλνουν τον ίδιο κωδικό δύο φορές). Τι επίπτωση έχει αυτό στην συμπεριφορά του αλγόριθμου σε δίκτυα δακτυλίου?
2o Πρόβλημα
Θεωρείστε ένα σύγχρονο κατανεμημένο σύστημα με n διεργασίες συνδεδεμένες μέσω ενός γενικού, μη-κατευθυνόμενου δικτύου με m κανάλια επικοινωνίας, όπου κάθε διεργασία έχει μια μοναδική ταυτότητα αλλά δεν γνωρίζει το σύνολο των διεργασιών, ούτε την τοπολογία του δικτύου. Κάθε διεργασία u δέχεται ως είσοδο έναν ακέραιο αριθμό iu. Σχεδιάστε έναν κατανεμημένο αλγόριθμο που επιτρέπει σε όλες τις διεργασίες να υπολογίσουν την διάμεση τιμή (median) όλων των αριθμών από αυτούς που έχουν δοθεί. Αναλύστε την χρονική πολυπλοκότητα και πολυπλοκότητα μηνυμάτων. Αποδείξτε τους ισχυρισμούς σας.
3o Πρόβλημα
Θεωρείστε ένα σύγχρονο κατανεμημένο σύστημα με n διεργασίες συνδεδεμένες μέσω ενός γενικού, μη-κατευθυνόμενου δικτύου με m κανάλια επικοινωνίας, όπου κάθε διεργασία έχει μια μοναδική ταυτότητα αλλά δεν γνωρίζει το σύνολο των διεργασιών, ούτε την τοπολογία του δικτύου. Κάθε διεργασία u δέχεται ως είσοδο έναν ακέραιο αριθμό iu. Σχεδιάστε έναν κατανεμημένο αλγόριθμο που επιτρέπει στη διεργασία u0 να εντοπίσει όλα τα ζεύγη γειτονικών διεργασίων uk, ul όπου ik + il = X (X είναι μια τιμή που έχει δοθεί κατα την εκκίνηση του συστήματος). Αναλύστε την χρονική πολυπλοκότητα και πολυπλοκότητα μηνυμάτων. Αποδείξτε τους ισχυρισμούς σας.


Παράδοση:

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


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


Απαντήσεις:


Βαθμολογία:

 ΑΜ   Ονοματεπώνυμο   Βαθμός 
 2803  Κανελλόπουλος Βασίλης  9.5 
 2861  Κόλιας Βασίλειος  3 
 2880  Λυκοκανέλλος Φιλοποίμην  7.5 
 2946  Σιώκης Απόστολος  10 
 2953  Σπυρώνης Ιωάννης  9 
 2963  Τσαμπίκας Σπυρίδων  7.5 
 2980  Χαρίση Ευνομία  6.5 
 2989  Τζαμπαζης Γιώργος  4 
 3000  Καναβός Ανδρέας  5 
 3003  Τόκης Θεόδωρος  6.5 
 3016  Κονδύλης Θεόδωρος – Στυλιανός  7 
 3027  Δημόπουλος Κωνσταντίνος  7.5 
 3033  Λαδάς Αλέξανδρος  7 
 3042  Φερεντίνου Κωνσταντίνα  8 
 3050  Ακριβόπουλος Ορέστης  7 
 3055  Αναστασίου Δημήτριος  4 
 3061  Βασιλάκης Νικόλαος  9 
 3067  Βλαχογιάννη Μαρία-Όλγα  10 
 3068  Βονιτσάνου Μαρία-Αλεξάνδρα  4 
 3072  Γερακιός Κώστας  9.5 
 3091  Δομένικου Αικατερίνη  9.5 
 3092  Δούβρης Αριστείδης  5 
 3095  Ζαγγανά Ελένη  8 
 3100  Κάιδος Χαράλαμπος  0* 
 3102  Καλοφωλιάς Γιάννης  10 
 3119  Κίσσα Μαρία  4 
 3126  Κόρδαρης Ιωάννης  7.5 
 3128  Κουκουλέτσος Δημήτρης  7 
 3132  Κουτσουπιά Μαργαρίτα  7 
 3138  Λέκκας Αντώνιος  7.5 
 3149  Μαρίνος Ηλίας  8 
 3179  Ντάσιος Βαγγέλης  8 
 3186  Παπαπαναγιώτου Βασίλης  9.5 
 3202  Πουλημένος Προκόπιος  9 
 3204  Πυργέλης Απόστολος  9 
 3221  Σταμάτης Απόστολος  9.5 
 3223  Στάμου Σπύρος  10 
 3236  Τσώτας Σωτήριος  7 
 3248  Χατζηπρίμου Κλεοπάτρα  5 
 3251  Ανδρέου Ανδρέας  8 
 3253  Ηλιάδης Σωκράτης  9 
 3255  Σαββίδης Γρηγόρης  7.5 
 3256  Πασχαλίδης Χαράλαμπος  9 
 3257  Δημοσθένους Γιώργος  6.5 
 3275  Γεωργίου Δημήτριος  7.5 
 3278  Οικονόμου Γεώργιος  7.5 
 3280  Λογαράς Μάριος  9 
 3296  Λιβαθινός Σπύρος  4.5 
 3305  Πίκουλας Γρηγόριος  10 
 3312  Ιωαννίδης Ιωάννης  10 
 3316  Κουτσουρίδης Χάρης  10 
 3328  Γαρδίκης Δημήτρης  0* 
 3343  Αντωνίου Μαρία  7 
 3352  Γεροσταμούλος Αθανάσιος  9.5 
 3371  Ευσταθίου Διονύσης  9.5 
 3376  Θηραιού Μαρία-Ειρήνη  8 
 3385  Καλοφωλιάς Βασίλης  8 
 3408  Κουρνούτου Μαρία  7.5 
 3424  Λούκας Ανδρέας  9.5 
 3447  Μπούσης Δημήτρης  8.5 
 3451  Νάφας Αλέξανδρος  10 
 3471  Πατλάκας Ιωάννης  8 
 3476  Πουλοκέφαλος Νικόλαος  10 
 3488  Σπύρου Δήμητρα  8 
 3507  Τσολάκος Λάμπρος  9.5 
 3531  Μαλλιαρός Φραγκίσκος  10 
 3544  Βούρκος Ανδρέας  7 
 3545  Αντωνίου Αθανάσιος  8 
 3552  Μάρκου Μάριος  9.5 
 3555  Πιερής Χρίστος  10 
 3581  Σέχου Αουρέλα  7.5 
 ????  Λιαροκάπης Μηνάς  6.5 


2η άσκηση (Δευτέρα, 17 Δεκεμβρίου 2007)

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 


Εξέταση Ιανουαρίου (Δευτέρα, 28 Ιανουαρίου 2007)

1o Θέμα [30%]
Θεωρείστε ένα σύγχρονο κατανεμημένο σύστημα με n διεργασίες συνδεδεμένες μέσω ενός γενικού, μη-κατευθυνόμενου δικτύου με m κανάλια επικοινωνίας.
  1. Διατυπώστε το πρόβλημα της εκλογής αρχηγού.
  2. Προτείνετε μια αλγοριθμική λύση που να ελαχιστοποιεί τον αριθμό μηνυμάτων που ανταλλάσσουν οι διεργασίες, στην περίπτωση όπου οι διεργασίες δεν έχουν μοναδική ταυτότητα και δεν έχουν πρόσβαση σε κάποια γεννήτρια τυχαίων αριθμών. Αναλύστε την ορθότητα του αλγόριθμου, την χρονική πολυπλοκότητα και την πολυπλοκότητα μηνυμάτων. Αποδείξτε τους ισχυρισμούς σας.
  3. Προτείνετε μια αλγοριθμική λύση που να επιτρέπει την εκλογή δύο αρχηγών, στην περίπτωση όπου οι διεργασίες έχουν μοναδική ταυτότητα. Αναλύστε την ορθότητα του αλγόριθμου, την χρονική πολυπλοκότητα και την πολυπλοκότητα μηνυμάτων. Αποδείξτε τους ισχυρισμούς σας.
Ως αλγοριθμική λύση θεωρούμε είτε έναν αλγόριθμο (από την βιβλιογραφία) είτε μια συλλογή αλγορίθμων (από την βιβλιογραφία) είτε έναν νέο αλγόριθμο. Κατά την περιγραφή της πρότασης σας, αναφέρετε ξεκάθαρα όποιες επιπλέον υποθέσεις πρέπει να γίνουν ως προς τον τρόπο λειτουργίας του συστήματος πέρα από αυτές που αναφέρονται σε κάθε ερώτημα.
2o Θέμα [35%]
Θεωρείστε ένα ασύγχρονο κατανεμημένο σύστημα με n διεργασίες συνδεδεμένες μέσω ενός δικτύου γραμμής. Οι διεργασίες μπορούν να ξεχωρίσουν τον δεξιό γείτονα τους από τον αριστερό και γνωρίζουν αν είναι στις άκρες του δικτύου. Κάθε διεργασία u δέχεται ως είσοδο έναν ακέραιο αριθμό iu και έχει σταθερού μεγέθους μνήμη. Προτείνετε μια αλγοριθμική λύση που να ταξινομεί τους αριθμούς μεταξύ των διεργασιών, όπου κάθε διεργασία u θα δίνει έξοδο έναν ακέραιο αριθμό ou και το σύνολο τιμών εξόδου είναι ίσο με το σύνολο τιμών εισόδου και o1 ≤ ... ≤ on. Προσπαθήστε να σχεδιάσετε τον πιο αποδοτικό αλγόριθμο ως προς την χρονική πολυπλοκότητα και πολυπλοκότητα μηνυμάτων. Αναλύστε την ορθότητα του αλγόριθμου και αποδείξτε τους ισχυρισμούς σας.
3o Θέμα [35%]
Θεωρείστε ένα σύγχρονο κατανεμημένο σύστημα με n διεργασίες συνδεδεμένες μέσω ενός γενικού δικτύου. Κάθε διεργασία έχει μια μοναδική ταυτότητα και δεν γνωρίζει το σύνολο των διεργασιών ή την τοπολογία του δικτύου. Σχεδιάστε έναν όσο το δυνατόν αποδοτικότερο αλγόριθμο για την κατασκευή ενός επικαλυπτικού δέντρου ελαχίστου-ύψους. Ορίστε τις ιδιότητες του αλγόριθμου σας και αναλύστε την ορθότητά του, καθώς και την χρονική πολυπλοκότητα και πολυπλοκότητα μηνυμάτων. Αποδείξτε τους ισχυρισμούς σας.


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


Βαθμολογία:

 ΑΜ   Ονοματεπώνυμο   Βαθμός 
 2861  Κόλιας Βασίλειος  4.5 
 2880  Λυκοκανέλλος Φιλοποίμην  5.5 
 2946  Σιώκης Απόστολος  8.5 
 2953  Σπυρώνης Ιωάννης  5 
 2980  Χαρίση Ευνομία  6 
 2989  Τζαμπαζης Γιώργος  6 
 3000  Καναβός Ανδρέας  5.5 
 3003  Τόκης Θεόδωρος  6 
 3007  Γερούτης Γεώργιος  2 
 3027  Δημόπουλος Κωνσταντίνος  9.5 
 3033  Λαδάς Αλέξανδρος  5 
 3050  Ακριβόπουλος Ορέστης  7 
 3055  Αναστασίου Δημήτριος  6 
 3061  Βασιλάκης Νικόλαος  8 
 3067  Βλαχογιάννη Μαρία-Όλγα  8 
 3068  Βονιτσάνου Μαρία-Αλεξάνδρα  6 
 3072  Γερακιός Κώστας  9.5 
 3091  Δομένικου Αικατερίνη  6.5 
 3092  Δούβρης Αριστείδης  6 
 3095  Ζαγγανά Ελένη  5.5 
 3102  Καλοφωλιάς Γιάννης  8.5 
 3119  Κίσσα Μαρία  6 
 3126  Κόρδαρης Ιωάννης  6 
 3128  Κουκουλέτσος Δημήτρης  8 
 3132  Κουτσουπιά Μαργαρίτα  7 
 3149  Μαρίνος Ηλίας  7.5 
 3179  Ντάσιος Βαγγέλης  5.5 
 3186  Παπαπαναγιώτου Βασίλης  9.5 
 3202  Πουλημένος Προκόπιος  7.5 
 3204  Πυργέλης Απόστολος  6.5 
 3221  Σταμάτης Απόστολος  9 
 3223  Στάμου Σπύρος  8 
 3236  Τσώτας Σωτήριος  6 
 3248  Χατζηπρίμου Κλεοπάτρα  5.5 
 3251  Ανδρέου Ανδρέας  8.5 
 3253  Ηλιάδης Σωκράτης  6.5 
 3255  Σαββίδης Γρηγόρης  7.5 
 3256  Πασχαλίδης Χαράλαμπος  8.5 
 3257  Δημοσθένους Γιώργος  5.5 
 3275  Γεωργίου Δημήτριος  6 
 3278  Οικονόμου Γεώργιος  7.5 
 3296  Λιβαθινός Σπύρος  3 
 3305  Πίκουλας Γρηγόριος  7 
 3312  Ιωαννίδης Ιωάννης  7 
 3316  Κουτσουρίδης Χάρης  8.5 
 3343  Αντωνίου Μαρία  7.5 
 3352  Γεροσταμούλος Αθανάσιος  9 
 3371  Ευσταθίου Διονύσης  9.5 
 3376  Θηραιού Μαρία-Ειρήνη  8 
 3385  Καλοφωλιάς Βασίλης  9.5 
 3408  Κουρνούτου Μαρία  6.5 
 3424  Λούκας Ανδρέας  10 
 3447  Μπούσης Δημήτρης  3 
 3451  Νάφας Αλέξανδρος  8.5 
 3476  Πουλοκέφαλος Νικόλαος  8 
 3488  Σπύρου Δήμητρα  9 
 3507  Τσολάκος Λάμπρος  5 
 3531  Μαλλιαρός Φραγκίσκος  9 
 3544  Βούρκος Ανδρέας  9.5 
 3545  Αντωνίου Αθανάσιος  7.5 
 3552  Μάρκου Μάριος  7.5 
 3555  Πιερής Χρίστος  5.5 


Εξέταση Σεπτεμβρίου (???)

1o Θέμα [35%]
Θεωρείστε ένα σύγχρονο κατανεμημένο σύστημα με n διεργασίες συνδεδεμένες μέσω ενός γενικού δικτύου. Κάθε διεργασία έχει μια μοναδική ταυτότητα και δεν γνωρίζει το σύνολο των διεργασιών ή την τοπολογία του δικτύου. Σχεδιάστε έναν όσο το δυνατόν αποδοτικότερο αλγόριθμο για την κατασκευή ενός επικαλυπτικού δέντρου αναζήτησης κατα βάθος. Ορίστε τις ιδιότητες του αλγόριθμου σας και αναλύστε την ορθότητά του, καθώς και την χρονική πολυπλοκότητα και πολυπλοκότητα μηνυμάτων. Αποδείξτε τους ισχυρισμούς σας.
2o Θέμα [35%]
Θεωρείστε ένα σύγχρονο κατανεμημένο σύστημα με n διεργασίες συνδεδεμένες μέσω ενός γενικού, μη-κατευθυνόμενου δικτύου με m κανάλια επικοινωνίας, όπου κάθε διεργασία έχει μια μοναδική ταυτότητα αλλά δεν γνωρίζει το σύνολο των διεργασιών, ούτε την τοπολογία του δικτύου. Προτείνετε μια αλγοριθμική λύση που να υπολογίζει τον συνολικό αριθμό των διεργασιών. Περιγράψτε τον αλγόριθμό σας, αναλύστε την ορθότητα του αλγόριθμου, την χρονική πολυπλοκότητα και πολυπλοκότητα μηνυμάτων. Αποδείξτε τους ισχυρισμούς σας.
3o Θέμα [30%]
Θεωρείστε ένα σύγχρονο κατανεμημένο σύστημα με n διεργασίες συνδεδεμένες μέσω ενός πλήρως συνδεδεμένου δικτύου. Κάθε διεργασία έχει μια μοναδική ταυτότητα και δεν γνωρίζει το σύνολο των διεργασιών ή την τοπολογία του δικτύου. Έστω ότι κατά την εκτέλεση του συστήματος προκύπτουν σφάλματα επανεκκίνησης στις διεργασίες. Σχεδιάστε έναν όσο το δυνατόν αποδοτικότερο αλγόριθμο για τον αμοιβαίο αποκλεισμό που να είναι ανεκτικός στα σφάλματα επανεκκίνησης. Ορίστε τις ιδιότητες του αλγόριθμου σας και αναλύστε την ορθότητά του, καθώς και την χρονική πολυπλοκότητα και πολυπλοκότητα μηνυμάτων. Αποδείξτε τους ισχυρισμούς σας.


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


Βαθμολογία:

 ΑΜ   Ονοματεπώνυμο   Βαθμός 
 2803  Κανελλόπουλος Βασίλης  8.5 
 3016  Κονδύλης Θεόδωρος – Στυλιανός  10 
 3447  Μπούσης Δημήτρης  10 


Τελικός Βαθμός

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

(Βαθμός 1ης άσκησης) x 0.15 + (Βαθμός 2ης άσκησης) x 0.15 + (Σύνολο Σωστών Ερ. Διαλ.) x 0.2 + (Σύνολο Σωστών Εργαστ.) x 0.75 + (Βαθμός Εξέτασης) x 0.7

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


Βαθμολογία:

 ΑΜ   Ονοματεπώνυμο   1η Άσκηση   2η Άσκηση   Ερ.Διαλ.   Εργαστ.   Εξέταση   Βαθμός 
 2803  Κανελλόπουλος Βασίλης   9.5  8  4   3   8.5   10 
 2861  Κόλιας Βασίλειος   3  9  0   3   4.5   7 
 2880  Λυκοκανέλλος Φιλοποίμην   7.5  9  2   3   5.5   9 
 2946  Σιώκης Απόστολος   10  10  6   3   8.5   10 
 2953  Σπυρώνης Ιωάννης   9  4.5  1   3   5   8 
 2980  Χαρίση Ευνομία   6.5  7.5  0   2   6   8 
 2989  Τζαμπαζης Γιώργος   4  0  0   0   6   5 
 3000  Καναβός Ανδρέας   5  6  0   3   5.5   8 
 3003  Τόκης Θεόδωρος   6.5  5.5  0   3   6   8.5 
 3016  Κονδύλης Θεόδωρος – Στυλιανός   7  8  0   3   10   10 
 3027  Δημόπουλος Κωνσταντίνος   7.5  8  3   0   9.5   9.5 
 3033  Λαδάς Αλέξανδρος   7  3  0   0   5   5 
 3050  Ακριβόπουλος Ορέστης   7  7  2   3   7   9.5 
 3055  Αναστασίου Δημήτριος   4  6.5  0   3   6   8 
 3061  Βασιλάκης Νικόλαος   9  8.5  0   2   8   9.5 
 3067  Βλαχογιάννη Μαρία-Όλγα   10  10  3   3   8   10 
 3068  Βονιτσάνου Μαρία-Αλεξάνδρα   4  8  0   3   6   8.5 
 3072  Γερακιός Κώστας   9.5  10  4   3   9.5   10 
 3091  Δομένικου Αικατερίνη   9.5  8  5   3   6.5   10 
 3092  Δούβρης Αριστείδης   5  5  1   3   6   8 
 3095  Ζαγγανά Ελένη   8  8  4   3   5.5   9.5 
 3102  Καλοφωλιάς Γιάννης   10  8.5  1   2   8.5   10 
 3119  Κίσσα Μαρία   4  6  0   3   6   8 
 3126  Κόρδαρης Ιωάννης   7.5  9.5  0   1   6   7.5 
 3128  Κουκουλέτσος Δημήτρης   7  6  2   0   8   8 
 3132  Κουτσουπιά Μαργαρίτα   7  8  0   0   7   7 
 3149  Μαρίνος Ηλίας   8  7.5  3   3   7.5   10 
 3179  Ντάσιος Βαγγέλης   8  5  1   3   5.5   8.5 
 3186  Παπαπαναγιώτου Βασίλης   9.5  10  4   3   9.5   10 
 3202  Πουλημένος Προκόπιος   9  8  4   3   7.5   10 
 3204  Πυργέλης Απόστολος   9  10  0   3   6.5   9.5 
 3221  Σταμάτης Απόστολος   9.5  10  5   3   9   10 
 3223  Στάμου Σπύρος   10  9  4   3   8   10 
 3236  Τσώτας Σωτήριος   7  6.5  2   3   6   9 
 3248  Χατζηπρίμου Κλεοπάτρα   5  6.5  0   2   5.5   7 
 3251  Ανδρέου Ανδρέας   8  8  6   2   8.5   10 
 3253  Ηλιάδης Σωκράτης   9  9  4   2   6.5   9.5 
 3255  Σαββίδης Γρηγόρης   7.5  8.5  5   2   7.5   10 
 3256  Πασχαλίδης Χαράλαμπος   9  9  6   3   8.5   10 
 3257  Δημοσθένους Γιώργος   6.5  8  5   3   5.5   9.5 
 3275  Γεωργίου Δημήτριος   7.5  7.5  1   3   6   9 
 3278  Οικονόμου Γεώργιος   7.5  5.5  3   3   7.5   10 
 3280  Λογαράς Μάριος   9  6.5  6   3   *   10 
 3305  Πίκουλας Γρηγόριος   10  8  4   3   7   10 
 3312  Ιωαννίδης Ιωάννης   10  10  3   2   7   10 
 3316  Κουτσουρίδης Χάρης   10  8  4   1   8.5   10 
 3343  Αντωνίου Μαρία   7  7  0   2   7.5   9 
 3352  Γεροσταμούλος Αθανάσιος   9.5  6  3   3   9   10 
 3371  Ευσταθίου Διονύσης   9.5  9  3   3   9.5   10 
 3376  Θηραιού Μαρία-Ειρήνη   8  8.5  2   3   8   10 
 3385  Καλοφωλιάς Βασίλης   8  8  5   3   9.5   10 
 3408  Κουρνούτου Μαρία   7.5  8  0   1   6.5   7.5 
 3424  Λούκας Ανδρέας   9.5  9.5  3   3   10   10 
 3447  Μπούσης Δημήτρης   8.5  8  2   3   10   10 
 3451  Νάφας Αλέξανδρος   10  8  4   3   8.5   10 
 3471  Πατλάκας Ιωάννης   8  9  7   3   *   10 
 3476  Πουλοκέφαλος Νικόλαος   10  10  3   3   8   10 
 3488  Σπύρου Δήμητρα   8  7  3   2   9   10 
 3507  Τσολάκος Λάμπρος   9.5  10  3   3   5   9.5 
 3531  Μαλλιαρός Φραγκίσκος   10  8  7   3   9   10 
 3544  Βούρκος Ανδρέας   7  10  5   3   9.5   10 
 3545  Αντωνίου Αθανάσιος   8  10  7   3   7.5   10 
 3552  Μάρκου Μάριος   9.5  7  7   3   7.5   10 
 3555  Πιερής Χρίστος   10  7  1   3   5.5   9 
 3581  Σέχου Αουρέλα   7.5  9  7   3   *   10 
Ανακτήθηκε από το "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".