Κατανεμημένα Συστήματα — Φεβρουάριος 2023¶

Μεταγραφή από τις φωτογραφίες IMG_4248 (σελίδα 1/2) και IMG_4249 (σελίδα 2/2) της γραπτής εξέτασης.

IMG_4248.png¶

Θέμα 1 (ΣΛ) (2μ.) Φλεβ. 2023

[ ] Ασθενής αλγόριθμος σημαίνει ότι μπορεί να εφαρμοστεί σε μεγάλο εύρος πιθανών δικτύων.
[ ] Ο αλγόριθμος FloodSet χρησιμοποιείται για την επίλυση του προβλήματος "επικύρωση δοσοληψιών".
[ ] Βυζαντινά σφάλματα σημαίνει ότι τα κανάλια επικοινωνίας παραποιούν τα μηνύματα.
[ ] Για να ελέγξουμε την κατάσταση ενός συστήματος μία χρονική στιγμή, μπορούμε να σταματήσουμε προσωρινά την εκτέλεση των διεργασιών και να ελέγξουμε την κατάσταση της κάθε μίας.

Θέμα 2 (1μ.)

Σχεδιάστε τις τοπολογίες : γραμμή, δακτύλιο, δέντρο, πλήρη, αστέρας.

Θέμα 3 (3,5μ.)

Σχεδιάστε αλγόριθμο για ασύγχρονο σύστημα με τοπολογία γραμμής που εκλέγει μοναδικό αρχηγό. Δώστε πολυπλοκότητα επικοινωνίας και χρονική πολυπλοκότητα. Οι διεργ. έχουν μοναδικό ID (UID), δεν γνωρίζουν τον αριθμό \(n\) των διεργ. γνωρίζουν όμως τον αριστερό και δεξιό γείτονά τους στο δίκτυο.

IMG_4249.png¶

Θέμα 4 (3,5μ.)

Έχουμε ένα σύγχρονο σύστημα με διεργασίες και κάθε διεργασία έχει έναν μετρητή θερμοκρασίας. Μπορούν να συμβούν το πολύ \(f\) σφάλματα. Έχουμε τοπολογία κλίκας (πλήρες δίκτυο). Οι διεργασίες έχουν μία αρχική τιμή θερμοκρασίας και πρέπει να υπολογιστεί ο μέσος όρος της θερμοκρασίας (η μέση θερμοκρασία). Να σχεδιάσετε αλγόριθμο που κάθε διεργ. να υπολογίζει τον μέσο όρο της θερμοκρασίας και να εγγυάται ότι ικανοποιούνται οι συνθήκες : εγκυρότητα, συμφωνία, τερματισμός. Οι διεργασίες έχουν μοναδικά IDs (UID).

\(\downarrow\)

Αν όλες οι διεργ. έχουν αρχική τιμή \(v\), θα είναι \(v\) η κοινή έξοδος που θα δώσουν όλες οι μη-εσφαλμένες διεργ.

Λύσεις (⚪ AI, μη επαληθευμένο)

Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (antigravity-gemini, deepseek-flash, gemini-3.7-flash), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο

Προσοχή

Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.

AI λύσεις — 2023-02¶

Οι λύσεις γράφτηκαν από μοντέλα AI και δεν έχουν ελεγχθεί από άνθρωπο. Η αρίθμηση ακολουθεί το αρχείο θεμάτων.

Θέμα 1¶

Αξιοπιστία: 2 από 3 ανεξάρτητες λύσεις συμφωνούν (η άλλη διαφωνούσε) · εμπιστοσύνη λύτη: μέτρια

Λάθος. Το ότι ένας αλγόριθμος εφαρμόζεται σε ευρύ φάσμα δικτύων είναι ιδιότητα γενικότητας/robustness και όχι ο ορισμός του «ασθενούς» αλγορίθμου.
Λάθος. Ο FloodSet είναι αλγόριθμος βυζαντινής συμφωνίας (Byzantine agreement) σε σύγχρονο πλήρες δίκτυο, όχι αλγόριθμος επικύρωσης δοσοληψιών.
Λάθος. Τα βυζαντινά σφάλματα αφορούν διεργασίες που μπορούν να συμπεριφερθούν αυθαίρετα/κακόβουλα· δεν σημαίνουν απλώς ότι τα κανάλια παραποιούν μηνύματα.
Λάθος. Δεν αρκεί να «παγώσουμε» ανεξάρτητα τις διεργασίες για να πάρουμε συνεπή καθολική κατάσταση· χρειάζεται αλγόριθμος snapshot (π.χ. Chandy–Lamport), ώστε να ληφθεί συνεπής τομή και να ληφθούν υπόψη και μηνύματα εν πτήσει.

Θέμα 2¶

Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή

Γραμμή: \(1-2-3-4-5\) (κάθε κόμβος συνδέεται μόνο με τους γειτονικούς του).
Δακτύλιος: \(1-2-3-4-5-1\) (κύκλος, η ακμή \(5-1\) κλείνει τον δακτύλιο).

Δέντρο: π.χ.

Πλήρες: \(K_5\), δηλαδή όλες οι δυνατές ακμές μεταξύ διαφορετικών κόμβων· για \(5\) κόμβους συνδέονται όλα τα ζεύγη.
Αστέρας: κέντρο ο \(1\) και φύλλα οι \(2,3,4,5\):
```
      2
      |
3 --- 1 --- 4
      |
      5
```

Θέμα 3¶

Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή

Έστω γραμμή \(p_1-p_2-\cdots-p_n\), όπου \(p_1\) είναι το αριστερό άκρο (δεν έχει αριστερό γείτονα) και \(p_n\) το δεξί άκρο (δεν έχει δεξιό γείτονα). Τα άκρα αναγνωρίζονται τοπικά από την απουσία γείτονα· δεν χρειάζεται γνώση του \(n\).

Αλγόριθμος εκλογής αρχηγού:

Φάση υποψηφιότητας: Το δεξί άκρο \(p_n\) στέλνει προς τα αριστερά μήνυμα \(\langle CAND, m\rangle\) με \(m=ID_n\). Κάθε ενδιάμεσος \(p_i\) που λαμβάνει \(\langle CAND,m\rangle\) από δεξιά θέτει [ m\leftarrow \max(m,ID_i) ] και το προωθεί προς τα αριστερά. Όταν το λάβει το αριστερό άκρο \(p_1\), θέτει [ M=\max(m,ID_1), ] το οποίο είναι το μέγιστο UID όλων των διεργασιών.
Φάση ανακοίνωσης: Το \(p_1\) στέλνει προς τα δεξιά μήνυμα \(\langle LEADER,M\rangle\). Κάθε κόμβος που το λαμβάνει θέτει ως αρχηγό τη διεργασία με UID \(M\) και το προωθεί προς τα δεξιά. Έτσι όλοι καταλήγουν στον μοναδικό αρχηγό \(p_M\).

Πολυπλοκότητα επικοινωνίας: \(n-1\) μηνύματα στη φάση CAND και \(n-1\) στη φάση LEADER, άρα [ 2n-2=O(n). ] Χρονική πολυπλοκότητα: \(n-1\) βήματα μετάδοσης για το CAND και \(n-1\) για το LEADER, άρα \(O(n)\) διαδοχικές μεταδόσεις μηνυμάτων. Δεν απαιτείται γνώση του \(n\).

Θέμα 4¶

Αξιοπιστία: 2 από 3 ανεξάρτητες λύσεις συμφωνούν (η άλλη διαφωνούσε) · εμπιστοσύνη λύτη: μέτρια

Παραδοχή: Θεωρώ σύγχρονο σύστημα, πλήρες δίκτυο, αξιόπιστα κανάλια, έως \(f\) βυζαντινά σφάλματα και \(n>3f\), όπως απαιτείται για ντετερμινιστική βυζαντινή συμφωνία χωρίς υπογραφές. Αν \(n\le 3f\), το πρόβλημα δεν λύνεται γενικά με τις κλασικές υποθέσεις.

Αλγόριθμος:

Για κάθε διεργασία \(j\), εκτελούμε μία παράλληλη εκτέλεση βυζαντινής συμφωνίας (π.χ. FloodSet / oral messages \(f+1\) γύρων) με αρχική τιμή την θερμοκρασία \(x_j\) της \(j\). Έτσι κάθε σωστή διεργασία καταλήγει στο ίδιο διάνυσμα [ a=(a_1,\dots,a_n), ] όπου για κάθε σωστή \(j\) ισχύει \(a_j=x_j\). Για εσφαλμένες \(j\), το \(a_j\) μπορεί να είναι αυθαίρετο, αλλά είναι το ίδιο σε όλες τις σωστές διεργασίες.
Ταξινομούμε τις τιμές \(a_1,\dots,a_n\) σε αύξουσα σειρά: [ a_{(1)}\le a_{(2)}\le\cdots\le a_{(n)}. ]
Αφαιρούμε τις \(f\) μικρότερες και τις \(f\) μεγαλύτερες και υπολογίζουμε τον μέσο όρο των υπόλοιπων \(n-2f\) τιμών: [ \bar a=\frac{1}{n-2f}\sum_{k=f+1}^{n-f} a_{(k)}. ] Κάθε σωστή διεργασία επιστρέφει το \(\bar a\).

Ιδιότητες:

Τερματισμός: Η βυζαντινή συμφωνία τερματίζει σε πεπερασμένο αριθμό γύρων (\(f+1\)), και η ταξινόμηση/μέσος όρος είναι τοπικός υπολογισμός.
Συμφωνία: Όλες οι σωστές διεργασίες καταλήγουν στο ίδιο διάνυσμα \(a\), άρα υπολογίζουν το ίδιο \(\bar a\).
Εγκυρότητα: Αν όλες οι σωστές διεργασίες έχουν αρχική τιμή \(v\), τότε τουλάχιστον \(n-f\) από τις \(a_j\) είναι ίσες με \(v\). Το πολύ \(f\) τιμές διαφέρουν από το \(v\). Αφαιρώντας τις \(f\) μικρότερες και τις \(f\) μεγαλύτερες, όλες οι τιμές που διαφέρουν από το \(v\) απορρίπτονται ως ακραίες (είτε είναι μικρότερες είτε μεγαλύτερες από \(v\)). Άρα οι εναπομείναντες \(n-2f\) τιμές είναι όλες \(v\), οπότε \(\bar a=v\).

Σημείωση: Αν ως «μέσος όρος» απαιτείται ο ακριβής αριθμητικός μέσος των αρχικών τιμών μόνο των μη-εσφαλμένων για κάθε βυζαντινή εκτέλεση, αυτό είναι αδύνατο: ένας βυζαντινός κόμβος μπορεί να στείλει ακριβώς τα μηνύματα που θα έστελνε ένας σωστός κόμβος με άλλη θερμοκρασία, οπότε δύο εκτελέσεις με ίδιο transcript απαιτούν διαφορετικό αποτέλεσμα. Ο παραπάνω αλγόριθμος δίνει τον καθιερωμένο fault-tolerant μέσο (trimmed mean) και ικανοποιεί τις τρεις ζητούμενες συνθήκες. Αν τα σφάλματα είναι απλώς crash failures, τότε μετά από συμφωνία στο σύνολο των ενεργών διεργασιών μπορεί να υπολογιστεί και ο ακριβής μέσος όρος των ενεργών.

✔ Επιβεβαίωσε · ✖ Βρήκα λάθος

✖ Βρήκα λάθος στη μεταγραφή