Efficient fault detection helps keep distributed systems consistent and fast
Efficient Heuristics and Machine Learning Approach for Fault Characterization in Distributed Self-Stabilizing Programs
Distributed, Parallel, and Cluster Computing
Summary
Distributed systems that share memory can sometimes read old or incorrect data, causing errors called consistency violating faults. The paper shows how two approaches—a special search method and a machine learning model—can find and understand these faults quickly. This helps designers build programs that stay correct even when these errors happen. The methods were tested to confirm they work well across different cases.
What this means in practice
- •For distributed systems engineers: Identify and handle faults that cause stale data reads in distributed shared memory systems to improve system reliability and efficiency during runtime.
- •For database replication teams: Use improved analysis of consistency faults to design database replication protocols that balance availability and correctness more effectively.
Authors
Amit Garu, Duong Nguyen
Abstract
Modern large-scale systems rely on distributed protocols to maximize efficiency while preserving the correctness guarantees of single-process execution. However, designing such protocols is non-trivial: adding resources to a system inherently increases its complexity, which in turn introduces faults that must be addressed during design. One such fault class, arising in systems that use distributed shared memory (e.g., replicated databases), is consistency violating fault (cvf), a fault in which a process accessing shared memory reads stale data previously written by another process. Cvfs are inherent to systems that prioritize availability over strict consistency. Prior work has shown that self-stabilizing programs remain correct under high availability, provided such faults stay within a tolerable bound. Characterizing the behavior of self-stabilizing programs in the presence of cvfs can therefore help system designers build systems that are both correct and efficient. In this paper, we study self-stabilizing programs under cvfs to understand when and where such faults occur, enabling runtime measures that improve computational efficiency. Since exhaustive state-space exploration does not scale, it suffers from state-space explosion; our study investigates two complementary approaches: a conflict-based state-space exploration technique for monotonically stabilizing $(Δ + 1)$-Graph Coloring programs, and a machine-learning-based approach for a Maximal Independent Set program. We propose a conflicting-edges-based state-space exploration algorithm alongside a rigorously validated ML model, evaluated on an out-of-distribution dataset through structural consistency checks against known graph invariants.