Benefit of Self-stabilizing Protocols in Eventually Consistent Key-value Stores: A Case Study

Document Type

Article

Publication Date

1-9-2019

Publication Title

ICDCN '19 Proceedings of the 20th International Conference on Distributed Computing and Networking

Volume

2019

First page number:

1

Last page number:

10

Abstract

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.

Keywords

Fault tolerance; Key-value stores; Self-stabilization

Disciplines

Computer Sciences

Language

English

UNLV article access

Find in your library

Share

COinS