Self-stabilizing state machine replication in static and reconfigurable asynchronous message-passing systems

Abstract

Η μέθοδος Αναπαραγωγής Μηχανής Καταστάσεων (ΑΜΚ) (state machine replication) στον κατανεμημένο υπολογισμό είναι θεμελιώδης στη χρήση πλεονασμού πόρων για την επίτευξη ανοχής σφαλμάτων. Στοχεύει στη συνεχή διατήρηση της συνέπειας πολλών αντιγράφων (replicas) ενός –πιθανώς δυναμικού– κατανεμημένου αντικειμένου, παρέχοντας έτσι αυξημένη διαθεσιμότητα (availability), προσπαθώντας όμως παράλληλα να περιορίσει, κατά το δυνατόν, τις επιπτώσεις στην επίδοση του συστήματος. Δύο καταξιωμένα μοντέλα παροχής ΑΜΚ είναι η ομοφωνία (consensus) και ο εικονικός συγχρονισμός (virtual synchrony). Αλγόριθμοι ΑΜΚ βάσει ομοφωνίας έχουν μελετηθεί και χρησιμοποιηθεί ευρέως. Πρόσφατα, η ΑΜΚ με ανοχή αυθαίρετων σφαλμάτων προτάθηκε ως εναλλακτική του μοντέλου Απόδειξης-Εργασίας (Proof-of-Work) για τον ορισμό της σειράς των “blocks” στα “blockchains”. Κυριότερος λόγος είναι η δυνατότητα του πιο πάνω μοντέλου να υπερβαίνει το πρόβλημα της φθίνουσας επίδοσης που προκαλούν οι αυξανόμενες ανάγκες για συναλλαγές, αλλά και της υψηλής κατανάλωσης ενέργειας. Στον αντίποδα, η ΑΜΚ με βάση τον εικονικό συγχρονισμό απευθύνεται σήμερα προς υπηρεσίες νέφους (cloud services) με ανάγκες για υψηλές ταχύτητες. Τα συστήματα που υλοποιούν ΑΜΚ παρέχουν εγγυήσεις επί τῇ βάσει παραδοχών όπως η ύπαρξη ανώτατου ορίου στο ρυθμό εισόδου/εξόδου των αντιγράφων (επεξεργαστών ή εξυπηρετητών) στο σύστημα, καθώς και των σφαλμάτων τα οποία μπορούν να επισυμβούν, οι αλάνθαστοι πιθανοτικοί έλεγχοι σφαλμάτων, αλλά και η υπόθεση αρχικοποίησης όλων των συστημικών μεταβλητών σε μια ορθή κατάσταση. Εάν όμως τα πιο πάνω, έστω και προσωρινά, παραβιαστούν από παροδικά σφάλματα, τότε αυτό μπορεί να αλλοιώσει την κατάσταση ενός ή περισσοτέρων αντιγράφων, περιλαμβανομένου του μετρητή του προγράμματός τους. Συνεπώς, το σύστημα οδηγείται σε μια αυθαίρετη κατάσταση που το εξαναγκάζει σε διαρκώς εσφαλμένη υπηρεσία, ή σε μόνιμη διακοπή της υπηρεσίας, έως ότου υπάρξει ανθρώπινη διορθωτική παρέμβαση. Τα αυτοσταθεροποιούμενα συστήματα (self-stabilizing systems) ενισχύουν τα ανεκτικά σφαλμάτων συστήματα, επιτρέποντάς τους να ανακάμπτουν αυτόματα από παροδικά σφάλματα. Έτσι, και σε συνδυασμό με άλλες τεχνικές ανοχής σφαλμάτων, η αυτοσταθεροποίηση παρέχει μια περιεκτική και εύρωστη στρατηγική ανοχής σφαλμάτων και ανάκαμψης. Η παρούσα διατριβή προτείνει αυτοσταθεροποιούμενες αλγοριθμικές λύσεις με αποδεδειγμένες εγγυήσεις σε προβλήματα που σχετίζονται με την ΑΜΚ. Στο πλαίσιο αυτό, παρουσιάζουμε την πρώτη πρακτικά-αυτοσταθεροποιούμενη (practically-self-stabilizing) ΑΜΚ που εδράζεται στο μοντέλο εικονικού συγχρονισμού για ένα στατικό σύνολο αντιγράφων που δύνανται να καταρρεύσουν. Έπειτα, εισαγάγουμε δυναμικότητα στο σύνολο των αντιγράφων, και παρέχουμε το πρώτο αυτοσταθεροποιούμενο σύστημα αναδιαμόρφωσης (reconfiguration) που μπορεί να οδηγήσει σε διαμορφοποιήσιμο ΑΜΚ, βασισμένο είτε σε μοντέλο εικονικού συγχρονισμού, είτε ομοφωνίας. Τέλος αντιμετωπίζουμε το πιο δύσκολο μοντέλο σφαλμάτων, τα αυθαίρετα σφάλματα (arbitrary/Byzantine faults), και προτείνουμε έναν ανθεκτικό σε αυθαίρετα σφάλματα αυτοσταθεροποιούμενο αλγόριθμο ΑΜΚ, που βασίζεται σε υλοποιήσιμους ανιχνευτές σφαλμάτων. Η διατριβή συνεισφέρει επίσης ορισμένα επιμέρους αποτελέσματα, όπως ένα αυτοσταθεροποιούμενο κατανεμημένο μετρητή που μπορεί να υλοποιήσει αυτοσταθεροποιούμενη κατανεμημένη κοινή μνήμη πολλαπλών γραφέων και αναγνωστών (multi-writer multi-reader shared memory emulation), καθώς και καινοτόμες τεχνικές σχεδιασμού και αποδείξεων. Σε γενική θεώρηση τα τρία αποτελέσματα καλύπτουν ένα σημαντικό κενό στον δρόμο για την υλοποίηση αυτοσταθεροποιούμενων συστημάτων “blockchain” βασισμένων σε ΑΜΚ, αλλά και αυτοσταθεροποιούμενης διαμορφοποιήσιμης ανεκτικής σε αυθαίρετα σφάλματα ΑΜΚ.

State machine replication (SMR) in distributed computing is fundamental when employing redundancy of storage to facilitate fault-tolerance. It aims at maintaining the consistency of the state of several copies of a -possibly dynamic- distributed object, thus, providing increased availability. At the same time, it strives to reduce the impact on the system's performance. Research on cloud systems has significantly benefited from accumulated knowledge on SMR to quickly progress towards making cloud services efficient and reliable. Two established paradigms providing SMR are consensus and virtual synchrony (VS). Consensus-based SMR algorithms are widely-studied and used, and well-understood. Recently, Byzantine-tolerant SMR was proposed as an alternative to the Proof-of-Work (PoW) paradigm of block ordering in blockchains. This is because it is suggested to overcome the poor performance scalability of PoW and avoid the high energy consumptions. On the other hand, systems that provide the VS property are today directed towards high-speed cloud services. Systems implementing SMR provide guarantees based on assumptions like bounded churn rates, bounded replica failures, failure-free probabilistic error detection mechanisms, or that system variables are started in a consistent state. If these are, even temporarily, violated due to the occurrence of transient faults, then this may corrupt the state of a single or multiple replicas, including its program counters. Subsequently, this leads the system to an arbitrary state, causing it to become possibly unavailable, unless there is human intervention. Self-stabilizing systems enhance existing fault tolerant systems to allow them to automatically recover from transient failures. In this way, and combined with other fault-tolerance techniques, self-stabilization provides a comprehensive and robust fault-resilience and recovery strategy. This thesis proposes self-stabilizing algorithmic solutions with proven guarantees to several SMR-related problems. In this framework, we first present the first practically-self-stabilizing VS-based SMR for a static crash-prone replica set. We then introduce dynamicity in the membership of the replica set, and provide a modular self-stabilizing reconfiguration scheme that can lead to self-stabilizing reconfigurable SMR (based on either VS or consensus). We then address the more challenging failure model of Byzantine faults, and propose a malicious-tolerant self-stabilizing SMR algorithm based on implementable failure detectors. The thesis also bears several by-products such as a self-stabilizing counter that can be incremented in distributed fashion, and novel design and proof techniques. Considered together, the three results cover a significant gap towards achieving self-stabilizing versions of SMR-based blockchain frameworks or of reconfigurable Byzantine-tolerant SMRs.