Impossibilité FLP
A démontré en 1985 qu'aucun algorithme de consensus asynchrone déterministe ne peut garantir à la fois liveness et safety si ne serait-ce qu'un seul nœud peut tomber en panne.
Fischer, Lynch, Paterson. « Asynchrone » signifie aucune garantie sur le délai de livraison des messages. Conséquence pratique : tout algorithme de consensus réel (Paxos, Raft, PBFT) contourne FLP en (a) s'appuyant sur des hypothèses temporelles (synchronie partielle — les messages finissent par arriver dans une borne donnée), (b) utilisant du hasard (consensus randomisé), ou (c) utilisant des détecteurs de défaillance. Avec le théorème CAP, l'un des piliers théoriques majeurs de la conception des systèmes distribués.