Models for concurrency: Local presentations for finite state distributed systems

Abstract

It is aimed to study the models of concurrency in the context of finite state systems, in order to understand the nature of distributed computing, and to help the design and analysis of distributed systems. Process models are considered in this study where no global observer is assumed. In process models a distributed system is assumed to consist of a finite number of sequential processes, which have some resources allocated to them. They proceed asynchronously and periodically exchange information among themselves. This thesis studies the local presentations of finite state distributed systems(FSDS), where each component is modelled as a finite state automaton(FA) over a fixed finite state of actions and global behaviour of the system is specified by a product of the component processes. Different structures on the component automata and by different rules for product construction are imposed and obtained different classes of local presentations. The local presentations considered in this thesis seem to be closely related to the class of knowledge based programs(FHMV), on the hope that these systems offer an automata-theoretic account of knowledge in distributed systems. This thesis studies the locally presented FSDS's from the point of view of their language behaviour. This thesis aims to establish tight connections between classes of FSDS's that are locally presented, the languages they accept, and their syntactic presentation in a top-level parallel fashion which reflects the architecture of process models. This thesis comprises of 7 chapters, among which first, second and the last chapters are dealing with motivation, preliminaries and conclusion respectively. The third chapter deals with 'View based systems' - an attempt at local presentation; Systems characterizing regular trace languages. The fourth chapter deals with 'Assumption Commitment Paradigm' - description and illustration by detailed examples. The fifth chapter 'The Assumption Compatible Systems' deals with the introduction of the main frame work, and studies the expressive power in terms of language acceptance, giving a simple syntax for the systems. And extends the theory to the regular infinite behaviours. The pre concluding chapter, 'Assumption-compatible systems with restrictions' shows some interesting subclasses of regular languages, how it could be captured by putting restrictions on assumption-compatible systems. This research work shows that (i)'a class of systems called Assumption Compatible Systems characterize all regular behaviour over the given set of actions that is distributed over the processes'; (ii) By putting constraints on system structure, different classes of behaviour is obtained; (iii) Infinite behaviour could also be characterized by these systems with suitable acceptance conditions.