タグ

2016年4月26日のブックマーク (1件)

  • A Brief Tour of FLP Impossibility | Paper Trail

    One of the most important results in distributed systems theory was published in April 1985 by Fischer, Lynch and Patterson. Their short paper ‘Impossibility of Distributed Consensus with One Faulty Process’, which eventually won the Dijkstra award given to the most influential papers in distributed computing, definitively placed an upper bound on what it is possible to achieve with distributed pr

    rjj
    rjj 2016/04/26
    Asynchronousでネットワークは信頼できる(=メッセージはいくらでも遅れるがいつかは配達される)高々1つのプロセスしかfail-stopしないシステムにおいて、任意の初期状態から同意に達するアルゴリズムは存在しない。