Toward feedback stabilization of faulty software systems: a case study

Software systems generally suffer from a certain fragility in the face of "disturbances" such as bugs, unforeseen user input, unmodeled interactions with other software components, and so on. A single such disturbance can make an entire system hang or crash. We postulate that what is required to address this fragility is a general means of using feedback to robustly stabilize these systems. In this paper we develop a model of an iterative software process, specifically a nondeterministic, faulty list sorter. Feedback is introduced into the process to achieve robust stability with respect to incorrect sorting operations. To keep the computational requirements of the controllers low, randomization and approximation are used. Methods by which software robustness can be enhanced by distributing a task between nodes, each of which are capable of selecting the "best" input to process, are also explored. The particular case of a sorting system consisting of a network of partial sorters, some of which may be buggy or even malicious, is examined.