Σημειώσεις:Προβλήματα:Διάταξη Γεγονότων

Από DistrSys

Πίνακας περιεχομένων 1 Φυσικά Ρολόγια 1.1 Ακρίβεια ρολογιού 1.2 Συγχρονισμός Φυσικού Ρολογιού 1.3 Αλγόριθμος (Λύση) του Christian 1.4 Λύση των Gusella kai Zatti 1.5 RFC 958: Network Time Protocol (NTP) 2 Λογικός Χρόνος και Αλγόριθμοι Συγχρονισμού 2.1 Η σχέση συνέβη πριν 2.2 Λογικός χρόνος για ασύγχρονα δίκτυα 2.2.1 Συστήματα Αποστολής λήψης 2.2.2 Παράδειγμα Συστήματος αποστολής/λήψης 2.3 Συστήματα Εκπομπής 3 Προσθέτοντας λογικό χρόνο σε ασύγχρονους αλγόριθμους

Φυσικά Ρολόγια

Πολλές φορές, όπως έχουμε ήδη διαπιστώσει, σε ένα κατανεμημένο σύστημα μας είναι πολύ χρήσιμο για να κάνουμε πιο εύκολη την ζωή μας, να έχουμε φυσικό ρολόι σε κάθε κόμβο με σκοπό να εξυπηρετούνται κάποιες λειτουργίες των αλγορίθμων μας όταν απαιτείται κάποια χρονική σειρά σε συγκεκριμένα γεγονότα. Τέτοιες περιπτώσεις είναι το πρόβλημα του συγχρονισμού, το πρόβλημα επικύρωσης δοσοληψιών, το πρόβλημα πιστoποίησης και άλλα.

Γενικά το πρόβλημα στα φυσικά ρολόγια εντοπίζεται στο ότι δεν είναι πάντα διαθέσιμο ένα κεντρικοποιημένο ρολόι με το οποίο σχετικά εύκολα θα μπορούσαν να συγχρονιστούν όλοι μας οι κόμβοι (αν και η ύπαρξη τεχνολογιών όπως GPS δεν κάνει κάτι τέτοιο πλέον όνειρο). Συνεπώς με κάποιο τρόπο εμείς πρέπει να διασφαλίσουμε ότι το ρολόι κάθε κόμβου σε κάποια στιγμή κατά την διάρκεια της εκτέλεσης του συστήματος θα έχει την ίδια τιμή t’. Ιδανικά αυτή η τιμή t’ θα πρέπει να είναι και ίση με την t (t=t’) όπου t η πραγματική ώρα, χωρίς αυτό όμως να επηρεάζει την λειτουργία του συστήματός μας καθώς το πρόβλημα δεν είναι να έχουμε την σωστή ώρα αλλά κάποια κοινή.

Λαμβάνοντας τώρα υπόψη την ανακρίβεια του εκάστοτε hardware του ρολογιού βλέπουμε πως σε επίπεδο λογισμικού η ώρα την στιγμή t είναι:

όπου H(t) είναι η τιμή του φυσικού ρολογιού, α η μονάδα μέτρησης του φυσικού ρολογιού και β η τιμή της ώρας 0, η διόρθωση δηλαδή που έχει γίνει στο ρολόι. Όπως ήδη είπαμε τα ρολόγια δεν είναι τέλεια, δηλαδή σχεδόν ποτέ δεν τυχαίνει να είναι C(t)=H(t).

Ακρίβεια ρολογιού

Όσον αφορά το επίπεδο του υλικού η ακρίβεια ενός ρολογιού μπορεί να δίνεται από δύο μετρικές τον ρυθμό απόκλισης και την διαφορά. Ο ρυθμός απόκλισης (drift) είναι ο ρυθμός με τον οποίο το ρολόι επιβραδύνει η επιταχύνει κατά την μέτρηση του χρόνου. Ένα ιδανικό ρολόι δεν θα αποκλίνει καθόλου. Κάθε άλλο θα πηγαίνει πιο γρήγορα ή πιο αργά, από πολύ έως λίγο. Αυτό μετράει ο ρυθμός απόκλισης. Η διαφορά (skew) δύο ρολογιών C1 και C2 ορίζεται σαν |C1(t) − C2(t)| δηλαδή σαν την απόλυτη τιμή της διαφοράς των τιμών των δύο ρολογιών την χρονική στιγμή t. Αν θέλουμε να δούμε την διαφορά ενός ρολογιού από την πραγματική ώρα προφανώς παίρνουμε|C(t) − Η(t)|.

Συγχρονισμός Φυσικού Ρολογιού

Η ουσία του προβλήματος έγκειται στο πως θα καταφέρουμε στο κατανεμημένο μας σύστημα να διορθώσουμε την ώρα του ρολογιού του εκάστοτε κόμβου έτσι ώστε να είναι σωστή ή καλύτερα να συμβαδίζει με τις ώρες των άλλων κόμβων. Μία λύση θα ήταν ο κάθε κόμβος να λαμβάνει από κάποιον άλλον την ώρα και ανάλογα με τον χρησιμοποιούμενο αλγόριθμο να την διορθώνει κατάλληλα. Σε μία τέτοια περίπτωση αν το ρολόι είχε θετικό ρυθμό απόκλισης τότε θα πρέπει να τοποθετήσει την ώρα του πίσω σε σχέση με αυτή που ήταν. Κάτι τέτοιο θα ήταν προβληματικό. Φανταστείτε ένα σύστημα για το οποίο ξέρουμε ότι έγινε κάποια ενέργεια την χρονική στιγμή Α και ξαφνικά η στιγμή αυτή αποτελεί πλέον το μέλλον. Συνεπώς λοιπόν πρέπει να είμαστε προσεκτικοί με το ποιο στοιχείο του ρολογιού θα πρέπει να αλλάξουμε. Δεν πρέπει λοιπόν αυτό να είναι η τιμή του ρολογιού αυτή καθεαυτή αλλά ο ρυθμός του. Στο παραπάνω παράδειγμα με το ρολόι που επιταχύνει αν μικραίναμε το ρυθμό του κατάλληλα μέσα σε λίγο χρόνο θα είχε την σωστή ώρα χωρίς άλλα προβλήματα. Ο συγχρονισμός ρολογιών μπορεί να είναι εσωτερικός ή εξωτερικός.

Εσωτερικός θεωρείται αν οι κόμβοι – διεργασίες Pu, u={1, . . . , n} είναι συγχρονισμένες μεταξύ τους έτσι ώστε να εξασφαλίζεται για κάθε ζεύγος διεργασιών σε κάθε χρονική στιγμή t θα έχουμε |Cu(t) − Cv (t)| ≤ δ με το δ να είναι η μέγιστη διαφορά των ρολογιών και δ ≥ 0. Προφανώς εδώ δεν υπάρχει εξωτερική πηγή ρολογιού και οι διεργασίες με βάση κάποιον αλγόριθμο συγχρονίζονται από μόνες τους, γι αυτό και εσωτερικός.

Εξωτερικό συγχρονισμό έχουμε όταν οι διεργασίες συγχρονίζονται με ένα εξωτερικό ρολόι Cglobal και συγχρονισμός επιτυγχάνεται όταν για κάθε ζεύγος διεργασιών και οποιαδήποτε χρονική στιγμή t ισχύει |Cu(t) − Cglobal(t)| ≤ δ, με δ ≥ 0. Το δ έχει το ίδιο νόημα με πριν.

Από τους ορισμούς των δύο ειδών συγχρονισμών προκύπτει άμεσα ότι αν σε ένα κατανεμημένο σύστημα έχουμε τις διεργασίες εξωτερικά συγχρονισμένες με διαφορά δ θα είναι ταυτόχρονα και εσωτερικά συγχρονισμένες με διαφορά 2δ. Κάτι αντίστροφο δεν ισχύει, δηλαδή αν γνωρίζουμε ότι οι διεργασίες είναι εσωτερικά συγχρονισμένες δεν μπορούμε να πούμε κάτι για τον εξωτερικό συγχρονισμό τους.

Πριν δούμε κάποιους αλγορίθμους για τον συγχρονισμό φυσικών ρολογιών ας κάνουμε κάποιες παραδοχές-παρατηρήσεις για το πρόβλημα. Πρέπει να έχουμε υπόψη ότι επειδή τα ρολόγια που έχουμε στην διάθεσή μας δεν είναι τέλεια ακόμα και αν τα συγχρονίσουμε μια χρονική στιγμή t, μετά από κάποιο χρόνο, ο οποίος εξαρτάται από το πόσο επιβραδύνει η επιταχύνει το κάθε ρολόι, τα δύο ρολόγια και πάλι θα έχουν διαφορετική ώρα. Συνεπώς ο συγχρονισμός θα είναι μια επαναληπτική διαδικασία και συγκεκριμένα θα πρέπει να συγχρονίσουμε τα τοπικά ρολόγια περιοδικά το λιγότερο κάθε δ/2ρ με δ την μέγιστη διαφορά που θέλουμε να πετύχουμε και ρ την σταθερά ρυθμού απόκλισης των ρολογιών που έχουμε στην διάθεσή μας (την χειρότερη). Είπαμε το λιγότερο καθώς για τον συγχρονισμό των ρολογιών θα τρέχει ένας κατανεμημένος αλγόριθμος, ο οποίος θα περιλαμβάνει αποστολή και λήψη μηνυμάτων κάτι που θα αργεί την όλη διαδικασία. Εξ αιτίας αυτού προφανώς έχουμε και επιπλέον επιβάρυνση του συστήματος με μηνύματα ενώ σοβαρά πρέπει όπως πάντα να λαμβάνεται υπόψη ότι μηνύματα μπορεί να χαθούν άρα συνεπώς να μην επιτευχθεί συγχρονισμός του συστήματος σε κάποια φάση του αλγορίθμου όπου θα έπρεπε να υπήρχε.

Όπως είπαμε και πριν ο εξωτερικός συγχρονισμός απαιτεί την ύπαρξη κάποιου ρολογιού με το οποίο μπορούμε να επικοινωνήσουμε και θα το θεωρούμε αξιόπιστη πηγή. Κάτι τέτοιο μπορεί να γίνει είτε με συστήματα παγκόσμιας γεωγραφικής θέσης (GPS) είτε με ραδιοφάρους. Με τα μεν πρώτα μπορούμε να πάρουμε την παγκόσμια ώρα και με τους ραδιοφάρους την τοπική. Αν στο σύστημά μας έχουμε δυνατότητα επικοινωνίας με τέτοιο ρολόι η κάτι παρεμφερές τότε ο εξωτερικός συγχρονισμός θα ήταν κάτι σχετικά εύκολο για τα τοπικά ρολόγια της κάθε διεργασίας. Σε αρκετές περιπτώσεις όμως κάτι τέτοιο δεν είναι εφικτό είτε λόγω κόστους είτε μεγάλης κατανάλωσης ενέργειας δυσανάλογης με τις συσκευές του κατανεμημένου μας συστήματος είτε λόγω μεγέθους. Ωστόσο κάτι λειτουργικό θα ήταν κάποιες από τις συσκευές του συστήματός μας να είχαν αυτήν την δυνατότητα και οι υπόλοιπες να συγχρονίζονται με βάση αυτές. Κάτι τέτοιο γίνεται στον αλγόριθμο του Christian που ακολουθεί.

Αλγόριθμος (Λύση) του Christian

• Ένα μέρος από τους κόμβους του συστήματος έχουν πρόσβαση σε πηγές ρολογιού που θεωρούνται αξιόπιστες (πχ GPS) και οι υπόλοιπες όχι. Αυτό κάνει το σύστημά μας ετερογενές. Υπάρχει τουλάχιστον 1 τέτοια διεργασία, έστω Pserver.
• Όταν μία διεργασία Pu βρίσκεται σε φάση συγχρονισμού στέλνει μήνυμα synch στην Pserver ρωτώντας την την ώρα. Ταυτόχρονα κρατάει στην μνήμη της την ώρα που έστειλε το μήνυμα (tsend).
• Όταν η διεργασία Pserver απαντήσει με το μήνυμα time(t) που περιέχει την ώρα της, η Pu κρατάει την ώρα που έλαβε το μήνυμα (trcv). Έτσι είναι σε θέση να υπολογίσει τον χρόνο που έκανε το μήνυμα να φτάσει από την στιγμή που έστειλε εκείνη το synch μήνυμα έστω Troundtrip = trcv – tsend. Η Τroundtrip θεωρούμε ότι δεν έχει σημαντικό σφάλμα και πράγματι περιλαμβάνει τον ακριβή χρόνο καθυστέρησης.
• Η διεργασία Pu θέτει την τιμή του ρολογιού της σε t’=tserver+Τroundtrip/2.
• Με αυτόν τον τρόπο επιτυγχάνεται ο συγχρονισμός για κάθε διεργασία. Επιπλέον, η διεργασία μπορεί να υπολογίσει ή ίσως να ξέρει το άνω όριο και το κάτω όριο για τον χρόνο μετάδοσης σε κάθε κανάλι, συνεπώς της είναι δυνατόν να ρυθμίζει τον ρυθμό μετάδοσης για τον συγχρονισμό στο td = tmax+tmin/2.
• Στην μέθοδο του Christian υπολογίζεται td=Τroundtrip/2-tmin.

Παραπάνω ανάλυση της μεθόδου του Christian μπορεί να γίνει με χρήση της πιθανοτικής μεθόδου και με της tmin, tmax, Troundtrip να είναι τυχαίες μεταβλητές. Ανάλογα με την τοπολογία, την ταχύτητα και το πόσοι κόμβοι έχουν το πλεονέκτημα της σωστής ώρας ο αλγόριθμος δίνει διαφορετικά tmin,tmax, και Troundtrip για την κάθε διεργασία Pu. Μία παράμετρος για την αποδοτικότητα του συστήματος είναι η διεργασία Pserver η οποία όπως γίνεται αντιληπτό θα έχει μεγάλο φόρτο εργα-σίας και σε κάποιες περιπτώσεις πχ σε ταυτόχρονες αιτήσεις θα καθυστερεί.

Λύση των Gusella kai Zatti

Μία άλλη λύση στο πρόβλημα που βλέπει από άλλη οπτική γωνία από αυτή του αλγορίθμου του Christian είναι αυτή των Gusella kai Zatti. Εδώ η ιδέα είναι πιο κεντρικοποιημένη και επιπλέον δεν υπάρχει ανάγκη για ύπαρξη ισχυρού ρολογιού. Ανά τακτά χρονικά διαστήματα μία διεργασία Pmaster επικοινωνεί με κάθε διεργασία Pu με τρόπο παρόμοιο με της μεθόδου του Christian για να λάβει τις τιμές των ρολογιών τους. Όταν όλες συγκεντρωθούν τότε ενσωματώνει και την δική της και υπολογίζει τον μέσο όρο. Έπειτα υπολογίζει τις τιμές της διαφοράς του μέσου όρου από την ώρα της κάθε διεργασίας Pu και στέλνει αυτήν την διαφορά. Η κάθε διεργασία υπολογίζει την σωστή ώρα που πρέπει να έχει και αλλάζει ανάλογα το ρολόι της. Προφανώς και η ίδια η Pmaster προσαρμόζει το δικό της.

RFC 958: Network Time Protocol (NTP)

Τελειώνοντας με τα φυσικά ρολόγια ας δούμε το Network Time Protocol. Το πρόβλημα με τις προηγούμενες μεθόδους είναι ότι λειτουργούσαν ωραία αλλά με τους περιορισμούς για μικρές πιθανότητες σφαλμάτων, έως και απουσία τους, και λίγων σχετικά κόμβων. Το NTP είναι έτσι φτιαγμένο ώστε μέσω του διαδικτύου να ενημερώνονται τα ρολόγια των διεργασιών που επικοινωνούν με αυτό. Μάλιστα προσφέρει ανοχή σε σφάλματα επικοινωνίας ακόμα και για μεγάλα χρονικά διαστήματα, κλιμάκωση για πολύ μεγάλο αριθμό κόμβων, και υψηλή ακρίβεια συγχρονισμού της τάξης των δεκάδων ms για κανάλια του διαδικτύου και λίγα ms σε τοπικά δίκτυα.

Περισσότερες πληροφορίες : http://www.faqs.org/rfcs/rfc958.html

Λογικός Χρόνος και Αλγόριθμοι Συγχρονισμού

Είδαμε στην προηγούμενη ενότητα ότι η χρήση φυσικών ρολογιών και ο συγχρονισμός τους είναι μία καθόλου εύκολη διαδικασία σε ένα κατανεμημένο σύστημα. Μάλιστα είδαμε ότι επιβαρύνει το σύστημα με αρκετά μηνύματα ενώ σε περίπτωση σφαλμάτων επικοινωνίας στις περισσότερες των περιπτώσεων δημιουργούνται προβλήματα στον συγχρονισμό.

Ωστόσο αν ρίξουμε μια ματιά στο γιατί χρειαζόμαστε τα ρολόγια σε ένα κατανεμημένο σύστημα διαπιστώνουμε ότι στις περισσότερες περιπτώσεις αυτό που χρειαζόμαστε είναι μια απλή διάταξη των γεγονότων μέσω μιας χρονολογικής σειράς. Ο Lamport παρατήρησε λοιπόν (‘‘Time, clocks, and the ordering of events in a dis-tributed system’’ – Περιοδικό Communications of the ACM, Volume 21, Issue 7 (July 1978), pp. 558—565) ότι σε πολλά προβλήματα δεν είναι αναγκαίο να έχουμε τα ρολόγια των διεργασιών συγχρονισμένα απλά πρέπει να εγγυόμαστε την πλήρη συνεπή διάταξη των γεγονότων στο σύστημα.

Θεωρούμε ότι κάθε διεργασία του συστήματός μας Pu βρίσκεται σε μία κατάσταση stateu. Διαχωρίζουμε τις ενέργειες που γίνονται στο σύστημά μας σε αυτές που αλλάζουν την κατάσταση της διεργασίας Pu και σε αυτές που δεν την αλλάζουν. Τις ενέργειες που δεν μεταβάλλουν την κατάσταση της δεν είναι αναγκαίο να τις καταγράψουμε καν. Για οποιαδήποτε ενέργεια που θα γίνεται τώρα στην διεργασία Pu, για παράδειγμα παραλαβή μηνύματος, αποστολή, αλλαγή της τιμής κάποιας μεταβλητής, ορίζουμε ένα συμβάν σu. Τα συμβάντα υποθέτουμε πως γίνονται σειριακά, κάτι που δεν αποκλίνει και πολύ της πραγματικότητας καθώς ας μην ξεχνάμε ότι βρισκόμαστε σε ασύγχρονα συστήματα κατά συνέπεια η πιθανότητα να έρθουν ταυτόχρονα δύο μηνύματα ας πούμε, είναι μικρή, αλλά και πάλι τότε κάποιο θα έχει έρθει λίγο πριν από το άλλο. Σε κάθε διεργασία υπάρχει μια αυστηρή διάταξη των συμβάντων που την αφορούν: σu1, σu2, σu3 … σuk, σuk+1 με αυτή τη διάταξη να σημαίνει ότι το σuk συνέβη πριν το σuk+1. Με αυτόν τον τρόπο ορίζουμε το ιστόρικο της κάθε διεργασίας P ως Hu={ σu1, σu2 …}.

Με αυτόν τον τρόπο για κάθε διεργασία έχουμε το ιστορικό της σε πλήρη διάταξη. Ωστόσο αυτό που θέλουμε στις περισσότερες περιπτώσεις είναι μια διάταξη γεγονότων για όλο το σύστημά μας. Έχουμε λοιπόν σε μία εκτέλεση a του συστήματός μας S, τα συμβάντα σ1,σ2,…,σk,… Η όλη ιδέα των λογικών ρολογιών είναι με κάποιο τρόπο να μπορέσουμε να διατάξουμε τα συμβάντα με χρονολογική σειρά δίνοντάς τους μια χρονοσφραγίδα (timestamp) TS(σ). Οι χρονοσφραγίδες θα επιλεγούν από ένα σύνολο Τ το οποίο μπορούμε αυθαίρετα και ανάλογα με τις ανάγκες μας να ορίσουμε. Για παράδειγμα μπορεί να είναι οι φυσικοί αριθμοί ή οι πραγματικοί αριθμοί που υποστηρίζει το σύστημά μας. Το σύνολο αυτό όπως γίνεται αντιληπτό δεν είναι ανάγκη να έχει καμία σχέση με την πραγματική ώρα.

Η σχέση συνέβη πριν

Κάπου εδώ ορίζουμε την σχέση συνέβη πριν. Θέλοντας να διατάξουμε τα συμβάντα που συμβαίνουν σε όλες τις διεργασίες στο σύστημά μας αντιμετωπίζουμε πρόβλημα. Το μόνο που ίσως ξέρουμε για να πετύχουμε κάτι τέτοιο είναι για κάποια συμβάντα μεταξύ των διεργασιών (πχ την αποστολή μηνυμάτων) ποιο συνέβη πριν από το άλλο. Είναι προφανές ότι μια αποστολή μηνύματος από την διεργασία Pu συνέβη πριν από την παραλαβή του ίδιου μηνύματος από την διεργασία Pv. H σχέση συνέβη πριν μοντελοποιεί δηλαδή την λογική σχέση εξάρτησης των συμβάντων. Ορίζεται ότι αν σi->σj τότε το συμβάν σi συνέβη πριν από το σj. Αυστηρότερα λοιπόν για την σχέση συνέβη πριν μπορούμε να πούμε:

• Αν μιλάμε για συμβάντα στην ίδια διεργασία τότε προφανώς ακολουθούμε την χρονολογική σειρά μέσα στην διεργασία όπως αυτή καταγράφηκε από την διεργασία στο ιστορικό της Hu.
• Αν μιλάμε για αποστολή και παραλαβή μηνύματος, το συμβάν της αποστολής μηνύματος (στην διεργασία αποστολέα) θεωρούμε ότι συνέβη πριν από το συμβάν παραλαβής μηνύματος (στην διεργασία παραλήπτη).
• Για την σχέση συνέβη πριν ισχύει η μεταβατική ιδιότητα αν δηλαδή σi->σj και σj->σk τότε ισχύει ότι σi->σk.

image

Είναι ευδιάκριτο από το παραπάνω σχήμα αλλά και από όσα είπαμε μέχρι τώρα ότι η σχέση συνέβη πριν αν και καταφέρνει να διατάξει μεγάλο μέρος των συμβάντων εκμεταλλευόμενη το ιστορικό των διεργασιών, τις αποστολές μηνυμάτων και την μεταβατική ιδιότητα, δεν είναι δυνατό να διατάξει όλα τα συμβάντα. Τα συμβάντα που δεν διατάσσονται με βάση την σχέση συνέβη πριν λέγονται λογικά ανεξάρτητα ή λογικά ταυτόχρονα. Για αυτά ισχύει σui||σvj  σui !->σvj ∩ σvj !->σui, δηλαδή κανένα δεν συνέβη πριν το άλλο. Ο όρος λογικά ταυτόχρονα δεν πρέπει να μας παρασύρει. Σε καμία περίπτωση δεν σημαίνει ότι τα δύο αυτά συμβάντα γίνονται την ίδια χρονική στιγμή, απλά δεν επηρεάζει την εκτέλεση του συστήματος μας αν θεωρήσουμε ότι έγινε πρώτο το ένα ή πρώτο το άλλο χωρίς να ξέρουμε στην πραγματικότητα την αλήθεια. Βέβαια, κάποιος εξωτερικός παρατηρητής θα μπορούσε να πει ποιο από τα δύο γεγονότα συνέβη πριν το άλλο. Όσον αφορά τα συμβάντα σε μία διεργασία λόγω του ιστορικού που είπαμε ότι κρατάμε ξέρουμε για όλα πιο συνέβη πριν το άλλο, συνεπώς δεν είναι δυνατόν συμβάντα τις ίδιας διεργασίας να είναι λογικά ανεξάρτητα.

Στο σχήμα βλέπουμε ότι e1.1||e3.2 ωστόσο το συμβάν e1.1 πραγματοποιήθηκε πριν από το e3.2. Επίσης e2.1||e1.4 με το πρώτο ωστόσο να έχει πραγματοποιηθεί πριν από το δεύτερο.

Συνοψίζοντας, είδαμε ότι δεν είναι δυνατόν να έχουμε διατεταγμένα όλα τα συμβάντα του συστήματός μας χρησιμοποιώντας την σχέση συνέβη πριν. Ωστόσο, ανά-μεσα σε δύο συμβάντα σ1 σ2 για τα οποία ισχύει σ1->σ2, αν υπήρχε ένα καθολικό ρολόι RC σε όλο το σύστημά μας και RC(σ1), RC(σ2) οι ώρες που πραγματοποιήθηκαν αντίστοιχα τα σ1 και σ2, τότε RC(σ1) < RC(σ2).

Λογικός χρόνος για ασύγχρονα δίκτυα

Η βασική ιδέα είναι ότι για κάθε γεγονός μιας εκτέλεσης σε ένα ασύγχρονο σύστημα Α δίδεται μια τιμή λογικού χρόνου, που είναι ένα στοιχείο ενός καθορισμένου πλήρως διατεταγμένου συνόλου Τ. Τυπικά , αυτό το σύνολο περιέχει τους μη αρνητικούς ακέραιους ή τους μη αρνητικούς πραγματικούς αριθμούς (ίσως επαυξημένο με άλλους τύπους τιμών όπως δείκτες διεργασιών). Αυτές οι λογικές τιμές δεν χρειάζεται να έχουν κάποια σχέση με τον πραγματικό χρόνο. Ωστόσο οι λογικές τιμές διαφορετικών γεγονότων απαιτείται να συμφωνούν με όλες τις απαραίτητες προϋποθέσεις γεγονότων μέσα στο σύστημα Α. Υπό αυτές τις υποθέσεις θα αποδείξουμε οτι η χρήση του λογικού χρόνου έχει τα ίδια αποτελέσματα με την ανάθεση πραγματικού χρόνου στις διεργασίες.
Εξετάζουμε τον λογικό χρόνο για συστήματα αποστολής/λήψης ξεχωριστά από τα συστήματα εκπομπής. Υποθέτουμε ότι τα κανάλια είναι τα αξιόπιστα αμφίδρομα FIFO και οτι δεν υπάρχουν λάθη.

Συστήματα Αποστολής λήψης

Θεωρούμε ένα ασύγχρονο σύστημα αποστολής/λήψης με αξιόπιστα αμφίδρομα FIFO κανάλια. Υποθέτουμε οτι ο γράφος του δικτύου είναι ισχυρά συνεκτικός. Θυμίζουμε ότι τα γεγονότα ενός τέτοιου συστήματος είναι των παρακάτω τύπων: γεγονότα επικοινωνίας του αυτομάτου με τους χρήστες του συστήματος, γεγονότα αποστολής λήψης με τα οποία επικοινωνούν οι διεργασίες με τα αυτόματα των καναλιών, και εσωτερικά γεγονότα των αυτομάτων των διεργασιών.( Θεωρούμε ότι τα αυτόματα των καναλιών επικοινωνίας που χρησιμοποιούμε δεν έχουν εσωτερικά γεγονότα που χρειάζεται να σημειωθούν)
Ας ορίσουμε ως α μια εκτέλεση ενός ασύγχρονου συστήματος αποστολής/λήψης Α. Τότε η ανάθεση λογικού χρόνου για το α ορίζεται ως η ανάθεση μιας τιμής του Τ σε κάθε γεγονός της α, με τρόπο συνεπή με κάθε πιθανή προϋπόθεση ανάμεσα στα γεγονότα του α. Συγκεκριμένα απαιτούμε να πληρούν τις παρακάτω 4 προϋποθέσεις:

1. Δυο γεγονότα δεν μπορούν να έχουν τον ίδιο λογικό χρόνο.
2. Οι λογικοί χρόνοι των γεγονότων σε κάθε διεργασία αυξάνονται αυστηρά σύμφωνα με την σειρά που συμβαίνουν στην α
3. Ο λογικός χρόνος κάθε αποστολής είναι αυστηρά μικρότερος του αντίστοιχου χρόνου λήψης.
4. Για κάθε συγκεκριμένη τιμή t του συνόλου Τ υπάρχει ακριβής αριθμός γεγονότων που μπορούν να τους ανατεθούν λογικοί

χρόνοι μικρότεροι του t. Από τις ιδιότητες 2 και 3 συνεπάγεται ότι η διάταξη του λογικού χρόνου πρέπει να συμφωνεί με την "συνέβη πριν" διάταξη των γεγονότων. Ωστόσο, επιτρέπουμε κάποια γεγονότα σε διαφορετικές διεργασίες να έχουν τους λογικούς τους χρόνους διατεταγμένους αντίστροφα από την σειρά τους στην α.
Μπορούμε να ισχυριστούμε ότι οποιαδήποτε ανάθεση λογικού χρόνου "μοιάζει" με μια ανάθεση πραγματικού χρόνου σε κάθε διεργασία του δικτύου. Συγκεκριμένα κάθε σωστή εκτέλεση α με μια ανάθεση λογικού χρόνου ltime μοιάζει για κάθε διεργασία σαν μια άλλη σωστή εκτέλεση α1 στην οποία οι λογικές τιμές του ltime αντιστοιχούν σε πραγματικές χρονικές στιγμές στις οποίες συμβαίνουν τα γεγονότα με την σειρά που περιγράφεται από το ltime

Θεώρημα (LogicalTime.1)

Εστω α μια ορθή εκτέλεση ενός συστήματος αποστολής λήψης Α με αξιόπιστα FIFO κανάλια και μια ανάθεση λογικού χρόνου ltime για την α. Τότε υπάρχει μια άλλη ορθή εκτέλεση α' του για την οποία ισχύει ότι:

1. η α' περιέχει τα ίδια γεγονότα με την α
2. τα γεγονότα στην α' συμβαίνουν με την ίδια διάταξη με τους λογικούς τους χρόνους στο α (τις ltime τιμές τους)
3. την α' εκτέλεση είναι αδύνατον να την ξεχωρίσουμε από την α για κάθε αυτόματο.

Απόδειξη:

Έστω γ μια ακολουθία που προκύπτει από την αναδιάταξη των γεγονότων του α σύμφωνα με την διάταξη ltimes. Η ύπαρξη αυτής της ακολουθίας εξασφαλίζεται από τις ιδιότητες 1 και 4 του λογικού χρόνου. Η ύπαρξη της ορθής εκτέλεσης α' προκύπτει από το μοντέλο των ασύγχρονων συστημάτων και το συμπέρασμα 14.2 σελ465 στο βιβλίο Distributed algorithms. Οι ιδιότητες 2 και 3 του λογικού χρόνου τότε συνεπάγονται πως η επαναδιάταξη διατηρεί την σχέση "συνέβη πριν" ανάμεσα σε όλα τα γεγονότα.

☐

Το παραπάνω θεώρημα καθορίζει πως η διάταξη των γεγονότων σε κάθε διεργασία πρέπει να είναι η ίδια στα α και α'. Ωστόσο επιτρέπει γεγονότα σε διαφορετικές διεργασίες να είναι διατεταγμένα με διαφορετικό τρόπο.

Παράδειγμα Συστήματος αποστολής/λήψης

Θεωρήστε ένα σύστημα αποστολής λήψης Α βασιζόμενο σε ένα πλήρες δίκτυο γράφου 3 κορυφών και μια εκτέλεση α του Α στην οποία τα μηνύματα στέλνονται και λαμβάνονται σύμφωνα με το σχήμα1.
Σε αυτό το διάγραμμα αποστολής λήψης, η εκτέλεση κάθε διεργασίας αναπαρίσταται απο μια κατακόρυφη γραμμή με τον χρόνο να εξελίσσεται προς τα κάτω. Οι τελείες υποδεικνύουν γεγονότα αποστολής ή λήψης και κάθε διαγώνια γραμμή ενώνει τα γεγονότα αποστολής και λήψης για ένα συγκεκριμένο μήνυμα. Δεν αναπαρίστανται άλλα γεγονότα όπως εσωτερικά γεγονότα των διεργασιών και γεγονότα με τα οποία οι διεργασίες επικοινωνούν με τους χρήστες. Αυτές μπορούν να παρασταθούν ως άλλες τελείες πάνω στις κατακόρυφες γραμμές.
Το σχήμα2 δείχνει μια ανάθεση λογικού χρόνου ltime για την εκτέλεση α (υποθέτοντας ότι η α αποτελείται μόνο από γεγονότα αποστολής και λήψης). Εφόσον ο χρόνος κυλά προς τα κάτω η ltime δεν αντιτίθεται στην διάταξη των γεγονότων στο α. Ωστόσο είναι σύμφωνη με όλες τις πιθανές προϋποθέσεις ανάμεσα στα γεγονότα του α.
Το σχήμα3 δείχνει την αναδιάταξη των γεγονότων του α στην διάταξη που περιγράφει το ltime παράγοντας την α' όπως περιγράφεται από το θεώρημα LogicalTime.1 . Να σημειωθεί ότι η σειρά των γεγονότων σε κάθε διεργασία είναι η ίδια στα α και α'.

Για κάθε εκτέλεση έχει οριστεί μια διάταξη εξαρτήσεων για τα γεγονότα που καλύπτει όλες τις πιθανές προϋποθέσεις ανάμεσα στα γεγονότα. Τότε σε κάθε περίπτωση τα γεγονότα της εκτέλεσης είναι αναδιατεταγμένα διατηρώντας όλες τις προϋποθέσεις άλλα αναδιατάσσοντας τες σύμφωνα με μια γενική έννοια χρόνου (σύγχρονους γύρους ή λογικό χρόνο). (Οι ορισμοί ενός τοπικού συνχρονιστή και λογικού χρόνου χρησιμοποιούνται για να δείξουν ότι αυτό μπορεί να συμβεί). Σε κάθε περίπτωση , Το συμπέρασμα είναι ότι η αναδιατεταγμένη εκτέλεση είναι τοπικά αδιαχώριστη από την αρχική εκτέλεση. Έτσι λοιπόν δείχνει σε όλους τους συμμετέχοντες στην αρχική εκτέλεση ότι λειτουργούν σε γενικότερο συνχρονισμό.

Συστήματα Εκπομπής

Μπορούμε επίσης να ορίσουμε λογικό χρόνο για αξιόπιστα ασύγχρονα συστήματα εκπομπής με αξιόπιστα κανάλια εκπομπής. Σε αυτή την περίπτωση τα γεγονότα είναι διεπαφή με χρήστη, γεγονότα εκπομπής και λήψης και εσωτερικά γεγονότα των διεργασιών.
Έστω α μια εκτέλεση ενός ασύγχρονου συστήματος εκπομπής. Μια ανάθεση λογικού χρόνου για το α ορίζεται ως η ανάθεση μιας τιμής του Τ σε κάθε γεγονός της α με τρόπο τέτοιο που να ικανοποιεί τις ίδιες ιδιότητες με το σύστημα αποστολής/λήψης εκτός της ιδιότητας 3 που τροποποιείται ως εξής:

• Ο λογικός χρόνος κάθε γεγονότος εκπομπής είναι αυστηρά μικρότερος από κάθε γεγονός λήψης που αφορά το μήνυμα της συγκεκριμένης εκπομπής.

Όπως και στα συστήματα αποστολής/λήψης έχουμε:

Θεώρημα (LogicalTime.2)

Έστω α μια ορθή εκτέλεση ενός συστήματος εκπομπής Α με ένα αξιόπιστο κανάλι εκπομπής , και ltime μια ανάθεση λογικού χρόνου για το α. Τότε υπάρχει μια άλλη ορθή εκτέλεση α' στο Α που

1. η α' περιέχει τα ίδια γεγονότα με το α
2. Τα γεγονότα στο α' συμβαίνουν σύμφωνα με τις τιμές ltimes στο α
3. την α' είναι αδύνατον να την ξεχωρίσουμε από την α για κάθε αυτόματο διεργασίας..

Απόδειξη:

Έστω γ μια ακολουθία που προκύπτει από την αναδιάταξη των γεγονότων του α σύμφωνα με την διάταξη ltime. Η ύπαρξη αυτής της ακολουθίας εξασφαλίζεται από τις ιδιότητες 1 και 4 του λογικού χρόνου. Η ύπαρξη της ορθής εκτέλεσης α' προκύπτει από την αναδιάταξη λογικά ταυτόχρονων γεγονότων που δεν μπορούν να συνδεθούν με περιορισμούς. Οι ιδιότητες 2 και 3 του λογικού χρόνου τότε συνεπάγονται πως η επαναδιάταξη διατηρεί την σχέση "συνέβη πριν" ανάμεσα σε όλα τα γεγονότα.

☐

Προσθέτοντας λογικό χρόνο σε ασύγχρονους αλγόριθμους

Για την προσθήκη λογικού χρόνου στα γεγονότα ενός ασύγχρονου συστήματος αποστολής/λήψης Α παρουσιάζονται 2 αλγόριθμοι. Κάθε ένας από τους αλγορίθμους αυτούς πρόκειται ουσιαστικά για ένα μετασχηματισμό του αλγορίθμου του Α σε ένα νέο αλγόριθμο L(A) με το ίδιο γράφο δικτύου. Ο μετασχηματισμός λειτουργεί σε κάθε διεργασία ξεχωριστά ορίζοντας την L(A)_i (διεργασία i του συστήματος L(A) ) σύμφωνα με την A_i (διεργασία i του συστήματος Α). Οι διεργασίες στο L(A) συνεργάζονται για να προσομοιώσουν κατά κάποιο τρόπο μια ορθή εκτέλεση του Α, όπου κάθε L(A)_i προσομοιώνει την αντίστοιχη A_i. Κάθε φορά που μια διεργασία του L(A) προσομοιώνει ένα βήμα του Α, "γεννά" και μια τιμή λογικού χρόνου. Και οι 2 αλγόριθμοι μπορούν να χρησιμοποιηθούν για την περιγραφή ενός συστήματος εκπομπής.

1. LamportTime
2. WelchTime