Benefits of Stabilization versus Rollback in
Self-Stabilizing Graph-Based Applications on
Eventually Consistent Key-Value Stores
In this paper, we evaluate and compare the performance
of two approaches, namely self-stabilization and rollback,
to handling consistency violating faults (cvfs) that occur when a
self-stabilizing distributed graph-based program is executed on
an eventually consistent key-value store. Consistency violating
faults are caused by reading wrong values due to weaker level
of consistency provided by the key-value store. One way to deal
with these faults is to utilize rollback whereas another way is
to rely on the property of self-stabilization that is expected to
provide recovery from arbitrary states. We evaluate both these
approaches in different case studies –planar graph coloring,
arbitrary graph coloring, and maximal matching– as well as for
different problem dimensions such as input data characteristics,
workload partition, and network latency. We also consider the
effect of executing a non-stabilizing algorithm with rollback with
a similar stabilizing algorithm that does not utilize rollback.
Paper: Return to the publication list
Return to the Sandeep's home page