Skip to main content
adding references
Source Link
hengxin
  • 9.6k
  • 3
  • 37
  • 74

The FLP theorem [1] says that

It is impossible for a set of processors in an asynchronous distributed system to agree on a binary value, even if only a single processor is subject to an unannounced crash.

There are several ways to circumvent this impossibility results, byby, according to Jennifer Welch; I suggest you to read the linked webpage

  1. changing the system assumptions
  • Assuming a synchronous system such as in the "Byzantine Generals" problem [2]
  • Assuming a partial synchronous system in which failure detectors [3] are used
  1. or changing the problem statement
  • No guarantee for termination (progress) such as Paxos [4]
  • Randomized protocol [5]
  • No need to agree on a single value such as in $k$-set agreement problem
  • No need to agree on exact values in approximate agreement

[1] Impossibility of Distributed Consensus with One Faulty Process) JACM, 1985.

[2] Reaching Agreement in the Presence of Faults JACM, 1980.

[3] Unreliable Failure Detectors for Reliable Distributed Systems JACM, 1996.

[4] Paxos Made Simple TR. By Lamport

[5] Another Advantage of Free Choice (Extended Abstract): Completely Asynchronous Agreement Protocols PODC, 1983. It has just received the 2015 Edsger W. Dijkstra Prize.

The FLP theorem [1] says that

It is impossible for a set of processors in an asynchronous distributed system to agree on a binary value, even if only a single processor is subject to an unannounced crash.

There are several ways to circumvent this impossibility results, by

  1. changing the system assumptions
  • Assuming a synchronous system such as in the "Byzantine Generals" problem [2]
  • Assuming a partial synchronous system in which failure detectors [3] are used
  1. or changing the problem statement
  • No guarantee for termination (progress) such as Paxos
  • Randomized protocol
  • No need to agree on a single value such as in $k$-set agreement problem
  • No need to agree on exact values in approximate agreement

[1] Impossibility of Distributed Consensus with One Faulty Process) JACM, 1985.

[2] Reaching Agreement in the Presence of Faults JACM, 1980.

[3] Unreliable Failure Detectors for Reliable Distributed Systems JACM, 1996.

The FLP theorem [1] says that

It is impossible for a set of processors in an asynchronous distributed system to agree on a binary value, even if only a single processor is subject to an unannounced crash.

There are several ways to circumvent this impossibility results, by, according to Jennifer Welch; I suggest you to read the linked webpage

  1. changing the system assumptions
  • Assuming a synchronous system such as in the "Byzantine Generals" problem [2]
  • Assuming a partial synchronous system in which failure detectors [3] are used
  1. or changing the problem statement
  • No guarantee for termination (progress) such as Paxos [4]
  • Randomized protocol [5]
  • No need to agree on a single value such as in $k$-set agreement problem
  • No need to agree on exact values in approximate agreement

[1] Impossibility of Distributed Consensus with One Faulty Process) JACM, 1985.

[2] Reaching Agreement in the Presence of Faults JACM, 1980.

[3] Unreliable Failure Detectors for Reliable Distributed Systems JACM, 1996.

[4] Paxos Made Simple TR. By Lamport

[5] Another Advantage of Free Choice (Extended Abstract): Completely Asynchronous Agreement Protocols PODC, 1983. It has just received the 2015 Edsger W. Dijkstra Prize.

Source Link
hengxin
  • 9.6k
  • 3
  • 37
  • 74

The FLP theorem [1] says that

It is impossible for a set of processors in an asynchronous distributed system to agree on a binary value, even if only a single processor is subject to an unannounced crash.

There are several ways to circumvent this impossibility results, by

  1. changing the system assumptions
  • Assuming a synchronous system such as in the "Byzantine Generals" problem [2]
  • Assuming a partial synchronous system in which failure detectors [3] are used
  1. or changing the problem statement
  • No guarantee for termination (progress) such as Paxos
  • Randomized protocol
  • No need to agree on a single value such as in $k$-set agreement problem
  • No need to agree on exact values in approximate agreement

[1] Impossibility of Distributed Consensus with One Faulty Process) JACM, 1985.

[2] Reaching Agreement in the Presence of Faults JACM, 1980.

[3] Unreliable Failure Detectors for Reliable Distributed Systems JACM, 1996.