Stability of Long-lived Consensus
Shlomi Dolev and Sergio Rajsbaum
To appear at Nineteenth Annual
ACM SIGACT-SIGOPS Symposium on PRINCIPLES OF DISTRIBUTED COMPUTING (PODC
2000), Portland, Oregon, 16-19 July 2000
Abstract
This paper introduces the notion of stability for a long-lived consensus
system. This notion reflects how sensitive to changes the decisions of
the system are, from one invocation of the consensus algorithm to the next,
with respect to input changes. Stable long-lived consensus systems are
proposed, and tight lower bounds on the achievable stability are proved,
for several different scenarios. The scenarios include systems that keep
memory from one invocation of consensus to the next versus memoryless systems;
systems that take their decisions based on the number of different inputs
but not on the source identities of those inputs versus non-symmetric systems.
These results intend to study essential aspects of stability, and hence
are independent of specific models of distributed computing. Applications
to particular asynchronous and synchronous systems are described.