  In this paper, we focus on the implementation of distributed programs in
using a key-value store where the state of the nodes is stored in a replicated
and partitioned data store to improve performance and reliability. Applications
of such algorithms occur in weather monitoring, social media, etc. We argue
that these applications should be designed to be stabilizing so that they
recover from an arbitrary state to a legitimate state. Specifically, if we use
a stabilizing algorithm then we can work with more efficient implementations
that provide eventual consistency rather than sequential consistency where the
data store behaves as if there is just one copy of the data. We find that,
although the use of eventual consistency results in consistency violation
faults (cvf) where some node executes its action incorrectly because it relies
on an older version of the data, the overall performance of the resulting
protocol is better. We use experimental analysis to evaluate the expected
improvement. We also identify other variations of stabilization that can
provide additional guarantees in the presence of eventual consistency.Finally,
we note that if the underlying algorithm is not stabilizing, even a single \cvf
may cause the algorithm to fail completely thereby making it impossible to
benefit from this approach.
