当前位置:   article > 正文

分布式理论梳理——FLP定理

flp理论

    FLP Impossibility(FLP不可能性)是分布式领域中一个非常著名的定理。它给出了一个令人吃惊的结论:在异步通信场景,即使只有一个进程失败了,没有任何算法能保证非失败进程能够达到一致性!这意味着,在假设网络可靠、节点只会因崩溃而失效的最小化异步模型系统中,仍然不存在一个可以解决一致性问题的确定性算法。

    这是为什么呢?如果一个节点的进程停止工作了,可其它节点并不知晓,它们认为是消息延迟或者这个进程特别慢,它们仍然会尝试读取消息。

    1)系统模型

    FLP定理基于下面几点假设:

  • 异步通信:
    异步通信与同步通信的最大区别是没有时钟、不能时间同步、不能使用超时、不能探测失败、消息可任意延迟、消息可乱序;
  • 通信健壮:
    只要进程非失败,消息虽会被无限延迟,但最终会被送达,且消息仅会被送达一次(无重复);
  • Fail-Stop模型:
    进程失败如同宕机,不再处理任何消息。相对Byzantine式模型,不会产生错误消息;
  • 协议约束:
    不要求所有非故障进程都达成一致,只要有一个进程进入决定状态就算达成一致,且一致结果只能是属于{0,1};
  • 失败进程数量:
    最多只有一个进程失败或单节点宕机;

    2)推导证明

    假设有A、B、C、D、E五个进程

声明:本文内容由网友自发贡献,转载请注明出处:【wpsshop博客】
推荐阅读
相关标签
  

闽ICP备14008679号