Reconfiguration models and algorithms for stateful interactive processes

In this paper, we present new results in the area of reconfiguration of sta teful interactive processes in the presence of faults. More precisely, we c onsider a set of servers/processes that have the same functionality, i.e., are able to perform the same tasks and provide the same set of services to their clients. In the case when several of them turn out to be faulty, we w ant to reconfigure the system so that the clients of the faulty servers/pro cesses are served by some other, fault-free, servers of the system in a way that is transparent to all the system clients. We propose a new method for reconfiguring in the presence of faults: compensation paths. Compensation paths are an efficient way of shifting spare resources from where they are available to where they are needed. We also present optimal and suboptimal simple reconfiguration algorithms of low polynomial time complexity O(nmlog (n(2)/m)) for the optimal and O(m) for the suboptimal algorithms, where M i s the number of processes and m is the number of primary-backup relationshi ps. The optimal algorithms compute the way to reconfigure the system whenev er the reconfiguration is possible. The suboptimal algorithms may sometimes fail to reconfigure the system, although reconfiguration would be possible by using the optimal centralized algorithms. However, suboptimal algorithm s have other competitive advantages over the centralized optimal algorithms with regard to time complexity and communication overhead.