×

Tuning distributed control algorithms for optimal functioning. (English) Zbl 0783.68030

Summary: We present a model which characterizes distributed computing algorithms. The goals of this model are to offer an abstract representation of asynchronous and heterogeneous distributed systems, to present a mechanism for specifying externally observable behaviours of distributed processes and to provide rules for combining these processes into networks with desired properties (good functioning, fairness...). Once these good properties are found, the determination of the optimal rules are studied.
Subsequently, the model is applied to three classical distributed computing problems: namely the dining philosophers problem, the mutual exclusion problem and the deadlock problem. The property of fairness has a special position that we discuss.

MSC:

68N25 Theory of operating systems
68M10 Network design and communication in computer systems
68W15 Distributed algorithms
65K10 Numerical optimization and variational techniques
60J10 Markov chains (discrete-time Markov processes on discrete state spaces)

Software:

UNITY

References:

[1] Bui, M. (1990) R?lage pour un fonctionnement optimal d’un r?seau de processeurs en algorithmique distribu?e. Revue R. de Math. Pures et Appl. 3, 197-202. · Zbl 0800.68177
[2] Bui, M. (1990), On Optimal Management of Resources in Distributed Networks, Optimization 21 (5), 785-796. · Zbl 0716.68039 · doi:10.1080/02331939008843607
[3] Bui, M. and Butelle, F. (1991), Evaluations pratiques de l’efficacit? d’algorithmes distribu?s de contr?le, Res. Rpt. INRIA.
[4] Brand, D. and Zafiropulo, P. (1983), On Communicating Finite-State Machines. Journal of the ACM 30 (2), 323-342. · Zbl 0512.68039 · doi:10.1145/322374.322380
[5] Casavant, T. L. and Kuhl, J. G. (1990), A Communicating Finite Automata Approach to Modeling Distributed Computation and Its Application to Distributed Decision Making, IEEE Trans. on Computers 39 (5), 628-639. · doi:10.1109/12.53576
[6] Chandy, K. M., Misra, J., and Haas, L. (1983), Distributed Deadlock Detection, ACM TOCS 1 (2), 144-156. · doi:10.1145/357360.357365
[7] Chandy, K. M. and Misra, J. (1988) Parallel Program Design: A Foundation, Addison-Wesley. · Zbl 0717.68034
[8] Hoare, C. A. R. (1978), Communicating Sequential Processes, CACM, No. 21, 666-677. · Zbl 0383.68028
[9] Iosifescu, M. (1980), Finite Markov Processes and Their Applications. Wiley. · Zbl 0436.60001
[10] Kleinrock, L. (1985), Distributed Systems, CACM 28 (11), 1200-1213.
[11] Lamport, L. (1986), The Mutual Exclusion Problem: Part I and II, J. of ACM 33 (2), 327-348. · Zbl 0627.68018 · doi:10.1145/5383.5385
[12] Lavall?e, I. (1990), El?ments d’algorithmique parall?le et distribu?e, Herm?s, Paris.
[13] Le Lann, G. (1977), Distributed Systems: Towards a Formal Approach, IFIP Congress, pp. 155-160.
[14] Rozoy, B. (1990), On Distributed Languages and Models for Distributed Computation, Res. Rept. No. 563, University Paris 11.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.