A method for evaluating time complexity of distributed algorithms on the asynchronous state-communication model

摘要

Distributed Systems are commonly modeled by asynchronous models where no assumption is made about process execution speed. The asynchronous model is preferable to the synchronous one because the model reflects the fact that a distributed system consists of computers with different process speed. However, the asynchrony of the system makes it difficult to evaluate time complexity of distributed algorithms. In this paper, we define linear state-transition algorithms, a class of distributed algorithms, in the state-communication model and show that (ideal) time complexity of the algorithms in the asynchronous distributed model is derived from analysis of their synchronous execution, where all processes are synchronized in the lock-step fashion. This provides an effective method for evaluating time complexity of the linear state-transition algorithms in the asynchronous distributed model. We also demonstrate the effectiveness of the method by applying it to the self-stabilizing alternator.