ΚΑΤΑΝΕΜΗΜΕΝΟΣ ΥΠΟΛΟΓΙΣΜΟΣ: ΘΕΜΑΤΑ ΑΞΙΟΠΙΣΤΙΑΣ

Abstract

Η ΑΝΟΧΗ ΣΦΑΛΜΑΤΩΝ ΕΙΝΑΙ ΖΩΤΙΚΗ ΙΔΙΟΤΗΤΑ ΚΑΘΕ ΣΥΣΤΗΜΑΤΟΣ, ΕΚΕΙ ΟΜΩΣ ΠΟΥ ΓΙΝΕΤΑΙ ΕΜΦΑΝΕΣΤΕΡΗ Η ΣΗΜΑΣΙΑ ΤΗΣ, ΕΙΝΑΙ ΣΕ ΚΑΤΑΝΕΜΗΜΕΝΟ ΠΕΡΙΒΑΛΛΟΝ (ΕΤΕΡΟΓΕΝΕΣ Η ΠΟΛΥΕΠΕΞΕΡΓΑΣΤΙΚΟ ΣΥΣΤΗΜΑ), ΟΠΟΥ ΑΦ'ΕΝΟΣ Η ΥΠΑΡΞΗ ΣΦΑΛΜΑΤΩΝ ΕΙΝΑΙ ΔΕΔΟΜΕΝΗ, ΑΦ'ΕΤΕΡΟΥ ΤΑ ΣΥΣΤΑΤΙΚΑ ΤΟΥ ΜΕΡΗ ΕΙΝΑΙ ΣΤΗΝ ΟΥΣΙΑ ΑΝΕΞΑΡΤΗΤΑ, ΠΟΥ ΣΗΜΑΙΝΕΙ ΠΩΣ ΤΟΠΙΚΑ ΣΦΑΛΜΑΤΑ ΔΕΝ ΠΡΕΠΕΙ ΝΑ ΕΧΟΥΝ ΓΕΝΙΚΕΣ ΕΠΙΠΤΩΣΕΙΣ, ΕΚΤΟΣ ΚΑΙ ΑΝ ΚΑΠΟΙΟ ΠΡΩΤΟΚΟΛΛΟ ΔΗΜΙΟΥΡΓΕΙ ΕΞΑΡΤΗΣΕΙΣ. ΓΙΑ ΝΑ ΑΠΑΝΤΗΣΕΙ ΣΤΟ ΣΗΜΑΝΤΙΚΟ ΕΡΩΤΗΜΑ ΑΝ ΕΙΝΑΙ ΔΥΝΑΤΗ Η ΣΧΕΔΙΑΣΗ ΚΑΤΑΝΑΜΕΜΕΝΩΝ ΠΡΩΤΟΚΟΛΛΩΝ ΠΟΥ ΝΑ ΑΝΤΑΠΕΞΕΡΧΟΝΤΑΙ ΚΑΙ ΣΕ ΠΑΥΣΕΙΣ ΛΕΙΤΟΥΡΓΙΑΣ ΕΠΕΞΕΡΓΑΣΤΩΝ ΑΛΛΑ ΚΑΙ ΣΕ ΠΑΡΟΔΙΚΑ ΕΣΦΑΛΜΕΝΕΣ ΣΥΜΠΕΡΙΦΟΡΕΣ ΜΟΝΑΔΩΝ ΤΟΥ ΣΥΣΤΗΜΑΤΟΣ, Η ΔΙΑΤΡΙΒΗ ΜΕΛΕΤΑ ΤΗ ΣΧΕΣΗ ΜΕΤΑΞΥ ΑΥΤΟΣΤΑΘΕΡΟΠΟΙΗΣΗΣ ΚΑΙ ΕΛΕΥΘΕΡΙΑΣ ΑΝΑΜΟΝΗΣ ΣΤΙΣ ΚΑΤΑΣΚΕΥΕΣ ΑΦΑΙΡΕΤΙΚΩΝ ΤΥΠΩΝ ΔΕΔΟΜΕΝΩΝ, ΠΡΟΤΕΙΝΟΝΤΑΣ ΕΝΑΝ ΓΕΝΙΚΟ ΟΡΙΣΜΟ ΤΩΝ ΣΧΕΤΙΚΩΝ ΕΝΝΟΙΩΝ ΚΑΙ ΚΑΤΟΠΙΝ ΔΙΝΟΝΤΑΣ ΑΝΑΛΥΤΙΚΗ ΜΕΛΕΤΗ ΤΩΝ ΑΥΤΟΣΤΑΘΕΡΟΠΟΙΟΥΜΕΝΩΝ ΕΛΕΥΘΕΡΩΝ ΑΝΑΜΟΝΗΣ ΜΗΧΑΝΙΣΜΩΝ ΕΠΙΚΟΙΝΩΝΙΑΣ ΣΕ ΣΥΣΤΗΜΑΤΑ ΜΕ (ΙΔΕΑΤΗ) ΚΟΙΝΗ ΜΝΗΜΗ. ΑΚΟΛΟΥΘΩΣ ΠΑΡΟΥΣΙΑΖΟΝΤΑΙ ΑΥΤΟΣΤΑΘΕΡΟΠΟΙΟΥΜΕΝΑ ΕΛΕΥΘΕΡΑ ΑΝΑΜΟΝΗΣ ΠΡΩΤΟΚΟΛΛΑ ΣΥΓΧΡΟΝΙΣΜΟΥ ΓΙΑ ΤΗΝ ΚΛΑΣΗ ΠΟΛΥΕΠΕΞΕΡΓΑΣΤΙΚΩΝ ΣΥΣΤΗΜΑΤΩΝ ΜΟΝΗΣ ΦΑΣΗΣ. ΓΙΑ ΤΗΝ ΙΔΙΑ ΚΛΑΣΗ ΔΙΝΕΤΑΙ ΛΥΣΗ ΣΤΗΝ ΕΛΕΥΘΕΡΗ ΑΝΑΜΟΝΗΣ ΟΜΟΦΩΝΙΑ, ΑΠΑΝΤΩΝΤΑΣ ΕΤΣΙ ΣΤΟ ΑΝΟΙΧΤΟ ΕΡΩΤΗΜΑ ΣΧΕΤΙΚΑ ΜΕ ΤΗΝ ΣΥΓΧΡΟΝΙΣΤΙΚΗ ΔΥΝΑΜΗ ΑΥΤΗΣ ΤΗΣ ΑΡΧΙΤΕΚΤΟΝΙΚΗΣ ΣΕ ΠΑΡΟΥΣΙΑ ΣΦΑΛΜΑΤΩΝ. ΕΠΙΣΗΣ ΔΕΙΧΝΕΤΑΙ ΠΩΣΜΠΟΡΟΥΝ ΚΟΜΨΕΣ ΑΛΓΟΡΙΘΜΙΚΕΣ ΤΕΧΝΙΚΕΣ ΝΑ ΑΞΙΟΠΟΙΗΘΟΥΝ ΓΙΑ ΤΟΝ ΣΧΕΔΙΑΣΜΟ ΑΞΙΟΠΙΣΤΩΝ ΠΙΟ ΑΠΟΔΟΤΙΚΩΝ ΛΥΣΕΩΝ ΓΙΑ ΤΟΝ ΟΝΟΜΑΤΙΣΜΟ ΔΙΕΡΓΑΣΙΩΝ ΚΑΙ ΤΗΝ ΚΑΤΑΝΟΜΗ ΠΟΡΩΝ, ΚΑΘΩΣ ΚΑΙ ΓΙΑ ΤΟ ΔΥΝΑΜΙΚΟ ΣΧΗΜΑ ΣΥΓΧΡΟΝΙΣΜΟΥ ΧΕΙΡΑΨΙΑΣ, ΠΟΥ ΕΙΝΑΙ ΣΗΜΑΝΤΙΚΟ ΓΙΑ ΤΗΝ ΕΠΙΚΟΙΝΩΝΙΑ ΔΙΕΡΓΑΣΙΩΝ.

WHILE FAULT-TOLERANCE IS A VITAL PROPERTY OF ANY SYSTEM, IT IS ALL THE MORE SIGNIFICANT IN A DISTRIBUTED ENVIRONMENT (HETEROGENEOUS OR MULTIPROCESSOR SYSTEM),WHERE ON ONE HAND FAILURES ARE A FACT OF LIFE, WHILE ON THE OTHER HAND THE SYSTEM COMPONENTS ARE IN PRINCIPLE INDEPENDENT, IMPLYING THAT SOME LOCAL FAILURE DOES NOT DIRECTLY AFFECT OTHER COMPONENTS,UNLESS A PROTOCOL CREATES DEPENDENCIES. FOR ANSWERING THE QUESTION WHETHER HIGHLY FAULT TOLERANT DISTRIBUTED PROTOCOLS THAT TOLERATE BOTH PERMANENT PROCESSOR FAILURES AS WELL AS TRANSIENTERRORS ARE FEASIBLE, THIS THESIS MAKES ONE OF THE FIRST STEPS, DEFINING CAREFULLY THE RESPECTIVE CONCEPTS, STUDYING ANALYTICALLY THE RELATION BETWEEN SELF-STABILIZATION AND WAIT-FREEDOM IN INTERPROCESS COMMUNICATION IN SYSTEMS WITH(VIRTUAL) SHARED MEMORY AND GIVING COMMUNICATION PROTOCOLS HAVING BOTH THESE PROPERTIES. SUBSEQUENTLY IT PRESENTS WAIT-FREE AND SELF-STABILIZATION SYNCHRONIZATION PROTOCOLS, SUITABLE FOR THE CLASS OF IN-PHASE MULTIPROCESSOR SYSTEM ARCHITECTURES. FOR THE SAME TYPE OF MULTIPROCESSORS, IT SOLVES WAIT-FREE CONSENSUS, THUS PROVING THAT THEY ARE STRONG ENOUGH TO SUPPORT FULLY RESILIENT SYNCHRONIZATION, WHICH WAS AN IMPORTANT OPEN QUESTION. NEXT IT IS SHOWN HOW CAN ELEGANT ALGORITHMIC TECHNIQUES BE APPLIED TO PROVIDE EFFICIENT, CLOSE TO OPTIMAL RESILIENT PROTOCOLS FOR PROCESS NAMING AND RESOURCE ALLOCATION AND A POWERFUL SYCHRONIZATION MECHANISM, HANDSHAKING, WHICH IS IMPORTANT FOR INTERPROCESS COMMUNICATION.