Simple Consensus with Timeouts

Question

There are n participants and each participant has a timeout that could fire at any time before or in the process of consensus. Participants are in a distributed setting where partitions and failures can happen.

All participants can start with a value 0 or 1 (or true/false). If any participant starts with 0 or any participant's timeout expires before reaching consensus, all participants must decide 0. Otherwise, all participants must decide 1.

I've gone through several iterations of a simple consensus protocol inspired or similar to the Ben-Or consensus protocol but can't seem to find a solution.

The key differences between the Ben-Or protocol and this setting are:

1. Presence of timeout
2. Not randomized: If any are zero, then all should decide zero. If any timeout, then all should decide zero.

An example (inspired by Ben-or) for this highly simplified setting:

x = True or False
while x or timeout not expired:
  broadcast report=True
  wait for all other participants' reports until timeout
  if all reports are True and received all reports:
    decide True
  otherwise
    decide False

Key thing to prove: If a process p decides True, all other processes q decide True

I might be missing some key impossibility theory here. Any thoughts would be greatly appreciated.

Answer 1

Randomization is how Ben-Or escapes the Fischer–Lynch–Paterson impossibility result for deterministic consensus algorithms in unreliable networks. I think F–L–P basically applies to this setting unless you intentionally run out the clock each time and return 0 everywhere.