Dancing with Fischer, Lynch & Paterson’s impossibility result

Abstract

This thesis presents Mimir, an asynchronously distributed Single Sign-On (SSO) service that uses biometric scanners on physical devices to reach states of authorized and authenticated. As an asynchronously distributed system, Mimir requires guaranteed consensus to achieve authorised and authenticated states, an impossibility to guarantee proved by FLP’s (Fischer, Lynch, Paterson) Impossibility Result. A practical approach is taken to implement Mimir as an asynchronously distributed system, and the implementation was used to study the navigation, mitigation, and practicalities of situations where practical systems encounter hindrances in reaching consensus. This included mechanisms for data synchronisation to enforce an orderly sequence of messages, timers for partial synchrony with the expectation of eventual synchronisation, and fault prevention. Experiments on fault prevention and orderly sequence were conducted to assess the constructed environment, and a standard approach to probability calculations was made. Despite the measures taken, our findings show that limitations, such as the FLP’s Impossibility Result, are more than theoretical boundaries; instead, they are shapers of practical systems and how they are built

Þessi ritgerð kynnir Mimi, ósamþætta og dreifða Single Sign-On (SSO) þjónustu sem notar líffræðilega skanna á handhægum tækjum til að þess að staðfesta auðkenni. Þar sem Mímir er ósamþætt og dreift kerfi, krefst það þess að samþykki sé tryggt til þess að afla auðkennis, sem getur verið ómögulegt að tryggja eins og sannað hefur verið með FLP (Fischer, Lynch, Paterson) ómöguleikaniðurstöðunni. Hagnýtar aðferðir voru nýttar til þess að þróa Mimi sem ósamþætt, dreift kerfi og hönnunin á kerfinu nýtt til þess að rannsaka boðleiðir, mótvægisaðgerðir og hagkvæmni í aðstæðum þar sem slík hagnýt kerfi mæta hindrunum við öflun samþykkis. Þar á meðal er samþætting ganga til að tryggja skipulega röð skilaboða, tímamælingar fyrir samþættingu að hluta þar sem búist er við samþættingu að endingu, og bilanavarnir. Tilraunir með bilanavarnir og skipulagða röðun voru gerðir til að þess að meta umhverfi kerfisins, ásamt því að staðlaðar aðferðir voru nýttar við líkindaútreikninga. Þrátt fyrir þessar mótvægisaðgerðir sýna niðurstöður okkar að takmarkanir, eins og FLP ómöguleikaniðurstaðan, eru meira en bara fræðilegir jaðrar og hafa mótandi áhrif á hvernig megi þróa og hanna hagnýt kerfi.