Κατανεμημένα Συστήματα — Ιανουάριος 2021¶
Μεταγραφή από τη φωτογραφία katanemimena3.png.
katanemimena3.png¶
Ερώτηση 1 / 1 (Ελεύθερου Κειμένου — 1 βαθμός)
Υποθέστε ότι οι διεργασίες ενός σύγχρονου κατανεμημένου συστήματος έχουν μοναδικές ταυτότητες (UIDs), γνωρίζουν ότι είναι συνδεδεμένες σε τοπολογία κατευθυνόμενου δακτυλίου και η κάθε μία γνωρίζει τον εισερχόμενο και τον εξερχόμενο γείτονά της. Το μέγεθος του δακτυλίου \(n\) δεν είναι γνωστό στις διεργασίες. Κάθε διεργασία θέλει να υπολογίσει την τιμή \(n\). Να περιγράψετε (χωρίς ψευδοκώδικα) έναν σύγχρονο κατανεμημένο αλγόριθμο για το πρόβλημα.
Λύσεις (⚪ AI, μη επαληθευμένο)
Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (deepseek-flash), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο
Προσοχή
Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.
AI λύσεις — 2021-01¶
Οι λύσεις γράφτηκαν από μοντέλα AI και δεν έχουν ελεγχθεί από άνθρωπο. Η αρίθμηση ακολουθεί το αρχείο θεμάτων.
Θέμα: Ερώτηση 1 / 1¶
Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή
Ο αλγόριθμος μπορεί να χωριστεί σε τρεις φάσεις.
- Επιλογή συντονιστή (leader) με βάση το UID.
Κάθε διεργασία στέλνει αρχικά το δικό της UID προς τον εξερχόμενο γείτονά της. Όταν μια διεργασία \(P\) λάβει UID \(u\): - αν \(u>\mathrm{UID}(P)\), το προωθεί στον εξερχόμενο γείτονα,
- αν \(u<\mathrm{UID}(P)\), το απορρίπτει,
- αν \(u=\mathrm{UID}(P)\), τότε η \(P\) ανακηρύσσεται συντονιστής.
Επειδή τα UID είναι μοναδικά και ο δακτύλιος είναι πεπερασμένος, μόνο το UID της διεργασίας με το μέγιστο UID θα διασχίσει ολόκληρο τον δακτύλιο και θα επιστρέψει στην αρχική του διεργασία. Κάθε μικρότερο UID θα απορριφθεί από την πρώτη διεργασία με μεγαλύτερο UID, άρα ο συντονιστής είναι μοναδικός και ορθός.
-
Μέτρηση του \(n\) από τον συντονιστή.
Μόλις ο συντονιστής αναγνωρίσει το δικό του UID, στέλνει ειδικό μήνυμα μέτρησης με τιμή \(c=1\), αντιπροσωπεύοντας τον εαυτό του. Κάθε άλλη διεργασία που λαμβάνει το μήνυμα αυξάνει το \(c\) κατά \(1\) και το προωθεί. Όταν το μήνυμα επιστρέψει στον συντονιστή, η τιμή του είναι \(c=n\), αφού έχει περάσει από όλες και μόνο τις \(n\) διεργασίες του δακτυλίου μία φορά. -
Διάδοση του \(n\) σε όλες τις διεργασίες.
Ο συντονιστής στέλνει νέο μήνυμα ανακοίνωσης που περιέχει την τιμή \(n\). Κάθε διεργασία αποθηκεύει το \(n\) και το προωθεί στον εξερχόμενο γείτονα. Όταν το μήνυμα επιστρέψει στον συντονιστή, η ανακοίνωση έχει φτάσει σε όλες τις διεργασίες και ο αλγόριθμος τερματίζει.
Ορθότητα: Το μέγιστο UID είναι μοναδικό, άρα εκλέγεται ένας και μόνο ένας συντονιστής. Το μήνυμα μέτρησης κάνει ακριβώς έναν πλήρη κύκλο, προσμετρώντας όλες τις διεργασίες, άρα επιστρέφει με τιμή \(n\). Η ανακοίνωση κάνει επίσης έναν πλήρη κύκλο, οπότε κάθε διεργασία μαθαίνει τελικά το σωστό \(n\).
Πολυπλοκότητα: Η φάση εκλογής μπορεί να απαιτήσει \(O(n^2)\) μηνύματα στη χειρότερη περίπτωση και \(O(n)\) γύρους σε σύγχρονο περιβάλλον· η μέτρηση και η ανακοίνωση απαιτούν \(O(n)\) μηνύματα και \(O(n)\) γύρους.