Chasing the FLP Impossibility Result in a LAN or How Robust Can a Fault Tolerant Server Be?

Fault tolerance can be achieved in distributed systems by replication. However, Fischer, Lynch and Paterson have proven an impossibility result about consensus in the asynchronous system model. Similar impossibility results have been established for atomic broadcast and group membership, and should be as such relevant for implementations of a replicated service. However, the practical impact of these impossibility results is unclear. For instance, do they set limits to the robustness of a replicated server exposed to extremely high loads? The paper tries to answer this question by describing an experiment conducted in a LAN. It consists of client processes that send requests to a replicated server (three replicas) using an atomic broadcast primitive. The experiment has parameters that allow us to control the load on the hosts and on the network and the timeout value used by our heartbeat failure detection mechanism. Our main observation is that the atomic broadcast algorithm never stops delivering messages, not even under arbitrarily high load and very small timeout values (1 ms). The result was surprising to us, as we expected that our atomic broadcast algorithm would stop delivering messages at such small timeout values. So, by trying to illustrate the practical impact of impossibility results, we discovered that we had implemented a very robust replicated service.