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

Issue title: Concurrency Specification and Programming (CS&P)

Article type: Research Article

Authors: Czaja, Ludwik

Affiliations: Institute of Informatics University of Warsaw and University of Economics and Computer Science in Warsaw. lczaja@mimuw.edu.pl

Note: [] Address for correspondence: Institute of Informatics, Warsaw University, Banacha 2, Warsaw, Poland

Abstract: 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.

DOI: 10.3233/FI-2011-509

Journal: Fundamenta Informaticae, vol. 109, no. 3, pp. 255-264, 2011