Thesis Topic Details

Topic ID:
3604
Title:
Expressiveness of Distributed Systems
Supervisor:
Rob Van Glabbeek
Research Area:
Theory, Distributed Systems, Formal Methods
Associated Staff
Assessor:
Peter Hoefner
Topic Details
Status:
Active
Type:
Research
Programs:
Group Suitable:
No
Industrial:
No
Pre-requisites:
The ability to understand and deliver formal mathematical proofs.
Description:
We aim to discover which systems can be implemented in a distributed way---and how---using only asynchronous communication between components, while preserving desirable properties that may be specified in terms of synchronous communication. In connection with this, we try to establish an expressiveness hierarchy of specification formalisms with different communication paradigms.

We propose and inventory various definitions of what it means for processes to communicate with each other using only asynchronous communication, and subsequently investigate which processes can be implemented conform these definitions. In deciding whether a given process can be implemented using only asynchronous communication, one needs to choose a semantic equivalence that specifies which aspects of the specified behaviour need to be preserved under implementation. Depending on this choice, either a class of systems can be implemented distributedly---and we aim at giving a structural characterisation of this class---or all systems can be implemented distributedly---and we aim to investigate the strongest behavioural equivalence that makes this possible.

The project will look at some particular formal mechanisms (e.g. process algebras, Petri nets, or Turing machines) and try to analyse their expressivity.
The goal involves the development of systems that can be or that cannot be implemented (incl. formal proofs of this) in the mechanism under consideration.
Comments:
--
Past Student Reports
 
No Reports Available. Contact the supervisor for more information.

Check out all available reports in the CSE Thesis Report Library.

NOTE: only current CSE students can login to view and select reports to download.