Αμοιβαίος Αποκλεισμός και Εκλογή Αρχηγού

Abstract

Σε αυτό το κεφάλαιο παρουσιάζονται αλγόριθμοι που επιλύουν τα θέματα του αμοιβαίου αποκλεισμού και της εκλογής αρχηγού στα κατανεμημένα συστήματα (ΚΣ). Η ανάγκη του αμοιβαίου αποκλεισμού εμφανίζεται στα ΚΣ, επειδή δεν υπάρχει αξιόπιστη πληροφόρηση για την καθολική κατάσταση του συστήματος, ούτε κοινό ρολόι μεταξύ των επικοινωνούντων συστημάτων. Έτσι, πρέπει να βρεθεί τρόπος ώστε μόνο ένα σύστημα τη φορά να έχει πρόσβαση σε έναν απομακρυσμένο κοινό πόρο. Παρουσιάζονται τρεις αλγόριθμοι για την επίτευξη του στόχου αυτού, ο αλγόριθμος του Raymond, ο αλγόριθμος των Ricart και Agrawala και ο αλγόριθμος του Maekawa. Πολλές φορές απαιτείται η εκλογή κάποιου κόμβου ως αρχηγού σε μια συστάδα κόμβων ενός ΚΣ. Σε αυτήν την κατεύθυνση παρουσιάζονται διάφοροι αλγόριθμοι εκλογής αρχηγού, όπως του LeLann, και των Chang και Roberts, με αντίστοιχα παραδείγματα.

This chapter presents algorithms that solve the issues of mutual exclusion and leader election in distributed systems. The need for mutual exclusion arises in distributed systems, because there is no reliable information about the global state of the system, nor a common clock between the communicating systems. So a way must be found so that only one system can access a remote shared resource at a time. Three algorithms are presented to achieve this goal, Raymond’s algorithm, Ricart and Agrawala’s algorithm, and Maekawa’s algorithm. Many times it is required to elect some node as leader in a cluster of distributed system nodes. In this direction, various leader election algorithms are presented, such as LeLann’s, and Chang and Roberts’, with corresponding examples.