On Deadlock and Fairness Decision Problems for Computations on Client-server Systems

• Autorzy: Czaja L.
• Języki publikacji: EN

Abstrakty

EN

Phenomena that inherently happen in distributed computing - some types of deadlock and fairness or starvation - are examined in a client-server model. Messages travelling between clients and a server are: request for an action, permission to start it, and termination of its execution. Deadlock-prone and (un)fair behaviours are formulated for the model and equivalence of the respective formulae to formulae expressing emptiness and finiteness of some sets generated by the model is established. From these results, some answers to decision problems for the aforesaid properties are obtained. Furthermore, equivalence between the so-called strong fairness (specified by first-order formula) and weak-fairness (second-order formula) is demonstrated

Słowa kluczowe

EN

decision problem; client-server systems; deadlocks; fairness

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 109, nr 3
• Strony: 255--264
• Opis fizyczny: Bibliogr. 5 poz., wykr.

Twórcy

autor

Czaja L.

• Institute of Informatics University of Warsaw and University of Economics and Computer Science in Warsaw,

Bibliografia

• [1] Brzozowski J.A.: Derivatives of regular expressions, J. ACM 11 (4) (1964)
• [2] Coulouris G., Dollimore J. Kindberg T.: Distributed Systems, Concepts and Design (second edition), Addison Wesley Longman Limited, London (1996)
• [3] Czaja L.: Deadlock and Fairness in Parallel Schemmas: a Set-Theoretic Charactrerization and Decision Problems, Information Processing Letters, vol. 10, number 4,5 (1980)
• [4] König D.: Űber eine Schlussweise aus dem Endlichen ins Umendliche, Acta Litt. Ac. Sci. Hung. Fran. Josep.3 (1927), 121-130
• [5] Thomas W.: Automata on Infinite Objects, in: Handbook of Theoretical Computer Science, vol. B (Jan van Leeuwen ed.), Elsevier, 1990