Σημειώσεις:Κατανεμημένοι Αλγόριθμοι:WelchTime

Από DistrSys

WelchTime

Πρόβλημα: Διάταξη Γεγονότων Δίκτυο: Γενικό Κλάση: Αποκεντρωτικός

Πολυπλοκότητα

Χρονική: - Επικοινωνίας: προσθέτει 1 double 1 int kai 1 id διεργασίας σε κάθε μήνυμα που αποστέλεται

Στη σύνταξη του κειμένου συνεισέφερε ο Αμαξηλάτης Δημήτριος

Όπως και ο LamportTime ο αλγόριθμος βασίζεται σε τοπικά λογικά ρολόγια, μόνο που αυτή την φορά δεν αυξάνονται ως απάντηση στην παραλαβή μηνυμάτων , αλλά τα μηνύματα που φθάνουν "νωρίς" καθυστερούνται. Κατά κάποιο τρόπο αυτός ο αλγόριθμος επεμβαίνει περισσότερο από τον LamportTime καθώς προσθέτει καθυστερήσεις στα γεγονότα της εκτέλεσης που κρύβεται πίσω του. Το πεδίο τιμών του λογικού χρόνου Τ είναι μια τριάδα (c,i,k) όπου c είναι ένας μη αρνητικός πραγματικός αριθμός, i ένας δείκτης διεργασίας , και k ένας θετικός ακέραιος. Η διάταξη των τριάδων είναι λεξικογραφική.

Μετατροπή WelchTime

Κάθε διεργασία WelchTime(A)_i διατηρεί μια τοπική μεταβλητή clock, με μη αρνητικές πραγματικές τιμές. Υποθέτουμε οτι οι τιμές του clock για την διεργασία i προκύπτουν από μια άλλη εφαρμογή που εξασφαλίζει πως οι τιμές του clock είναι μονότονα μη φθίνουσες και μη φραγμένες. Ο λογικός χρόνος κάθε γεγονότος είναι η τιμή της clock όταν αυτό συμβαίνει, με τον δείκτη της διεργασίας i να ξεχωρίζει γεγονότα ανάμεσα στις διεργασίες και τον ακέραιο k να διαχωρίζει τα γεγονότα μέσα στην ίδια διεργασία που συμβαίνουν χωρίς να έχει προλάβει να αλλάξει το clock. Να σημειωθεί ότι η τιμή του clock δεν αλλάζει κατά την διάρκεια οποιουδήποτε γεγονότος του αλγορίθμου Α. Η τιμή του clock για κάθε γεγονός send επισυνάπτεται σαν μια χρονοσφραγίδα στο μήνυμα που στέλνεται. Κάθε διεργασία i διατηρεί μια FIFO σειρά receive-buffer, για να κρατά τα μηνύματα των οποίων οι χρονοσφραγίδες είναι μεγαλύτερες ή ίσες με το τοπικό clock. Όταν ένα μήνυμα φτάνει στην διεργασία i εξετάζεται η χρονοσφραγίδα του. Εάν η χρονοσφραγίδα είναι μικρότερη από το clock το μήνυμα επεξεργάζεται άμεσα. Σε αντίθετη περίπτωση τοποθετείται στον receive-buffer. Σε κάθε τοπικά ελεγχόμενο βήμα που δεν επηρεάζει το ρολόι η διεργασία i αρχικά αφαιρεί από τον receive-buffer και επεξεργάζεται όλα τα μηνύματα των οποίων οι χρονοσφραγίδες είναι μικρότερες από την τιμή του clock. Αυτά τα μηνύματα επεξεργάζονται με την σειρά που εμφανίζονται στον receive-buffer.
Αυτός ο αλγόριθμος προσομοιώνει ένα γεγονός receive(m)_i του Α όταν το αντίστοιχο μήνυμα επεξεργάζεται( αντί για όταν πρωτοφτάνει στην διεργασία i). Η τιμή του clock που συνδέεται με το γεγονός receive είναι η τιμή του clock την στιγμή που το μήνυμα επεξεργάζεται.

Λογικός χρόνος στον WelchTime

Η ιδιότητα 4 του λογικού χρόνου στον WelchTime προκύπτει από τα μη φραγμένα λογικά ρολόγια. Η έλλειψη φράγματος στις τιμές εξασφαλίζει πως κάθε μήνυμα στον receive-buffer επεξεργάζεται τελικά κάποια στιγμή στο μέλλον. Επίσης οι ιδιότητες 1 και 2 προκύπτουν από τις τιμές i και k που προστίθενται στις τιμές των λογικών ρολογιών , ενώ η ιδιότητα 3 από την λειτουργία του receive-buffer.
Ως προς όλους τους ορισμούς που αναφέρθηκαν πριν , η μετατροπή που παράγει τον WelchTime(A)_i από τον A_i προσθέτει και διατηρεί το λογικό ρολόι , τον receive-buffer και τους αριθμούς i και k. Σε αυτόν τον μετασχηματισμό οι ενέργειες λήψης του A_i μπορούν να καθυστερηθούν.
Σε αυτόν τον μετασχηματισμό οι ενέργειες receive του A_i μπορούν να καθυστερήσουν. Η "προσομοίωση" τώρα παράγει μια σωστή εκτέλεση του Α που επαναδιατάσει κάποια γεγονότα receive του A σεβόμενο τα υπόλοιπα γεγονότα. Κάθε φορά που μια διεργασία i προσομοιώνει ένα γεγονός του Α, η λογική τιμή που δημιουργείται είναι μια triple (clock,i,k) , όπου k είναι ένας αριθμός διάταξης που χρησιμοποιείται ως δεύτερος όρος διάταξης.
Να σημειωθεί ότι η καθυστέρηση που μπορεί να προστεθεί από τον WelchTime είναι αρκετά μεγάλη όταν τα τοπικά ρολόγια των διεργασιών είναι πολύ εκτός συγχρονισμού. Αυτός ο αλγόριθμος λειτουργεί καλύτερα όταν τα ρολόγια διατηρούνται αρκετά συγχρονισμένα.

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