FLP: deterministinio asinchroninio konsensuso riba
Tyrimų kontekstas
postgraduate concept · established · Patikros data 2026-10-10
Fischer, Lynch ir Paterson įrodo, kad deterministinis konsensuso protokolas jų visiškai asinchroniniame pranešimų perdavimo modelyje gali turėti leidžiamą vykdymą be sprendimo, kai įvyksta ne daugiau kaip vienas sustojimo gedimas.
Esminės žinios
Fischer, Lynch ir Paterson įrodo, kad deterministinis konsensuso protokolas jų visiškai asinchroniniame pranešimų perdavimo modelyje gali turėti leidžiamą vykdymą be sprendimo, kai įvyksta ne daugiau kaip vienas sustojimo gedimas. Sutapimas ir galiojimas negarantuoja baigtinumo kiekvienam leidžiamam tvarkaraščiui. Teorema neteigia, kad kiekvienas vykdymas baigiasi nesėkme, ir neatmeta pažangos esant dalinei sinchronijai, tikimybinio baigtinumo naudojant atsitiktinumą ar stipresnių gedimų detektoriaus prielaidų.
Sąlygos ir taikymo ribos
- Procesai yra deterministiniai; pranešimų vėlavimas neapribotas, o vienas procesas gali sugesti sustodamas pagal straipsnyje nurodytas vykdymo leistinumo sąlygas.
- Tikras protokolas turi nurodyti, kuri papildoma prielaida pagrindžia jo gyvybingumo garantiją.
Šaltiniai · 1
Šaltiniai
Šaltiniai išlaiko savo taikymo ribas. Vien nuoroda nepatvirtina kiekvieno teiginio patikrinimo.
Pagrindimas ir peržiūra
Autorius patikrino šį anglišką teiginį, pateiktą lygtį, jei ji yra, ir nurodytas prielaidas pagal šias šaltinių vietas: Modelio apibrėžimai, leistini vykdymai ir pagrindinė neįmanomumo teorema. Patikra apsiriboja užrašytais teiginiais; neteigiama, kad visiškai atkurtas įrodymas, pakartotinai atlikta programinė įrodymo patikra ar aprėpta visa literatūra.
2026-10-10 · Autoriaus atlikta šaltinio teksto, teiginio, lygties ir taikymo srities patikra; grafo sąsajų aprėptis nurodyta atskirai. Prieš užbaigiant šaką būtina atskira nepriklausoma turinio, šaltinių ir inventoriaus peržiūra.
Įrašo informacija
Nuolatinė nuoroda į šį įrašą ↗- Įrašo identifikatorius
- research-info-flp-impossibility
- Versija
- research.1
- Struktūruotas žinyno įrašas
- Podiplominis ir tyrimų žinynas