rfc708.txt

RFC 相关的技术文档

Network Working Group				James E. White
Request for Comments:  708			Augmentation Research Center



             Elements of a Distributed Programming System











                           January 5, 1976

                            James E. White
                     Augmentation Research Center

                     Stanford Research Institute
                    Menlo Park, California  94025

                         [phone] X2960







This paper suggests some extensions to the simple Procedure Call Protocol
described in a previous paper (27197).  By expanding the procedure call
model and standardizing other common forms of inter-process interaction,
such extensions would provide the applications programmer with an even
more powerful distributed programming system.

The work reported here was supported by the Advanced Research Projects
Agency of the Department of Defense, and by the Rome Air Development 
Center of the Air Force.

This paper will be submitted to publication in the Journal of Computer
Languages.


Network Working Group		James E. White
Request for Comments:  708	Elements of a Distributed Programming System



                             INTRODUCTION


In a companion paper [i], the author proposes a simple protocol and
software framework that would facilitate the construction of distributed
systems within a resource-sharing computer network by enabling distant
processes to communicate with one another at the procedure call level.
Although of great utility even in its present form, this rudimentary
"distributed programming system (DPS)" supports only the most fundamental
aspects of remote procedure calling.  In particular, it permits the
caller to identify the remote procedure to be called, supply the 
necessary arguments, determine the outcome of the procedure, and recover 
its results.  The present paper extends this simple procedure call model
and standardizes other common forms of process interaction to provide
a more powerful and comprehensive distributed programming system.  The
particular extensions proposed in this paper serve hopefully to reveal the 
DPS concept's potential, and are offered not as dogma but rather as
stimulus for further research.

The first section of this paper summarizes the basic distributed
programming system derived in [1].  The second section describes the
general strategy to be followed in extending it.  The third and longest
section identifies and explores some of the aspects of process interaction
that are sufficiently common to warrant standardization, and suggests
methods for incorporating them in the DPS model.



                      REVIEWING THE BASIC SYSTEM


The distributed programming system derived in [1] assumes the existence
of and is built upon a network-wide "inter-process communication (IPC)"
facility.  As depicted in Figure 1, DPS consists of a high-level model of
computer processes and a simple, application-independent "procedure
call protocol (PCP)" that implements the model by regulating the dialog
between two processes interconnected by means of an IPC communication 
"channel."  DPS is implemented by an installation-provided "run-time 
environment (RTE)," which is link loaded with (or otherwise made
available to) each applications program.






                                   -1-

Network Working Group					      James E. White
Requests for Comments:  708	Elements of a Distributed Programming System
					         Reviewing the Basic System



The Model

The procedure call model (hereafter termed the Model) views a process as a
collection of remotely callable subroutines or "procedures."  Each procedure
is invoked by name, can be supplied a list of arguments, and returns to its
caller both a boolean outcome, indicating whether it succeeded or failed,
and a list of results.  The Model permits the process at either end of the 
IPC channel to invoke procedures in its neighbor, and further permits a
process to accept two or more procedure calls for concurrent execution.

The arguments and results of procedures are modeled from a small set of
primitive "data types," listed below:

	LIST:  A list is an ordered sequence of N data objects called
	"elements" (here and throughout these descriptions, N is	
	confined to the range [0, 2**15-1]).  A LIST may contain
	other LISTs as elements, and can therefore be employed to
	construct arbitrarily complex, composite arguments or results.

	CHARSTR:  A character string is an ordered sequence of N ASCII
	characters, and conveniently models a variety of textual
	entities, from short user names to whole paragraphs of text.

	BITSTR:  A bit string is an ordered sequence of N bits and,
	therefore, provides a means for representing arbitrary
	binary data (for example, the contents of a word of memory).

	INTEGER:  An integer is a fixed-point number in the range
	[-2**31, 2**31-1], and conveniently models various kinds of
	numerical data, including time intervals, distances, and so on.

	INDEX:  An index is an integer in the range [1, 2**15-1].  As
	its name and value range suggest, an INDEX can be used to
	address a particular bit of character within a string, or 
	element within a list.  Furthermore, many of the protocol
	extensions to be proposed in this paper will employ INDEXES as
	handles for objects within the DPS environment (for example,
	processes and channels).

	BOOLEAN:  A boolean represents a single bit of information
	and has either the value  true or false.

	EMPTY:  An empty is a valueless place holder within a LIST of
	parameter list.


                                     -2-

Network Working Group					      James E. White
Requests for Comments:  708	Elements of a Distributed Programming System
						  Reviewing the Basic System


The Protocol

The procedure call protocol (hereafter terms the Protocol), which
implements the Model, defines a "transmission format" (like those suggested
in Appendix A) for each of the seven data types listed above, and
requires that parameters be encoded in that format whenever they are
transported between processes.

The Protocol also specified the inter-process messages by which remote
procedures are invoked.  These messages can be described symbolically as
follows:

	message-type=CALL	[tid] procedure-name arguments
	message-type=RETURN      tid  outcome        results

The first message invokes the procedure whose NAME is specified using the
ARGUMENTS provided.  The second is returned in eventual response to the
first and reports the OUTCOME and RESULTS of the completed procedure.
Whenever OUTCOME indicates that a procedure has failed, the procedure's 
RESULTS are required to be an error number and diagnostic message, the 
former to help the invoking program determine what to do next, the 
latter for possible presentation to the user.  The presence of an
optional "transaction identifier (TID)" in the CALL message constitutes
a request by the caller for an acknowledging RETURN message echoing the
identifier.

Although data types and their transmission formats serve primarily as
vehicles for representing the arguments and results of remote procedures,
they can just as readily and effectively be employed to represent the
messages by which those parameters are transmitted.  The Protocol,
therefore, represents each of the two messages described above as a PCP 
data object, namely, a LIST whose first element is an INDEX message
type.  The following concise statement of the Protocol results:

	LIST (CALL,   tid,    procedure, arguments)
              INDEX=1 [INDEX] CHARSTR    LIST
	LIST (RETURN, tid,    outcome,   results)
	      INDEX=2 INDEX   BOOLEAN    LIST

Here and in subsequent protocol descriptions, elements enclosed in square
brackets are optional (that is, may be EMPTY).  The RESULTS of an
unsuccessful procedure would be represented as follows:

	LIST (error, diagnostic)
	      INDEX  CHARSTR



                                    -3-

Network Working Group					      James E. White
Requests for Comments:  708	Elements of a Distributed Programming System
					          Reviewing the Basic System



The Run-Time Environment

The run-time environment (hereafter termed the environment) interfaces the
applications program to a remote process via an IPC channel.  In doing so,
it provides the applications program with a collection of "primitives,"
implemented either as subroutines or system calls, that the applications
program can employ to manipulate the remote process to which the channel
connects it.  The environment implements these primitives by sending
and receiving various protocol messages via the channel.

In its present rudimentary form, the Protocol enables the environment to
make a single, remote procedure calling primitive like the following
available to the applications program:

	CALLPROCEDURE (procedure, arguments -> outcome, results)
		       CHARSTR    LIST         BOOLEAN  LIST

This primitive invokes the indicated remote PROCEDURE using the ARGUMENTS
provided and returns its OUTCOME and RESULTS.  While this primitive
blocks the invoking applications program until the remote procedure
returns, a variant that simply initiates the call and allows the
applications program to collect the outcome and results in a second
operation can also be provided.

Since the interface between the environment and the applications program
is machine- and possibly even language-dependent, environment-provided
primitives can only be described in this paper symbolically.  Although
PCP data types provide a convenient vehicle for describing their
arguments and results are therefore used for that purpose above and
throughout the paper, such parameters will normally be transmitted
between the environment and the applications program in some internal
format.


               BOOTSTRAPPING THE NEW PROTOCOL FUNCTIONS


Since the Protocol already provides a mechanism for invoking arbitrary
remote procedures, the Model extensions to be proposed in this paper
will be implemented whenever possible as procedures, rather than as
additional messages.  Unlike applications procedures, these special
"system procedures" will be called and implemented by run-time environments, 
rather than by the applications programs they serve.  Although inaccessible
to the remote applications program via the normal environment-provided
remote procedure calling primitive, system procedures will enable the
environment to implement and offer new primitives to its applications
program.
                                    -4-


Network Working Group					      James E. White
Requests for Comments:  708	Elements of a Distributed Programming System
				    Bootstrapping the New Protocol Functions



The calling sequences of many of these new primitives will closely
correspond to those of the remote system procedures by which they are
implemented.  Other primitives will be more complex and require for their
implementation calls to several system procedures, possibly in different
processes.  Besides describing the Protocol additions required by various
Model extensions proposed, the author will, throughout this paper, suggest
calling sequences for the new primitives that become available to the 
applications program.





































                                       -5-

Network Working Group					      James E. White
Request for Comments:  708	Elements of a Distributed Programming System
				       Some Possible Extensions to the Model



                SOME POSSIBLE EXTENSIONS TO THE MODEL


1.  Creating Remote Processes

Before a program in one machine can use resources in another, it must either
create a new process in the remote machine, or gain access to an existing
one.  In either case, the local process must establish an IPC channel to a
resident dispatching process within the remote system, specify the program 
to be started or contacted. and identify itself so that its access to the
program can be established and billing carried out.  After these preliminary
steps have been accomplished, the requested process assumes responsibility
for the IPC channel and substantive communication begins.

The manner in which the environment carries out the above scenario is
largely dictated by the IPC facility upon which the distributed system is
based.  If the IPC facility itself provides single primitive that
accomplishes the entire task, then the environment need only invoke that
primitive.  If, on the other hand, it only provides a mechanism by which
the environment can establish a channel to the remote dispatcher, as is
the case within the ARPA computer Network (the ARPANET), then the Protocol 
itself must contain provisions for naming the program to be run and
presenting the required credential.

Adding to the Protocol the following system procedure enables the local
environment to provide the remote dispatcher with the necessary information
in this latter case:

	INIPROCESS (program, credential)
		    CHARSTR  LIST (user,   password, account)
				   CHARSTR CHARSTR   CHARSTR

Its arguments include the name of the applications PROGRAM to be run; and
the USER name, PASSWORD, and ACCOUNT of the local user to whom its use is
to be billed.

This new procedure effectively adds to the Model the notion of "creation," and enables the environment to offer the following primitives
to its applications program:

	CRTPROCESS (computer, program, credential -> ph)
		    CHARSTR   CHARSTR  (as above)    INDEX
	DELPROCESS (ph)
		    INDEX


                                   -6-


Network Working Group						James E. White
Request for Comments:  708	  Elements of a Distributed Programming System
				         Some Possible Extensions to the Model
						     Creating Remote Processes



The first primitive creates a new process or establishes contact with an
existing one by first creating a channel to the dispatcher within the
indicated COMPUTER and then invoking the remote system procedure INIPROCESS
with the specified PROGRAM name and CREDENTIALS as arguments.  The primitive
returns a "process handle PH" by which the applications program can refer to 
the newly created process in subsequent dialog with the local environment
by the IPC facility, an index into a table within the environment, or anything
else the environment's implementor may find convenient.

The second primitive "deletes" the previously created process whose handle
PH is specified by simply deleting the IPC channel to the remote process and
reclaiming any internal table space that may have been allocated to the
process.

2.  Introducing Processes to One Another

The simplest distributed systems begin with a single process that creates,
via the CRTPROCESS primitive described above, one or more "inferior"
processes whose resources it requires.  Some or all of these inferiors may 
in turn require other remote resources and so create interiors of their
own.  This creative activity can proceed, in principle, to arbitrary depth.
The distributed system is thus a tree structure whose nodes are processes 
and whose branches are IPC channels.

Although a distributed system can include an arbitrarily large number of
processes, each process is cognizant of only the process that created it
and those it itself creates, that is, its parent and sons.  The radius
within which a process can access the resources of the tree is thus
artificially small.  This limited sharing range, which prevents the
convenient implementation of many distributed systems, can be overcome
by extending the Model to permit an arbitrarily complex network of
communication paths to be superimposed upon the process tree.

One of the many ways by which the Protocol can provide for such communication
paths is to permit one process to "introduce" and thereby make known to one 
another any two processes it itself knows (for example, two of its sons,
or its parent and son).  Once introduced, the two processes would be able 
to invoke one another's procedures with the same freedom the introducing
process enjoys.  They could also introduce one another to other processes,
and so create even longer communication paths.