This paper deals with the problems of specifying, composing, reasoning about, and implementing collaborative Internet-based applications. As the use of the Internet for collaboration continues to grow, the class of problems associated with such applications becomes increasingly important. The issues encountered in designing such applications are somewhat different from those encountered in traditional structured distributed systems. This section motivates work on these problems.
Traditional distributed systems (e.g., air-traffic control), are constructed with reliability in mind; for such systems, the consequences of failure would be disastrous. To ensure reliability control, such a system is developed and maintained with the overall responsibility designated to a single agency (in the case of our example, the Federal Aviation Administration). By contrast, a collaborative application on the Internet may be composed of many program units developed by different groups of people. For such distributed systems, no single agency assumes overall responsibility for reliability control. For convenience, we refer to the former kind of concurrent system as structured, as opposed to the latter kind, which we call anarchic.
Figure 1 provides a small application that illustrates the problems of specifying, composing, reasoning about, and implementing collaborative Internet-based applications. Suppose an interest group on collaborative applications is considering holding a ``Birds of a Feather'' (BOF) meeting at the HICSS conference. Each site-appointed secretary polls the group members to determine (a) whether they will be attending HICSS, and (b) if they are attending, the evenings during which they can attend a BOF meeting. Then, the secretaries coordinate with each other, generating a few potential meeting times, and each secretary checks with its respective group members about selecting one. This procedure may have to be repeated until the group converges on a date, or until they decide that no date is acceptable to a quorum of the members.
Figure 1: People at three different universities want to
decide on a time to meet. Typically, this decision is achieved by
appointing one or more secretaries to coordinate polling and meeting time
selection.
Presently, the procedure of choosing a BOF meeting time is usually carried out by email. An alternative approach is to carry out this procedure automatically using a distributed program (that might also verify with the group members as a final step). Our work is concerned with the theories and tools that facilitate developing such a distributed program. Next, we present a few examples of structured concurrent systems, and identify the issues that make anarchic systems different.
Four very different applications that can be developed using the theories and tools of structured concurrent systems are: an air-traffic control system, a parallel simulation of fluid flow, a tool that enables computer-aided design of VLSI chips, and a database server with a collection of clients that perform queries and updates. Some of the issues that are different when developing anarchic applications (such as an automatic BOF meeting time scheduler) are:
By contrast, all of the processes on the Internet that modify calendars might not be drawn from the same specification. In the BOF example in Figure 1, there might not be a single agency responsible for designing and implementing the calendar processes of all the BOF members in the Internet.
By contrast, a collaborative distributed application developer might not know which processes are going to interact before the interaction itself begins. Specifically, by providing a publicly accessible program interface available on the Internet, the developer allows interactions to occur between the local program and any other process on the Internet cognizant of that interface. A user of the program may have to figure out where a component (e.g., the calendar scheduling process of the BOF secretary) is located. Also, components can allow different checkable access privileges to various other components.
In the anarchic case, the components are given, and the task is to compose them to achieve some end. The application developer needs to determine whether components have compatible interfaces, and whether the components can be composed in a meaningful way. If they cannot be composed, the developer must address whether they can be refined in a straightforward way, so that composition is feasible.
A specific concern of our research is developing the infrastructure that supports structuring distributed applications by composing components using sequential, choice, and parallel composition, in the anarchic environment of unforeseen applications and unpredicted interactions.
We suggest program component units that can be composed in systematic ways to create structured distributed applications. We propose two kinds of compositional units, processes and sessions, and demonstrate properties of these units in the context of other work done on the theory of composition.
Processes can be composed in parallel, and we reason about processes using theories of parallel composition in temporal logic [CM88, Lam94]. Sessions are collections of processes composed in parallel [AL93, Cha94]. A session is specified in terms of the precondition and postcondition predicates [Hoa69] of its component processes. Sessions can be composed using sequential and choice composition, and we reason about sessions using theory from the field of sequential programming [DS90]. Distributed applications can be structured by nesting processes and sessions, and our software infrastructure [CRS96] supports such capability.
We model every program, appliance, and document connected to the Internet with a state that is persistent for the lifetime of its corresponding entity, as shown in Figure 2. In this model, as in any state-based approach, the execution of a system is regarded as a sequence of states, where a state is an assignment of values to a set of variables.
Figure 2: State is encapsulated in the persistent
files of an entity's corresponding process. A process is a persistent
object that may be multithreaded. Interfaces to other processes provide
a mechanism for reliably transferring requests to modify local state.
Given this model, we propose an infrastructure that supports the systematic modification of the states of arbitrary collections of entities. Specific questions that we explore include the following. How are processes and sessions specified? What is the interface between processes? How does a programmer deal with different processes having different capabilities with respect to other processes? What is parallel composition, i.e., how can processes be composed together? What are the rules that determine that processes can be composed, and what can be done if these rules are not satisfied? How can process types and specific instances of processes be found on the Internet? How are sessions composed, and how can sessions be nested within processes?
Our programming model is different from the traditional model used in distributed systems: each appliance and document on the Internet has a corresponding state, and access to this state is handled by a controlling process. As a result, our overall distributed system may have millions of persistent objects and hundreds of thousands of concurrent sessions. One of the issues addressed in this paper is the provision of a programming model that has large numbers of processes while using limited resources.
One way in which collaboration among many processes can occur is by using the client-server paradigm: all processes are clients of a server process that is responsible for coordination. An alternative manner of collaboration is to have peer-to-peer interaction among processes, for which all processes are responsible for coordination. We conjecture that our programming model could handle both client-server and peer-to-peer interactions, though the focus in this paper is on peer-to-peer communication.
Our Caltech group is designing and implementing an infrastructure [CRS96] based on the models and theories of structured composition discussed in this paper. The infrastructure allows application developers to design and implement collaborative processes and sessions over the Internet. Our implementation uses standard platforms that are widely available: Java [GJS96], TCP/IP [Ste94], and the World Wide Web [BLCGP92]. The focus of our research, however, is on basic ideas about composition applicable to any collaborative distributed system. As discussed in Section 5, CORBA [Obj95] can be employed to obtain a more elegant implementation, but our current system does not use this technology.