Managing self-inflicted nondeterminism
Dmitrii Zagorodnov, Keith Marzullo · 2005
When a computation is replicated for greater availability – either by simultaneous execution on multiple machines or by restarting it after a crash – the problem of keeping replicas consistent arises. Replicas lose consistency when their run-time states diverge. This can happen because of differences in hardware inputs (clock ticks, network packets, keystrokes, etc.), which in turn lead to differences in “wall clock” time and in scheduling of events, such as context switches and signals. Hence, asynchrony in hardware makes software nondeterministic. When replicating existing services, one does not have the ability to change the service to be flexible with respect to nondeterminism. Given this constraint, the traditional approach to maintaining replica consistency is to impose tighter synchronization. By forcing replicas to operate in lockstep – either on the level of hardware signals [8] or on the level of processor instructions [4] – the entire memory state of replicated machines can be kept identical. Working on a higher level, some systems [2, 6, 3] synchronize only the state that is deemed important for consistent execution. Since it is difficult to precisely identify the relevant sources of nondeterminism, these systems are conservative by synchronizing much more than is necessary. The cost of tighter synchronization is a loss of performance. For example, Hypervisor [4] suffered roughly a factor of 2 overhead in execution and TFT [3] reported between 23% and 58% for gzip, depending on the compression level. Although the cost of synchronization decreases when it is performed at higher levels, the cost of engineering a high-level solution grows since changing the OS or the application is usually timeconsuming and error-prone. Our experience in replicating TCP-based network servers [1, 9] indicates that the overwhelming majority of state inconsistencies among replicas never lead to differences in the external behavior of the server. One can draw an analogy between the effects of a nondeterministic event (such as a hardware interrupt) and the effects of a fault (a hardware glitch or a software bug): both have the potential to cause the service to diverge from its specification, but neither is guaranteed to do so. Not every fault leads to an error in the state and, likewise, not every event leads to a state divergence. Even when there is an error or a divergence in the run-time state, it does not always “leak outside” and cause a failure of the service. When it does not, we call the event benign; otherwise, we say that it is malignant.