A communicating finite automata approach to modeling distributed computation and its application to distributed decision-making

• Published in: IEEE transactions on computers 1990-05, Vol.39 (5), p.628-639
• Main Authors: Casavant, T.L., Kuhl, J.G.
• Format: Article
• Language: English
• Subjects: Algorithm design and analysis; Automata; Computational modeling; Computer applications; Distributed computing; Distributed decision making; Performance analysis; Physics computing; Processor scheduling; Scheduling algorithm
• ISSN: 0018-9340; 1557-9956
• DOI: 10.1109/12.53576

A modeling technique for distributed computation based on a combination of directed graphs and finite automata is described. The paradigm of distributed decision-making (DDM) is used to illustrate the technique for its two primary purposes: providing a standard specification mechanism for different algorithms for solving the same problem and providing a common mechanism for objective quantitative evaluation and comparison of alternative DDM algorithms. This is accomplished through the definition of the terms performance and efficiency as they relate to the domain of DDM. The two terms, which have precise meanings with respect to the analysis of sequential algorithms, currently lack a common interpretation in the environment of DDM. In particular, they need to be expressed in terms of the information movement necessary to share state information. The method has been used extensively to conduct analyses of several distribution scheduling algorithms. This paper focuses on the model specification properties.< >