Jump Over Left Menu
The Distributed Computing Systems Programme 1977-84
This Overview was the opening talk at the DCS Conference at Sussex University in September 1984. The Proceedings were published by Peter Peregrinus Ltd on behalf of The Institution of Electrical Engineers as Distributed computing systems programme edited by D A Duce in 1984 (ISBN 0-86341-023-5).
The body principally responsible for funding computer science research in U.K. Universities and Polytechnics is the SERC. This responsibility is discharged in the main by the awarding of research grants to institutions. Funds may be requested for staff, travel and equipment, and in addition investigators may request access to the council's own facilities, for example computing resources, typically located in one of the council's laboratories. Research grant applications are considered by the council's committees, whose members are drawn from academe and from industry, together with assessors from other government departments. Thus the principle of peer review is adopted, within a context which evaluates the intellectual potential of the proposed research together with the possibility of, eventual, industrial value.
The council operates mainly in a responsive mode, responding to applications submitted by its clients, rather than a directive mode in which the initiative for new projects rests with the council. Prior to 1977 Information Technology was funded purely in this responsive way, although examples of different ways of working could be found in other areas of the council's activities. There had developed a strong feeling within the council committees concerned, that it would greatly enhance the state of computing research in the U. K. if there could be identified a common focus for new activity. At the same time, it was becoming increasingly obvious that a principal barrier to further development of computing systems, was the inability to manage the power becoming available from cheaper, faster hardware; particularly when many processors were grouped in complex, concurrent networks: that is, distributed computing. The Computer Science committee, recognizing the importance of distributed computing as a research area, appointed a panel in June 1976 under the chairmanship of Prof. I. Barron, to consider what action was necessary to encourage, coordinate or direct research in Distributed Computing. This panel was asked to take particular account of the potentially high cost of such research and the avoidance of unnecessary duplication of effort.
In its report to the committee in October 1976, the panel recommended that a coordinated research programme should be established and that additional funds should be sought for the programme. When a draft programme was circulated to relevant academic departments for comment, more than 50 replies were received, the great majority expressing a desire to participate and offering useful criticisms of the proposed mechanics and content of the programme. A one-day Workshop, in March 1977, provided an opportunity for a direct exchange of views on the original proposal and on the research problems to be addressed. The panel, in response to these helpful interchanges of views, revised a number of its original proposals.
The eventual proposal to set up a coordinated programme of research into Distributed Computing Systems was warmly welcomed by the Engineering Board of SERC. Approval in principle for the programme was given by the Board in June 1977; the programme was initiated in the academic year 1977-78. DCS was the first attempt by SERC to establish a long term, extensive, coordinated programme of research in Information Technology.
The primary scientific objectives of the programme were to seek an understanding of the principles of Distributed Computing Systems and to establish the engineering techniques necessary to implement such systems efficiently. These broad objectives reflect the relative immaturity of the subject when the programme was founded. In particular the programme sought to establish an understanding of parallelism in infonuation processing systems and to devise ways to take advantage of this.
The practical objectives of the programme can be summarized  as: to achieve results of practical value to the U.K. industry by directing research to a key area for the future; to promote relevant Computing Science research of high quality in academic departments by coordinating the efforts and achievements of individual research teams, and to ensure a cost effective research programme.
A Distributed Computing System was considered to be one in which there are a number of autonomous but interacting computers cooperating on a common problem. The essential feature of such a system is that it contains multiple control paths executing different parts of a program and interacting with each other. Such systemS might consist of any number of autonomous units, but the more challenging problems involve a large number of units. Thus, the spectrum of Distributed Computing Systems includes networks of conventional computers, systems containing sets of microprocessors, and novel forms of highly parallel computer architecture with greater integration of processing and storage.
The motivations for and importance of research into distributed computing systems are many and varied. Some major ones are:
- Performance: eventually it will be impossible to increase the speed of a single processor and retain commercial viability. Several processors, cooperating on a single task, will be the only way to greatly enhance performance.
- Reliability: a fully distributed system should be able to tolerate faults caused by either software or hardware. Hardware faults can be tolerated for example, by having more than one of each critical element. Software faults can be reduced by running different algorithms in parallel and checking the validity of results.
- Clarity: many problems are naturally parallel. Some problems are inherently simpler if expressed as a set of interconnected and communicating processes. If a problem's solution is expressed in this way it could be easier to provide a proof of correctness for the whole solution by breaking the proof task down, first proving the correctness of individual processes, and then proving the correctness of their interconnection.
- Distribution: in areas such as real time control it is often important that processor power is available where it is required in order to minimise the bandwidth requirements of data paths.
- Cost: the low cost of microprocessors allows certain tasks to be performed more economically on sets of microprocessors than on a single main frame processor.
2. MANAGEMENT OF DCS
We have already mentioned two extreme ways in which SERC operates, responsive mode and directed mode. In responsive mode the initiative for new projects rests entirely with investigators. Submissions are made to SERC as new ideas are conceived and support becomes necessary. The committees reviewing grant applications can only exercise control at bottom, by accepting or rejecting applications. The other pole to this model is a totally directed programme in which essentially, the Director, issues invitations to research groups to work on particular problems. The initiative for new work then rests entirely with the Director. In practice, of course, neither extreme is fully adopted - any research programme which is to be successful must take account of the talents and interests of the research community, and equally the community must understand that the availability of limited funds makes it impossible to pursue all lines of research that, at first sight, seem promising; priorities must be established.
Within this scheme, a coordinated programme falls mid-way between the two extremes. The aim of coordination is to establish a symbiotic working relationship between the committee responsible for the management of the programme, whose chief concern lies in the proper administration of limited resources, and the researchers whose concern is the pursuit of knowledge in their chosen disciplines. It is essential to create an atmosphere of mutual understanding and cooperation among the researchers themselves, and to create an environment in which research ideas can be discussed and priorities agreed.
There were two main reasons for adopting a coordinated approach to research in distributed computing. First reflecting the importance of the subject to the progress of computing and information technology, it helps to ensure a reasonable balance of SERC support across the various areas concerned; and a framework facilitating take-up of research results by industry. Second the substantial costs of much research in this field, and the limits of funds available, make it essential to provide support in a cost effective way - without impinging on the necessary freedom of investigators in carrying out fundamental research.
The idea of a fully directed programme was explored but subsequently rejected. (The idea of a directed I.T. programme has now been realized in the Alvey programme.)
What then are the practicalities of coordination? Coordination has been achieved at two levels. First within the programme itself, there has been continuing contact with investigators, starting with assistance in formulating research proposals, and throughout the research period, by regular interchange of information both spoken and written. Second, outside the programme, links have been fostered with industrial organizations (including government establishments etc.) likely to make use of the research in some form.
The coordination team includes an Academic Coordinator (drawn from the staff of SERC Rutherford Appleton Laboratory), responsible principally for liaison with and monitoring of the research projects; and an Industrial Coordinator, (from industry) who is also charged with expanding the external contact range of the research, with a view to collaborative research and technology transfer. The coordinators are supported by a Technical Secretary and by various support and development staff maintaining and enhancing the programme's infrastructure. When the programme was established it was envisaged that coordination would not be a very demanding activity and so the first coordinators were employed on a part-time (1 day per week) basis. It rapidly became clear that this premise was false and that coordination is a very demanding activity indeed. Since the earliest days of the programme the Academic Coordinator has been employed on a full-time basis, but the Industrial Coordinator has remained a part-time appointment.
The programme has been monitored and controlled by a panel of researchers and industrialists, appointed by the council, to whom the coordinators report. The panel has both evaluated and recommended award of research grants in DCS subject areas, and considered regular six-monthly progress reports from each group in the programme.
3. INFRASTRUCTURE ACTIVITIES
A major factor in the development of the DCS programme has been the recognition of the need for a well appointed infrastructure on which to build research programmes. The infrastructure provided by DCS has included a meetings programme of workshops and conferences, a community wide mail shot , Annual Report, an equipment pool, and a high level of backup technical support.
3.1 Meetings programme
To be successful, a coordinated programme must engender a sense of community in its participants. It must also bring together disparate groups of researchers in a constructive way, to foster the germination of new ideas or new approaches to traditional problems. The single most influential factor in bringing this about within the DeS programme has been the workshop programme. Some of the most significant pieces of research in the programme can be traced back to particular gatherings of researchers. Considerable experience in organizing workshops has been built up in DCS. The most fruitful meetings have typically been of 1½ days duration and limited to 25-30 participants. As the programme evolved and research themes became established, meetings of researchers in each area were held at regular intervals, to monitor and discuss progress.
As the programme matured, it became appropriate to hold an annual conference, attended by all the research groups within the programme plus other interested researchers and practitioners from both industry and academe. In March 1983, as well, a special conference was held at the NCC in Manchester entitled Distributed Computing A Review for Industry , to acquaint senior technical management in U.K. industry with the work of the programme.
From the earliest days of the programme a monthly mailshot was sent to all participants. The mailshot is a collection of papers submitted by the participants themselves and its contents ranged from draft technical papers for comment through to announcements of forthcoming meetings. A particularly valuable feature has been the inclusion of trip reports. It was made a condition of overseas travel that a trip report should be produced for the mailshot. This has proved a very valuable way of keeping the programme abreast of developments overseas.
3.4 Annual Report
From the start, the programme has produced an Annual Report, containing an overview of each project within the programme . This has proved a very valuable introduction to the programme for both industry and academe.
At an early stage the DCS panel decided to establish an equipment pool from which investigators could borrow. Initially the pool was stocked with magnetic tape decks, VDU's and modems to improve communications and software interchange between research groups. A key decision was to provide Unix (TM) licences for the programme. As time has passed the pool has grown and now includes local area network equipment (Cambridge Ring), X25 connections and high performance single user workstations (Perqs) .
Electronic communications between projects within the programme have steadily improved, through the provision of hardware to link to either the Universities/ Research councils X25 network, JANET, or British Telecoms PSS network. X25 software for the Unix operating system has been produced by the University of York. This is a good example of one of the benefits of coordination: recognizing the need for this software, the DCS panel funded just one site to produce it. Without coordination there would have been a real danger of many sites embarking upon the same project with consequent wastage of effort.
3.6 Technical Backup
SERC operates a nunber of laboratories to provide specialized services and facilities to SERC funded projects. Within the computer science area, SERC's Rutherford Appleton Laboratory (RAL) provides, for example, large mainframe computers and microelectronics design and fabrication facilities.
The DCS programme has been supported by RAL since January 1978. The Academic Coordinator and Technical Secretary are on the staff of RAL and other RAL staff provide software and hardware support for the programme. RAL support has included:
- Support for the Unix operating system used by the majority of DCS investigators.
- Provision of software to couple the Unix troff text formatting software to SERC's III FR80 microfilm recorder.
- Assembly and distribution of software to drive the Cambridge Ring.
- Construction of 6 Cambridge Rings for the DCS equipment pool and procurement from industry of a further 10 6-node ring systems.
- Procurement, distribution and maintenance of the equipment pool.
- Support and operation of the programme's electronic mail facility.
4. RESEARCH THEMES
When the DCS programme was first established, the DCS panel categorized the research into five major topic areas, representing a progression from fundamental theory to novel applications. The areas were:
- Theory and Languages: An adequate theoretical basis for Distributed Computing Systems.
- Resource Management: Distribution of control, allocation, scheduling and organization.
- Operational Attributes: Particularly reliability and performance.
- Design, Implementation and Application: Hardware and software techniques for development and implementation.
As the programme evolved, projects have clustered around emerging ways in which to structure distributed systems which may be claimed reasonably as emerging ground themes:
- Loosely-coupled distributed systems. Such systems are multicomputer configurations that do not share immediate memory and can be dispersed over wide geographical areas. Research in this area has been concerned with the overall structure of such systems, requirements for operating systems appropriate to this environment and related programming languages.
- Closely-coupled distributed systems. Typically systems which do share a common memory. Again research has been concerned with architecture, operating systems, programming languages and applications.
- Non von-Neumann architectures. Research in this area has been concerned with alternative ways to provide high speed numerical computing and with architectures to support the efficient evaluation of declarative languages.
A fourth major theme in DCS has been concerned with theories of parallel computation and with the development of notations and techniques for specifying and verifying such systems.
The work on loosely-coupled systems can be traced back to the work of Wilkes, Needham and others at Cambridge which led to the construction of the Cambridge Distributed Operating System . A key component in this work was the design of the Cambridge Ring local area network, the design study for which was published in 1975. This work commenced prior to DCS, but later Cambridge work was DCS funded. From Cambridge, this approach spread to the University of Kent and other sites, including York, Keele, Oxford, Strathclyde and Newcastle; all of whom have made their particular contribution to knowledge in this area. A particularly important step came early in 1980 when DCS constructed 6 Cambridge Rings, each of four nodes, to the Cambridge Mark 2 design. The demand for this equipment from research groups was considerably in excess of supply and the panel, recognizing the opportunity to foster the take-up of this result by industry, placed a contract with U.K. industry for the construction of further Ring hardware. This was a formative step in establishing the supply of Ring equipment in the U.K. The availability of common hardware for the pursuit of research in this area had a very beneficial effect in drawing research groups together.
Work in the tightly-coupled systems area can be traced back to projects in Evans' group at Loughborough and Aspinall's group at Swansea (now at UMIST). Grimsdale's group at Sussex were subsequently funded to work in this area. Dixon at Hatfield Polytechnic and Evans have explored the application of such systems to various classes of numerical problems.
The non-von Neumann architectures work can be traced back to projects at Manchester, Newcastle and Westfield College, concerned with the dataflow approach. A seminal event in this area was a Workshop at Newcastle in 1979 which brought together the dataflow researchers and researchers in the fields of applicative and logic languages. This led to a number of proposals for ways to exploit parallelism for efficient execution of such languages and for further language developnent work. DCS has been largely responsible for the creation of the strong U. K. research community in this field.
Our fundamental understanding of concurrency has been greatly enriched by the work of Milner and Plotkin at Edinburgh and Lauer at Newcastle. It is only proper to acknowledge the great contribution of Hoare's group at Oxford to this field, though this was not funded entirely by DCS. The recent work by Hoare's group on the specification of distributed systems has been funded by DCS and is described in the chapter by Morgan and Gimson. Cunningham, Kramer and Abramsky at Imperial College have also made significant contributions to this area. Design methodologies for distributed systems are discussed in the papers by Hughes and Powell, and Sloman and Kramer.
Performance modelling of distributed systems has been extensively investigated by Mitrani at Newcastle and a review of the area appears later in this book.
5. INDIVIDUAL PROJECTS
It is useful to describe a small number of the projects funded by DCS, by way of illustration and to set in context the subsequent chapters in this book. Descriptions of all the projects funded may be found in .
The Manchester Dataflow Project has demonstrated the viability of a parallel computing system based on the dataflow model of computation, which exploits irregular parallelism at the instruction level. It allows a wider range of applications than the more rigid vector and array processors. The prototype machine has demonstrated perfonnance improvements through concurrency almost lineal for up to 10 processing elements. This project has delivered concrete results where previously there was only speculation. The prototype hardware is being used both by research institutions and by industry to assess the direction of future dataflow products.
In the declarative architectures field, the ALICE Project is investigating the developnent of applicative languages, their use in real-world problems, formally based developnent systems and implementations on highly parallel architectures. This project has received a great deal of public interest and has produced significant papers on language design, programming methodology and computer architecture.
Turner (Kent) has made great contributions to the areas of declarative language design (SASL, KRC, Miranda) and evaluation (combinators). Henderson (Stirling) has explored the problems of producing purely functional operating systems. Sleep (East Anglia) has also explored the distributed evaluation of applicative languages.
Within the loosely-coupled systems field, the Unix United work of Randell's group  has received wide acclaim. This development was funded by DCS and is being exploited commercially. Distributed filestores and operating systems have also been investigated at Keele (Bennett), York (Wand), and Strathclyde (Shepherd). Bornat and Coulouris (QMC) have investigated one approach to the construction of such systems (Pascal-m).
The main groups in the tightly-coupled systems area are those of Aspinall (UMIST), Evans (Loughborough) and Grimsdale (Sussex). Each has constructed a model system and explored its applicability to a range of problems.
The work of Milner and Plotkin on theoretical models of concurrent systems has received world-wide acclaim. Several U.K. companies are exploring the applications of these techniques to their application areas. Cunningham's group (Imperial College) and Hoare's group (Oxford) have made significant advances in the specification of concurrent systems.
6. SOME STATISTICS
The box (Fig 1.1) illustrates the scale and breadth of involvement which DCS has created and managed over the past few years. In particular, we believe that the investment which the programme has made in infrastructure and coordination, amounting to about 21% of the funds expended, has enhanced the overall value of the activity enormously.
|Normal research grants awarded||103|
|Cooperative grants awarded||3|
|Visiting Fellowships Awarded||20|
Universities holding DCS Grants
|Polytechnics holding DCS Grants||3|
Number of research staff employed (approx)
Total value of grants awarded
|Expenditure on coordination||0.4M|
|Expenditure on infrastructure||2.0M|
Fractional spend on infrastructure
|Fractional spend on coordination||4.6%|
The major achievement of the DCS programme has been to create a strong research community in the U.K.
It is not too strong to claim that without DCS the discussions which lead to the formation of the Alvey programme could not have taken place. DCS has also established new research groups where none previously existed and has enabled a number of young researchers to become established in the field much more rapidly than otherwise would have been the case. The human interface between the management panel and its clients through the coordinators has been a key factor in bringing this about.
The establishment of the U.K.'s strong position in declarative systems research owes much to DCS.
Now that the DCS programme has ended, the work funded by DCS will continue through either the Alvey Directorate or the SERC's Computing Science Sub-committee as appropriate. Research ideas fostered by DCS are appearing in products through the Alvey programme.
Many of the lessons learnt in the DCS programme have been incorporated in the Alvey programme, for example the need for full-time technically competent staff to manage the programme and the need for infrastructure both in terms of a workshop programme and computing resources.
This book, plus the research publications of the participants in the programme, mark the intellectual achievement of the programme. In terms of contribution to knowledge, the programme should claim, for example: the advance and earliest use of local networking technology through the Cambridge Ring; the development of new architectural techniques, particularly for Idataflow and Graph Reduction systems; creation of some of the first techniques for specifying and describing concurrent computation; and methods for performance modelling and analysis in complex systems.
Technology transfer to industry is much harder to estimate. The main products of the DCS programme are ideas and demonstrations of ideas, rather than systems that can, and should, be turned directly into commerical products. Trained manpower has also been a major product of the programme, and it is through this avenue that technology transfer is best being achieved. More than one company, has benefitted directly from DCS manpower!
The DCS programme has involved a very large number of talented researchers, whose contributions to the programme I wish to acknowledge globally here. I also wish to acknowledge the contributions made by the former chairmen of the DCS panel, Iann Barron, Ian Pyle, and Roger Needham, together with all who have served on the panel; and above all the coordinators of the programme, Bob Hopgood, Gill Ringland, Rob Witty, Jeremy Tucker, David Duce and Fred Chambers.
1. DCS Annual Report, available from Dr D. A. Duce, Computing Division, Rutherford Appleton Laboratory, Chilton, Didcot, OXON OX11 0QX.
2. Distributed Computing - A Review for Industry, Proceedings available from Dr D. A. Duce, address as above.
3. R. M. Needham and A. J. Herbert, The Cambridge Distributed Computing System, Addison-Wesley, 1982.
4. D. R. Brownridge, L. F. Marshall and B. Randell, The Newcastle Connection - or UNIXes of the World Unite, Software Practice and Experience, Vol. 12, No 12, December 1982.