Most algorithms for constructing minimal spanning trees are sequential in operation. Distributed algorithms for constructing these trees operate both concurrently and asynchronously, and are useful in store-and-forward packet-switching computer-communication networks where there is typically no single source of control. The difficulties in designing such algorithms arise from communication and synchronization problems. This paper discusses these problems and describes the first distributed algorithm for constructing minimal spanning trees. This algorithm and the principles and techniques underlying its design will find application in large communication networks and large multiprocessor computer systems.

The problem of naming and locating objects in a distributed environment is considered, and the clearinghouse, a decentralized agent for supporting the naming of these "network-visible" objects, is described.The objects "known" to the clearinghouse are of many types and include workstations, file servers, print servers, mail servers, clearinghouse servers, and human user.All objects known to the clearinghouse are named using the same convention, and the clearinghouse provides information about objects in a uniform fashion, regardless of their type.The clearinghouse also supports aliases.The clearinghouse binds a name to a set of properties of various types.For instance, the name of a user may be associated with the location of his local workstation, mailbox, and nonlocation information such as password and comments.The clearinghouse is decentralized and replicated.That is, instead of one global clearinghouse server, there are many local clearinghouse servers, each storing a copy of a portion of the global database.The totality of services supplied by these clearinghouse servers is called "the clearinghouse."Decentralization and replication increase efficiency, security, and reliability.A request to the clearinghouse to bind a name to its set of properties may originate anywhere in the system and be directed to any clearinghouse server.A clearinghouse client need not be concerned with the question of which clearinghouse server actually contains the binding--the clearinghouse stub in the client in conjunction with distributed clearinghouse servers automatically fmds the mapping ff it exists.Updates to the various copies of a mapping may occur asynchronously and be interleaved with requests for bindings of names to properties; updates to the various copies are not treated as indivisible transactions.Any resulting inconsistency between the various copies is only transient: the clearinghouse automatically arbitrates between conflicting updates to restore consistency.

The Pilot operating system is designed for the personal computing environment. It provides a basic set of services within which higher-level programs can more easily serve the user and/or communicate with other programs on other machines. Pilot omits certain functions sometimes associated with “complete” operating systems, such as character-string naming or user-command interpretation; higher-level software provides such facilities as needed. On the other hand, Pilot provides a higher level of service than that normally associated with the “kernel” or “nucleus” of an operating system. Pilot is closely coupled to the Mesa programming language and runs on a rather powerful personal computer, which would have been thought sufficient to support a substantial timesharing system of a few years ago. The primary user interface is a high resolution bit-map display, with a keyboard and a pointing device. Secondary storage generally takes the form of a sizable local disk. A local packet network provides a high bandwidth connection to other personal computers, and to server systems offering such remote services as printing and shared file storage.