ACD Atlas Computing Division Distributed Computing Systems

Jump To Main Content

Jump Over Banner

Home

Jump Over Left Menu

DCS Projects: London, Imperial

DR M S SLOMAN

COMMUNICATIONS FOR DISTRIBUTED PROCESS CONTROL

Sept 78 - Aug 81

Background

The original objectives of this project were to investigate the Communication Techniques for Distributed Process Control Systems. Half-way through the project, another related project was funded by the National Coal Board, on using Data Networks for Monitoring and Control in Coal Mines. This was much wider ranging, in that it included the study of programming techniques for distributed systems, distributed computer architecture and operating systems as well as communication techniques. The outcome of the NCB funded project has been the CONIC Architecture for Distributed Computer Control Systems (DCCS) with the SERC funded project forming the basis of the CONIC Communications System.

Research Goals

The research goals of the SERC funded project were to:

  1. Identify application requirements for communications
  2. Investigate the relevance of the CCITT X25 standard process for control applications
  3. Develop communication techniques for loosely coupled distributed microcomputers for the above application area.

Maurice Sloman speaking at DCS Conference, University of Sussex, 1984

Maurice Sloman speaking at DCS Conference, University of Sussex, 1984
Large View

Achievements

The initial phase of the project concentrated on a literature survey and discussions with a wide range of industries to determine application requirements for DCCS [3]. The CCITT X25 standard for accessing packet switched networks was evaluated, as a basis for a communication system for control applications. The evaluation showed that it would not meet the requirements without substantial modification [4]. More suitable local area network technology was likely to emerge for office automation applications so it was decided to work on the higher layers of the communication system.

Most process control systems exhibit a natural hierarchical structure. The overall plant is divided into subsystems in which the subsystems may themselves consist of a number of complex machines. This is reflected in the network topology which consists of broadcast sub-networks interconnected by store and forward gateways [5]. This topology permits easy modification by the addition and deletion of subnets or stations as required. The gateways isolate the subnets so that a failure in one will not affect the other subnets. The data rate and technology of a subnet can be chosen to suit the particular function for which it is used. The communication system was tailored to the above network topology and to the CONIC high level language intertask communication primitives [1]. These consist of two primitives: a request reply transaction, similar to the ADA rendezvous, but with timeout on completion of the transaction; and an asynchronous send primitive which never blocks the sender but has clearly defined buffer overwrite semantics. The same primitives are used for both local and remote communication.

The communication system supports the transfer of variable length messages between stations and is used for remote inter-task communications [6]. It provides two main services. The first is a reliable connection based service which performs automatic correction of transmission errors and reroutes around failures. The application programs using this service need not concern themselves with retransmissions etc. The second service is a simple datagram service with lower overheads but no guarantee of delivery. This is mainly used for system management but is also available for application use. The communication system also supports multi-destination addressing and broadcasting. The system routes messages from one subnet to another using tables. These tables are built up and maintained using a completely distributed algorithm which automatically recovers from failures.

Relevance to Industry

CONIC provides an integrated set of techniques and tools for constructing and managing large Distributed Computer Control Systems [2]. The CONIC software architecture provides a two level language: one for programming individual software components (module functions). and another for configuring a system from instances of these modules. The CONIC Operating System and Communication System supply the run-time support for this architecture. CONIC provides a very flexible approach to the design and implementation of distributed computer systems for process control, telecommunications and factory automation.

Work in Hand

The NCB is continuing to fund the development and extension of the CONIC Architecture. The investigators intend to examine techniques for specifying the behaviour of software components which communicate by message passing. In addition. on-line management tools and techniques for configuration and subsequent modification of large distributed real-time systems will be developed.

References

1. J. Kramer, J. Magee and M. Sloman. Intertask Communication Primitives for Distributed Process Control, 2nd International Conference on Distributed Computing Systems, Paris, April 1981.

2. J. Kramer, J. Magee, M. Sloman and A. Lister, CONIC: An Integrated Approach to Distributed Computer Control Systems, Proceedings lEE. Part E. January 1983 1-10.

3. S. Prince and M. Sloman, The Communication Requirements of a Distributed Computer Control System, Proceedings lEE. Vol. 128. Part E, No. 1, pp 2134, January 1981.

4. M. Sloman, The Relevance of the CCITT X25 Recommendations to Process Control Applications, in Real Time Data Handling and Process Control, edited by H. Meyer, N Holland, 1980, pp 447-453.

5. M. Sloman and S. Prince, Local Network Architecture for Process Control, In Local Networks for Computer Communications, pp 407-427, edited by A. West and P.Jansen, N Holland, November 1981.

6. M. Sloman, The CONIC Communication System for Distributed Process Control', Imperial College Research Report, DOC 82/8, October 1982.

S ABRAMSKY

AN APPLICATIVE PROGRAMMING METHODOLOGY FOR CONCURRENT AND DISTRIBUTED SYSTEMS

Oct 82 - Oct 84

Background and Nature of Research

There has recently been an upsurge of interest in applicative (or functional) programming. On one hand, applicative programs are simpler and more amenable to rigorous Software Engineering disciplines than their imperative counterparts; but in addition, they provide a more promising basis for the development of highly parallel architectures, since they are less wedded to a sequential model of execution. However, to date applicative programming has only been applied to concurrent and distributed systems, such as operating systems and networks of personal computers, in a limited and speculative way.

Research Goals

The proposed research has three main aims:

  1. To develop a coherent and systematic style of applicative programming for concurrent systems.
  2. To develop rigorous workable methods for formal specification, verification and transformation of such programs.
  3. To investigate implementation techniques for applicative multiprogramming, in order to construct experimental systems, and to obtain some insight into performance requirements and feasibility.

Achievements and Work in Hand

The project has made very encouraging progress in this period. The practical work carried out by Richard Sykes, has achieved the following:

  1. A complete implementation of the SECD-M machine [1] on the Perq (in Pascal), incorporating lazy evaluation, multiple processes, non-determinism in the form of fair merge (a significant extension of the original design), and I/O device interfacing, including multiple virtual keyboards and screens, character and S-expression disc I/O, and the Perq puck.
  2. A LISP KIT compiler extended to incorporate merge as a primitive.
  3. The design and implementation of a configuration language, which allows
    1. Compiled code to be loaded from a file and linked-in to a system by connecting its input streams to output and input streams of the system.
    2. Device interfacing to be set up by mapping input and output streams of the system to input and output devices.
  4. A number of applicative concurrent systems have been programmed, and run on a test-bed, including:
    1. A window manager. to allow multi-window I/O on the Perq display.
    2. Line protocols - some simple communications protocols programmed functionally - this work was done in collaboration with Colin Low.
    3. A directory based filing system, including functionally programmed disc I/O - still being developed.
    4. A Unix-like shell, supporting executable files I/O redirections to files, windows, etc. - still being developed.
    5. A mouse-controlled line drawing program.

Some of this work is reported in [4].

On the theoretical side, some promising advances have been made in the semantics of applicative multiprogramming, including:

  1. The development of a fixed-point semantics based on a categorical powerdomain construction which is an exact agreement with operational semantics, and is continuous even for unbounded nondeterminism.
  2. The characterisation of classical powerdomain semantics by indistinguishability modulo finite experiments, and the development of a hierarchy of non-deterministic languages and tests by varying the finiteness restrictions.

These results will appear in [2] and [3] respectively.

Applicability

The results are applicable to the development of functional programming as a realistic candidate for large-scale use. They also contribute to the development of high-level descriptions of concurrent systems. Finally, they provide some valuable information on implementation and performance requirements for applicative multiprogramming systems.

References

Note: QMC CSL nnn = Queen Mary College Computer Systems Laboratory Report number nnn.

1. S. Abramsky, SECD-M: A Virtual Machine for Applicative Multiprogramming, QMC CSL 322, 1982.

2. S. Abramsky, On Semantic Foundations for Applicative Multiprogramming, Proceedings of ICALP '83, Springer, Lecture Notes in Computer Science series, also QMC CSL 321. 1982.

3. S. Abramsky, Experiments, Powerdomains and Fully Abstract Models for Applicative Multiprogramming, Proceedings of FCT '83, Springer, Lecture Notes in Computer Science series), 1983.

4. R. Sykes, ' Techniques for Applicative Multiprogramming, submitted to ACM Conference on Principles of Programming Languages, 1983.

R J CUNNINGHAM and J KRAMER

COMPUTER ASSISTED METHODS FOR DEVELOPING VERIFIED SOFTWARE

Jan 82 - Dec 84

Background

The aim of this research project is to investigate and develop software tools which will assist the specification, design and production of verified software for distributed systems. Origins of the work lie in a method developed by the investigators for applying proof-directed methods of programming to the design of hierarchical distributed processing systems [1.7.2]. This indicated a potential benefit from software tools which would support a constructive approach to the development of sound software.

Goals

The main thrust of the project is in the provision of an experimental environment which will assist a software engineer in verifying each phase of the software development process; getting a formal specification from informal requirements and pursuing a process of verifiable design to produce a sound maintainable produce. A facility for creating and updating a database of specifications is an important part of the proposed environment. Software tools based on formal logics are intended to be available for automating key steps in validating specifications and constructing verifiable designs. It has always been intended that the environment should be based on a Unix system and exploit other high-level software in order to develop new tools and maintain the specification database. The integrated system is intended to be a vehicle for experimental applications in the use of formal design tools for distributed systems.

Achievements

In considering the most appropriate route for obtaining sophisticated tools for formal analysis it was decided to exploit theorem proving expertise within the department [6] and use Prolog as a prototyping language. Some separation of technical issues in logic and algebra was also resolved.

In previous reports there have been descriptions of work on basic tools for the analysis of standard form logic [3], and research into rewriting rules for simplifying expressions in partial algebras 4].

A parser and intermediate form for an experimental specification language have been developed.

Work in Hand

A more powerful theorem proving module based on Connection Graphs 6] is being developed. A report is in preparation.

Software tools previously provided in Waterloo Prolog have been converted to Edinburgh Prolog for the purposes of portability and integration with the Unix system.

Work on a polymorphic type checker for the specification language has been initiated.

Related Activity

Members of the project team collaborated in the organisation, lectures and demonstration at the BCS-FACS/SERC workshop on program specification and verification at York.

R. J. Cunningham participated by invitation in the ACM March workshop on high-level debugging and has also served on Validation, Verification and Testing Group of the DoI Software Tools Study.

Dr J. Kramer has contributed at an EWICS meeting on Application-Oriented Specifications and the SERC/DCS June Conference at Brighton.

A paper by Goldsack and Cunningham is included in the Pergamon Infotec State-of-the-Art Report on Software Engineering Developments 5].

References

1. R. J. Cunningham and J. Kramer, An Approach to the Design of Distributed Computer Control Software, Proc. lEE Conference on Distributed Control Systems 1977.

2. R. J. Cunningham and J. Kramer, ' The Design of Stable Distributed Processing Systems, Research Report 80/10, Department of Computing, Imperial College.

3. R. J. Cunningham and Silvana Zappacosta-Amoldi, Software Tools for First Order Logic, Software Practice and Experience 13(1983):1019-1025.

4. A. J. J. Dick and R. J. Cunningham, Systematic Design Methods in the Design of Computer Programs, in Software Engineering and Developments: State-of-the-Art Report 11:3, (Editor P.J.L.Wallis), Pergamon Infotec 1983.

6. R. A. Kowalski. A Proof Procedure based on Connection Graphs, JACM 22 4, 1975.

7. J. Kramer and R. J. Cunningham, Towards a Notation for the Functional Design of Distributed Processing Systems, Proc. IEEE/ACM International Conference on Parallel Processing, Michigan 1978.

DR J DARLINGTON

DEVELOPMENT OF A GENERAL PURPOSE APPLICATIVE LANGUAGE MACHINE AND APPLICATIVE PROGRAMMING ENVIRONMENT

Oct 82 - Sept 85

Background

This project to develop software and hardware components of an applicative language programming system, started to receive DCS funding in October 1982. The work was previously supported by other SERC grants. The DCS funding allowed expansion of the work, in particular the construction of a parallel graph reduction machine. ALICE (Applicative Language Idealised Engine).

Goals

The aim of the project is to investigate the potential of the applicative languages for improving software reliability and efficiency. The mathematical origins of these languages mean that they inherit all the essential attributes of mathematical notations such as conciseness, comprehensibility and manipulability, in marked contrast to the more conventional procedural languages whose close attachment to the von-Neumann model of computation embodied in all present day machines precludes these advantages. In particular the project is investigating the development of the languages themselves, their application to real world problems, the use of formally based program development systems and implementations on highly parallel architectures.

Progress in 1982/83

Work proceeded along the planned routes at a satisfactory pace and is on target for an ALICE prototype in 1985. Highlights of the first year's activity were:

  1. The overall design of ALICE was simplified and carried a stage nearer concrete realisation. Final coding of the machine in Occam was started and was half completed as of October 1983.
  2. The design of the network chip was completed. This 4 × 4 crossbar switch is asynchronous and self-timing and enables fault detection on the fly chip replacement in delta networks. The fabrication was planned for October 1983. A patent application has been filed via BTG.
  3. Various alternative network topologies were investigated and a new class of networks developed, in many ways superior to delta networks.
  4. A compiler for full standard USP to ALICE CTL was developed.
  5. The OR-parallel Prolog interpreter was extended to incorporate AND parallelism.
  6. A method of extending functional languages to incorporate unification was developed and is being studied. This enables one to incorporate facilities found in logic languages such as Prolog into a functional language.
  7. The Hope in Hope compiler was further developed and optimised.
  8. The Hope Pascal interpreter was further developed and distributed to a number of sites.
  9. A range of application software was developed in Hope including a picture description package and a language independent structure editor.
  10. Applications of declarative languages to real time problems were investigated and a methodology developed to allow necessary sequencing to be introduced in declarative notations in a systematic manner.
  11. The design of a simple single user operating system for the ALICE prototype was started.

Papers Produced

1. J. Darlington, Unifying Functional and Logic Languages, Internal Note, Department of Computing, Imperial College.

2. J. Darlington, From Specification to Program via Transformation, Invited Paper Mathematical Centre Symposium on Program Specification November 1983.

3. J. Darlington and M. J. Reeve, ALICE and the Parallel Evaluation of Logic Programs, Invited Paper Computer Architecture Symposium, Stockholm, June 1983.

4. A. J. Field, A Structure Independent Switching System with System Level Fault Tolerance, Internal Report, Department of Computing, Imperial College, 1983.

5. M. J. Reeve, ' The ALICE Compiler Target Language Reference Manual, Internal Report, Department of Computing, Imperial College.

DR M SLOMAN and DR J KRAMER

SPECIFICATION AND ON-LINE MANAGEMENT FOR DISTRIBUTED REAL-TIME SYSTEMS

Jan 83 - Dec 85

Background and Nature of Research

This project investigates specification techniques and on-line configuration management for distributed real-time systems. It is based on the CONIC project at Imperial College. The CONIC Architecture for a DCCS [1] [3] is the outcome of a project funded by the National Coal Board on the use of microcomputers for monitoring and control in coal mines. Dr Sloman has an associated project funded by SERC on Communication Techniques for Distributed Control.

CONIC provides an integrated set of techniques and tools for constructing and managing large Distributed Computer Control Systems. The CONIC software architecture provides a two level language: one for programming individual software components (module definitions), and the other for the configuration of a distributed system from instances of these modules.

Future distributed systems will consist of large numbers of microprocessor based stations connected to a communication system. The complexity of structuring and controlling the hardware and software components in such large distributed systems requires the use of computer based tools for management of the system. Conventional system builders use a system description and generate an initial system, possibly with some checking for consistency with respect to the specification of the system structure.

However most systems are not static, but evolve as requirements change. Hence it must be possible to modify or extend parts of the system. Since it may not be safe or economic to shut down the entire system. it must be possible to introduce these changes while the system is running. Thus the configuration facility needs to be on-line, to have the capability of controlling individual components (eg. add, remove, start or stop) and must maintain information on the current status of the system. CONIC provides a suitable software component and the run-time environment to instantiate and interconnect these components dynamically, but tools are needed to check that changes are made in a safe and consistent way. A configuration language is necessary to allow the designer to express the logical structure of his system in terms of interconnected groups of modules. and the mapping onto hardware structure of stations and subnets. Ideally the system must be capable of automatically determining the physical interconnection structure of the hardware components but the languages should also allow this to be expressed by the designer. The language used to describe incremental changes should be the same as that used for initial system descriptions.

The configuration manager will have to provide a number of users (eg plant manager, maintenance engineer, control engineer, plant operator) with information on the current structure and status of the system, and these users may have different views of the system. This indicates that different names or naming trees for objects may have to be supported. To be investigated are the issues of how groups of modules can be named and treated as a single entity to hide complexity or to reflect application structure (eg. subsystems). The configuration manager will have to maintain a database which contains all the above information and may have to provide different user profiles or access filters.

Individual Module Behaviour - A number of the more recent programming languages have recognised the need to separate the interface specification from the operational details given in the body of the package, or module. This has gone some way to providing a separation of specification from implementation information, but so far has only provided structural information. A major concern is that these interface specifications do not include behavioural aspects. In the same way as the algebraic approach has provided a sound basis for the specification of the behaviour of abstract data types, so there is a need for behavioural specifications, including real-time constraints, of message passing modules in distributed systems.

Composition of Modules - Using a suitable configuration language CONIC modules can be interconnected to form a system. These connections would be checked to ensure structural compatibility (ie. that exit to entry port links and have the same message types) and so to provide some security against erroneous configurations. The system description, together with rules of composition of individual module behaviours, would provide a means for specification of system behaviour. Behavioural compatibility could then be checked at the same time as structural compatibility.

CONIC also supports the notion of reusable modules by instantiation with different actual parameters. The affect of these parameters on module instance to its environment should be checkable. The on-line system configuration facilities discussed in the previous section will provide a powerful but potentially dangerous environment in which modules can be replaced, added or deleted at run time. Behavioural specifications with composition rules would help to ensure that only safe modifications are made to the system.

The need, then, is for a practical, soundly based approach to the specification and composition of the message passing modules.

Work in Hand

Some progress in the configuration management area has been made. An initial off-line network builder which creates static configurations of CONIC modules for a network of stations has been implemented, [2] provides a model of the system configuration process and a framework for examining dynamic configuration. This proposes a language which specifies the logical configuration of nested groups of modules and provides the means for specifying changes to the initial configuration. Considerable work is still needed to refine these proposals and in particular to provide an elegant means to specify the mapping of the logical configuration onto a physical one.

References

1. J. Kramer, J. Magee, M. Sloman and A. Uster, CONIC: An Integrated Approach to Distributed Computer Control Systems, IEE Proceedings, Vol. 130. t E. No. 1. pp. 1-10, January 1983.

2. J. Magee and J. Kramer, Dynamic System Configuration for Distributed Realtime Systems, IFAC/IFIP Workshop on Real-time Programming, March 1983.

3. M. Sloman, J. Kramer, J. Magee and K. Twidle, A Flexible Communication System for Distributed Computer Control, IFAC DCCS Workshop, May 1983.