Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
In Impossibility of distributed consensus with one faulty process @1985 by Fischer at al., the authors state (p375)
We also assume that processes do not have access to synchronized clocks, so algorithms based on timeouts, for example, cannot be used.
Why do algorithms that employ timeouts require that clocks be synchronized across processes?
Note that the authors also assume the following:
Crucial to our proof is that processing is completely asynchronous; that is, we make no assumptions about the relative speeds of processesor about the delay time in delivering a message.
The notion of "timing out processes" refers to the ability of knowing when to conclude that a process must have crashed. If you have a completely asynchronous system, then it does not help to equip processes with perfectly synchronized clocks, as these cannot be used to distinguish a slow process from one that has crashed.
