An integrated microcomputer network for experiments in distributed programming
David Hillel Gelernter · 1983
A network computer is a computer network designed to function not as a collection of autonomous hosts but as one machine. Systems intended to support experiments with asynchronous distributed programs, including both distributed systems programs and distributed applications, form a major sub-class of network computers. The goal of the Stony Brook Network (SBN) project is to construct such a general-purpose network computer. Unlike most other systems in its class, SBN is a language-centered design. SBN's starting point is the distributed programming language Linda. To run on SBN, a distributed program must either be written in or be pre-processed into Linda; the language is intended to be a maximally powerful, flexible and expressive vehicle for distributed programming. The role of SBN's hardware and communication software is to support Linda with greatest possible efficiency, or in other words to implement a maximally-efficient Linda machine. Part I discusses the Linda design, which encompasses unusual inter-process communication primitives and program-structuring devices. Inter-process communication takes place via a shared data called structured Though logically shared, memory may be implemented over many memory-disjoint nodes. Processes in Linda communicate by means of the three operations that memory defines. Linda's four basic structuring tools allow the construction of a large variety of program components--sequential, concurrent and mutual-exculsion statements, tasks, remote-procedure-like blocks and monitor-like blocks, conditional and timed receives among others. Part II discusses algorithms to be incorporated in a communication system that supports Linda and memory. Runtime rendez-vous between outputting and inputting processes is a requirement of Linda and an implementation technique that is optimal given well-defined assumptions is described. Store-and-forward deadlock is a potential problem in any packet-swtiching communication system, and SBN is a packet-switching design; a new algorithm for packet deadlock prevention is described and its correctness is proven. Finally, a new communication protocol and associated architecture that, we argue, are well-suited to network computers of SBN's class is discussed.