Κατανεμημένα Συστήματα — Σεπτέμβριος 2021¶
Μεταγραφή από τις φωτογραφίες IMG_0235, IMG_0234, IMG_0233, IMG_0232 και IMG_0236 (σελίδες 1/5 έως 5/5) της εξέτασης· η IMG_0237 είναι δεύτερη φωτογραφία της σελίδας 2/5.
IMG_0235.jpg¶
Ερώτηση 1 / 5 (Ελεύθερου Κειμένου — 1 βαθμός)
Εξηγείστε περιληπτικά την χρονική πολυπλοκότητα του αλγορίθμου LCR
Σε σύγχρονο κατανεμημένο σύστημα
Σημείωση: η φωτογραφία περιέχει απαντήσεις φοιτητή στο πεδίο κειμένου.
IMG_0234.jpg¶
Ερώτηση 2 / 5 (Ελεύθερου Κειμένου — 1 βαθμός)
Εξηγείστε περιληπτικά την πολυπλοκότητα επικοινωνίας του αλγορίθμου SynchBFS
Σε σύγχρονο κατανεμημένο σύστημα
Σημείωση: η φωτογραφία περιέχει απαντήσεις φοιτητή στο πεδίο κειμένου.
IMG_0233.jpg¶
Ερώτηση 3 / 5 (Ελεύθερου Κειμένου — 1 βαθμός)
εριγράψτε τον αλγόριθμο LCR
[Λείπει από τη φωτογραφία: το αρχικό γράμμα της εντολής, κομμένο στο αριστερό άκρο]
Σημείωση: η φωτογραφία περιέχει απαντήσεις φοιτητή στο πεδίο κειμένου.
IMG_0232.jpg¶
Ερώτηση 4 / 5 (Ελεύθερου Κειμένου — 1 βαθμός)
Εξηγείστε περιληπτικά την πολυπλοκότητα επικοινωνίας του αλγορίθμου HS
Σε σύγχρονο κατανεμημένο σύστημα
Σημείωση: η φωτογραφία περιέχει απαντήσεις φοιτητή στο πεδίο κειμένου.
IMG_0236.jpg¶
Ερώτηση 5 / 5 (Ελεύθερου Κειμένου — 1 βαθμός)
Εξηγείστε περιληπτικά την χρονική πολυπλοκότητα του αλγορίθμου FloodMax
Σε σύγχρονο κατανεμημένο σύστημα
Σημείωση: η φωτογραφία περιέχει απαντήσεις φοιτητή στο πεδίο κειμένου.
Επιπλέον πηγές χωρίς μεταγραφή εδώ (λύσεις →
2021-09.solutions.md, ή διπλότυπες φωτογραφίες της ίδιας σελίδας):IMG_0237.jpg
Λύσεις (⚪ AI, μη επαληθευμένο)
Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (deepseek-flash), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο
Προσοχή
Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.
AI λύσεις — 2021-09¶
Οι λύσεις γράφτηκαν από μοντέλα AI και δεν έχουν ελεγχθεί από άνθρωπο. Η αρίθμηση ακολουθεί το αρχείο θεμάτων.
Θέμα 1¶
Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή
Ο LCR σε δακτύλιο \(n\) κόμβων είναι σύγχρονος: σε κάθε γύρο ένα ID μπορεί να προχωρήσει το πολύ μία θέση. Το μέγιστο ID χρειάζεται το πολύ \(n\) βήματα για να διατρέξει όλο τον δακτύλιο και να επιστρέψει στον κόμβο προέλευσής του, ο οποίος και εκλέγεται. Άρα η χρονική πολυπλοκότητα είναι \(O(n)\) γύροι (χειρότερη περίπτωση \(\Theta(n)\))· μικρότερα IDs εξαλείφονται νωρίτερα όταν συναντήσουν μεγαλύτερο.
Θέμα 2¶
Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή
Ο SynchBFS, ξεκινώντας από μία ρίζα, στέλνει μηνύματα αναζήτησης μόνο όταν ένας κόμβος επιλέγει για πρώτη φορά γονέα και προωθεί το πολύ μία φορά προς κάθε γείτονα (ή σταθερό αριθμό μηνυμάτων ανά ακμή). Επομένως η επικοινωνιακή πολυπλοκότητα είναι \(O(m)\), όπου \(m=|E|\) είναι το πλήθος των ακμών του γράφου· για συνδεδεμένο γράφο ισχύει και \(O(n+m)=O(m)\), αφού \(m\ge n-1\).
Θέμα 3¶
Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή
Ο LCR είναι αλγόριθμος εκλογής αρχηγού σε μονόδρομο δακτύλιο με μοναδικά αναγνωριστικά. Κάθε κόμβος στέλνει αρχικά το δικό του ID στον επόμενο κόμβο του δακτυλίου. Όταν ένας κόμβος λάβει ένα ID \(x\): - αν \(x\) είναι μεγαλύτερο από το δικό του ID, το προωθεί στον επόμενο κόμβο, - αν \(x\) είναι μικρότερο από το δικό του ID, το απορρίπτει, - αν \(x\) είναι ίσο με το δικό του ID, τότε το ID του έχει διατρέξει όλο τον δακτύλιο χωρίς να έχει εξαλειφθεί, άρα ο κόμβος αυτός εκλέγεται αρχηγός.
Το μέγιστο ID είναι το μόνο που μπορεί να διατρέξει ολόκληρο τον δακτύλιο· κάθε μικρότερο ID σταματά όταν συναντήσει μεγαλύτερο. Ισοδύναμα, κάθε κόμβος μπορεί να κρατά το μέγιστο ID που έχει δει και να προωθεί μόνο νέο μέγιστο.
Θέμα 4¶
Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή
Ο HS (Hirschberg–Sinclair) εκτελεί φάσεις με αποστάσεις \(1,2,4,\ldots\) σε αμφίδρομο δακτύλιο. Σε κάθε φάση οι ενεργοί υποψήφιοι στέλνουν το ID τους και προς τις δύο κατευθύνσεις μέχρι την καθορισμένη απόσταση και επιβιώνει μόνο το ID που είναι μέγιστο στη γειτονιά του εύρους αυτού. Επειδή σε κάθε φάση οι ενεργοί υποψήφιοι αραιώνουν κατά σταθερό παράγοντα, το σύνολο των μηνυμάτων ανά φάση είναι \(O(n)\) και υπάρχουν \(O(\log n)\) φάσεις. Άρα η επικοινωνιακή πολυπλοκότητα είναι \(O(n\log n)\) μηνύματα (χειρότερη περίπτωση \(\Theta(n\log n)\)).
Θέμα 5¶
Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή
Στον FloodMax κάθε κόμβος διατηρεί το μέγιστο ID που γνωρίζει και σε κάθε γύρο το ανταλλάσσει με τους γείτονές του. Το μέγιστο ID διαδίδεται μία ακμή ανά γύρο, άρα χρειάζεται χρόνο ανάλογο της διαμέτρου \(D\) του γράφου: \(O(D)\) γύροι. Επειδή \(D\le n-1\), η συνήθης ασφαλής εκδοχή που εκτελείται για \(n-1\) ή \(n\) γύρους έχει χρονική πολυπλοκότητα \(O(n)\) (χειρότερη περίπτωση \(\Theta(n)\)), ενώ αν η \(D\) είναι γνωστή μπορεί να σταματήσει σε \(O(D)\) γύρους.