    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

                             (415) 326-6200 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.

                                       -7-

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

    2.1  Introductions Within a Homogeneous Environment

    Provided one remains within a "homogeneous environment" (that is, the domain
    of a single IPC facility), the introduction of two processes requires little
    more than the formation of an IPC channel between them.  Adding to the
    Protocol the following system procedures, which manipulate IPC "ports,"
    enables the run-time environment of the process performing the introduction
    to negotiate such a channel:

            ALOPORT (-> ph,   COMPUTER, PORT)
                        INDEX CHARSTR   any
            CNNPORT (ph,   computer, port)
                     INDEX CHARSTR   any
            DCNPORT (ph)
                     INDEX

    The detailed calling sequences for these procedures are dictated by the IPC
    facility that underlies the distributed system.  Those above are therefore
    only representative of what may be required within any particular network,
    but are only slightly less complicated than those required, for example,
    within the ARPANET.

    To create the channel, the introducing process' run-time environment
    allocates a PORT in each target process via ALOPORT, and then instructs
    each process via CNNPORT to connect its port to the other's via the IPC
    facility.  The process handle PH returned by ALOPORT serves as a handle
    both initially for the allocated port, and then later for the process to
    which the attached channel provides access.  To "separate" the two processes,
    the introducing process' environment need only invoke the DCNPORT procedure
    in each process, thereby dissolving the channel, releasing the associated
    ports, and deallocating the process handles.

    Armed with these three new system procedures, the environment can provide
    the following new primitives to its applications program:

            ITDPROCESS (ph1,  ph2 -> ph12, PH21, ih)
                        INDEX INDEX  INDEX INDEX INDEX
            SEPPROCESS (ih)
                        INDEX

                                       -8-

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

    The first primitive introduces the two processes whose handles PH1 and PH2
    are specified.  Each handle may designate either a son, in which case the
    handle is one returned by CRTPROCESS; the parent process, for which a
    special handle (for example, 1) must always be defined; or a previously
    introduced process, in which case the handle is one obtained in a previous
    invocation of ITDPROCESS.

    ITDPROCESS returns handles PH12 and PH21 by which the two processes will
    know one another, as well as an "introduction handle IH" that the applications
    program can later employ to separate the two processes via SEPPROCESS.  The
    applications program initiating the introduction assumes responsibility for
    communicating to each introduced applications program its handle for the
    other.

    2.2  Introductions Within a Heterogeneous Environment

    While their interconnection via an IPC channel is sufficient to introduce
    two processes to one another, in a heterogeneous environment the creation
    of such a channel is impossible.  Suppose, as depicted in Figure 2, that
    processes P1 and P2 (in computers C1 and C2, respectively) are interconnected
    within a distributed system by means of a network IPC facility.  Assume
    further that P2 attaches to the system another process P3 in a minicomputer
    M that although attached to C2 is not formally a part of the network.  With
    this configuration, it is impossible for P2 to introduce processes P1 and P3
    to one another by simply establishing an IPC channel between them, since
    they are not within the domain of a single IPC facility.

    One way of overcoming this problem is to extend the Model to embrace the
    notion of a composite or "logical channel" composed of two or more physical
    (that is, IPC) channels.  A message transmitted by process P1 via the logical
    channel to Pn (n=3 in the example above) would be relayed over successive
    physical channels by the environments of intermediate processes P2 through
    Pn-1.  Although more expensive than physical channels, since each message
    must traverse at least two physical channels and be handled by all the
    environments along the way, logical channels would nevertheless enable
    processes that could not otherwise do so to access one another's resources.
    Since the relaying of messages is a responsibility of the environment, the
    applications program need never be aware of it.

                                       -9-

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

    As depicted in Figure 3, a logical channel would consist of table entries
    maintained by the environment of each process P1 through Pn, plus the
    environment to forward messages that arrive with a "routing code" addressing
    the local table entry.  Each table entry would contain process handles for
    the two adjacent processes, as well as the routing code recognized by each.
    To communicate a message to its distant neighbor, the source process (say
    P1) would transmit it via its IPC channel to P2, with a routing code
    addressing the appropriate table entry within P2.  Upon receipt of the
    message, P2 would locate its table entry via the routing code, update the
    message with the routing code recognized by P3, and forward the message
    to P3.  Eventually the message would reach its final destination, Pn.

    Adding to the Protocol the following system procedures enables the
    environment to construct a logical channel like that described above:

            CRTROUTE (mycode, oldcode -> code, ph)
                      INDEX   [INDEX]    INDEX INDEX
            DELROUTE (yourcode)
                      INDEX

    The simplest logical channel (n=3) is created by P2, which invokes CRTROUTE
    in both P1 and P3, specifying in each case the routing code MYCODE it has
    assigned to its segment of the logical channel, and receiving in return
    the routing CODES and process handles PHs assigned by the two processes.
    OLDCODE is not required in this simple case and is therefore EMPTY.

    More complicated logical channels (n>3) are required when one or both
    of the processes to be introduced is already linked, by a logical channel,
    to the process performing the introduction.  In such cases, a portion of
    the new channel to be constructed must replicate the existing channel, and
    hence the routing code OLDCODE for the table entry that represents that
    channel within the target process is specified as an additional argument
    of the system procedure.  The target process must call CRTROUTE recursively
    in the adjacent process to replicate the rest of the model channel.

                                     -10-

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

    The process Pi that creates a logical channel assumes responsibility for
    insuring that it is eventually dismantled.  It deletes the logical channel
    by invoking DELROUTE in Pi-1 and Pi+1, each of which propagates the call
    toward its end of the channel.

    3.  Controlling Access to Local Resources

    The process introduction primitive proposed above effectively permits
    access to a process to be transmitted from one process to another.  Any
    process P2 that already possesses a handle to a process P1 can obtain a
    handle for use by a third process P3.  Once P1 and P3 have been introduced,
    P3 can freely call procedures in P1 (and vice versa).

    Although a process can, by aborting the ALOPORT system procedure, prevent
    its introduction to another process and so restrict the set of processes
    that gain access to it, finer access controls may sometimes be required.
    A process may, for example, house two separate resources, one of which
    is to be made available only to its parent (for example), and the other
    to any process to which the parent introduces it.  Before such a strategy
    can be conveniently implemented, the Model must be extended to permit
    access controls to be independently applied to individual resources within
    a single process.

    Although a single procedure can be considered a resource, it is more practical and convenient to conceive of larger, composite resources
    consisting of a number of related procedures.  A simple data base
    management module containing procedures for creating, deleting, assigning
    values to, reading, and searching for data objects exemplifies such
    composite resources.  Although each procedure is useless in isolating, the
    whole family of procedures provides a meaningful service.  Such "package"
    of logically related procedures might thus be the most reasonable object
    of the finer access controls to be defined.

    Access controls can be applied to packages by requiring that a process
    first "open" and obtain a handle for a remote package before it may call
    any of the procedures it contains.  When the process attempts to open
    the package, its right to do so can be verified and the attempt aborted if
    necessary.  Challenging the open attempt would, of course, be less expensive
    than challenging every procedure call.  The opening of a package would also
    provide a convenient time for package-dependent state information to be
    initialized.

                                     -11-

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

    Adding to the Protocol the following pair of system procedures enables the
    environment to open and close packages within another process.  For
    efficiency, these procedures manipulate an arbitrary number of packages
    in a single transaction.

            OPNPACKAGE (packages ->    pkhs)
                        LISTofCHARSTRs LISTofINDEXs
            CLSPACKAGE (pkhs)
                       (as above)

    The first procedure opens and returns "package handles PKHS" for the
    specified PACKAGES; the second closes one or more packages and releases
    the handles PKHS previously obtained for them.

    Besides incorporating these two new system procedures, the Protocol must
    further require that a package handle accompany the procedure name in every
    CALL message (an EMPTY handle perhaps designating a system procedure).  Note
    that this requirement has the side effect of making the package the domain
    within which procedure names must be unique.

    The system procedures described above enable the environment to make
    available to its applications program, primitives that have calling
    sequences similar to those of the corresponding system procedures but
    which accept the process handle of the target process as an additional
    argument.  Their implementation requires only that the environment
    identify the remote process from its internal tables and invoke OPNPACKAGE
    or CLSPACKAGE in that process.

    4.  Standardizing Access to Global Variables

    Conventional systems often maintain global "variables" that can be accessed
    by modules throughout the system.  Such variables are typically manipulated
    using primitives of the form:

        (1)  Return the current value of V.
        (2)  Replace the current contents of V with a new value.

    These primitives are either provided as language constructs or implemented
    by specialized procedures.  The former approach encourages uniform
    treatment of all variables within the system.

    Those distributed systems that maintain remotely-accessible variables must
    also select a strategy for implementing the required access primitives.
    While such primitives can, of course, be implemented as specialized

                                         -12-

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

    applications procedures, adding to the Protocol the following new system
    procedures insures a uniform run-time access mechanism:

            RDVARIABLE (pkh,  variable -> value)
                        INDEX CHARSTR     any
            WRVARIABLE (pkh,  variable, value)
                        INDEX CHARSTR   any

    These procedures effectively define variables as named data objects modeled
    from PCP data types, and suggest that they be clustered in packages with
    related procedures.  The system procedures return and specify, respectively,
    the VALUE of the VARIABLE whose name and package handle PKH are specified.

    These new procedures enable the environment to make available its applications
    program, primitives that have calling sequences similar to those of the
    corresponding system procedures but which accept the process handle of the
    target process as an additional argument.  These primitives provide a basis
    upon which a suitably modified compiler can reestablish the compile-time
    uniformity that characterizes the manipulation of variables in conventional
    programming environments.  Their implementation requires only that the local
    environment identify the remote process from its internal tables and invoke
    RDVARIABLE or WRVARIABLE in that process.

    Most variables will restrict the range of data types and values that may be
    assigned to them; some may even be read-only.  But because they are modeled
    using PCP data types, their values can, in principle, be arbitrarily complex
    (for example, a LIST of LISTS) and the programmer may sometimes wish to
    manipulate only a single element of the variable (or, if the element is
    itself a LIST, just one of its elements; and so on, to arbitrary depth).

    Adding the following argument to their calling sequences extends the system
    procedures proposed above to optionally manipulate a single element of a
    variable's composite value:

            substructure
            (LISTofINDEXs)

    At successive levels of the value's tree structure, the INDEX of the desired
    element is identified; the resulting list of indices identifies the
    SUBSTRUCTURE whose value is to be returned or replaced.

                                         -13-

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

    5.  Routing Parameters Between Procedures

    In conventional programming systems, the results of procedures are used in a
    variety of ways, depending upon the context of the calls made upon them.  A
    result may, for example:

            (1)  Provide the basis for a branch decision within the calling
                 program.
            (2)  Become an argument to a subsequent procedure call.
            (3)  Be ignored and thus effectively discarded.

    At run-time, the knowledge of a result's intended use usually lies solely
    within the calling program, which examines the results, passes it to a
    second procedure, or ignores it as it chooses.

    In a distributed system, the transportation of results from callee to caller,
    carried out by means of one of more inter-process messages, can be an
    expensive operation, especially when the results are large.  Data movement
    can be reduced in Cases 2 and 3 above by extending the Model to permit the
    intended disposition of each procedure result to be made known in advance
    to the callee's environment.  In Case 2, provided both callees reside
    within the same process, the result can be held at its source and later
    locally supplied to the next procedure.  In Case 3, the result can be
    discarded at its source (perhaps not even computed), rather than sent and
    discarded at its destination.

    5.1  Specifying Parameters Indirectly

    Variables offer potential for the eliminating the inefficiencies involved in
    Case 2 above by providing a place within the callees' process where results
    generated by one procedure can be held until required by another.  The
    Protocol can be extended to permit variables to be used in this way by
    allowing the caller of any procedure to include optional "argument- and
    result-list mask" like the following as additional parameters of the CALL
    message:

            parameter list mask
            [LIST variable, ...)]
                  [CHARSTR]

    A parameter list mask would permit each parameter to be transmitted either
    directly, via the parameter list, or indirectly via a VARIABLE within the
    callee's process.  Thus each element of the mask specifies how the callee's

                                        -14-

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

    environment is to obtain or dispose of the corresponding parameter.  To supply
    the result of one procedure as an argument to another, the caller need only
    then appropriately set corresponding elements of the result and argument
    list masks in the first and second calls, respectively.  The result list
    mask should be ignored if the procedure fails, and the error number and
    diagnostic message returned directly to the caller.

    5.2  Providing Scratch Variables for Parameter Routing

    Although each applications program could provide variables for use as described
    above, a more economical approach is to extend the Model to permit special
    "scratch variables," maintained by the environment without assistance from
    its applications program, to be created and deleted as necessary at run-time.
    Adding to the Protocol the following pair of system procedures enables the
    local environment to create and delete such variables in a remote process:

            CRTVARIABLE (variable, value)
                         CHARSTR   any
            DELVARIABLE (variable)
                         CHARSTR

    These procedures create and delete the specified VARIABLE, respectively.
    CRTVARIABLE also assigns an initial VALUE to the newly-created variable.

    These new procedures enable the environment to make available to its
    applications program, primitives that have calling sequences similar to
    those of the corresponding system procedures but which accept the process
    handle of the target process as an additional argument.  Their implementation
    required only that the environment identify the remote process from its
    internal tables and invoke CRTVARIABLE or DELVARIABLE in that process.

    5.3  Discarding Results

    The inefficiencies that result in Case 3 above are conveniently eliminated
    by allowing the caller to identify via the result list mask (for example,
    via a zero-length CHARSTR) that a result will be ignored and therefore need
    not be returned to the caller.

                                        -15-

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

    6.  Supporting a Richer Spectrum of Control Transfers

    As currently defined by the Model, a procedure call is a simple two-stage
    dialog in which the caller first describes the operation it wishes performed
    and the callee, after performing the operation, reports its outcome.
    Although this simple dialog form is sufficient to conveniently implement
    a large class of distributed systems, more complex forms are sometimes
    required.  The Model can be extended to admit a variety of more powerful
    dialog forms, of which the four described below are examples.

    6.1  Transferring Control Between Caller and Callee

    Many conventional programming systems permit caller and callee to exchange
    control any number of times before the callee returns.  Such "coroutine
    linkages" provide a means, for example, by which the callee can obtain
    help with a problem that it has encountered or deliver the results of one
    suboperation and obtain the arguments for the next.

    Adding to the Protocol the following system procedure, whose invocation
    relinquishes control of another, previously initiated procedure, enables
    the environment to effect a coroutine linkage between caller and callee:

            TAKEPROCEDURE (tid,  yourtid, parameters)
                           INDEX BOOLEAN  LIST

    Its arguments include the identifier TID of the affected transaction, an
    indication YOURTID of from whose name space the identifier was assigned
    (that is, whether the process relinquishing control is the caller or callee),
    and PARAMETERS provided by the procedure surrendering control.  By exploiting
    an existing provision of the Protocol (that is, by declining acknowledgment
    of its calls to TAKEPROCEDURE) the invoking environment can effect the
    control transfer with a single inter-process message.

    The addition of this new procedure to the Protocol enables the environment
    to provide the following new primitive to its applications program:

            LINKPROCEDURE (tid,  arguments -> outcome,  results)
                           INDEX LIST         [BOOLEAN] LIST

                                      -16-

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

    This primitive assumes that the CALLPROCEDURE primitive is also modified to
    return the pertinent transaction identifier should the callee initiate a
    coroutine linkage rather than return.  Invocation of LINKPROCEDURE then
    continues the dialog by supplying ARGUMENTS and returning control to the remote
    procedure, and then awaiting the next transfer of control and the RESULTS that
    accompany it.  If the remote procedure then returns, rather than initiating
    another coroutine linkage, the primitive reports its OUTCOME and invalidates
    the transaction identifier.

    While this primitive blocks the applications program until the remoter
    procedure relinquishes control, a variant that simply initiates the coroutine
    linkage and allows the applications program to collect the outcome and
    results in a second operation can also be provided.

    6.2  Signaling the Caller/Callee

    A monolog is often more appropriate than the dialog initiated by a coroutine
    linkage.  The caller or callee might wish, for example, to report an event it
    has detected or send large parameters piecemeal to minimize buffering
    requirements.  Since no return parameters are required in such cases, the
    initiating procedure need only "signal" its partner, while retaining control
    of the call.

    Adding to the Protocol the following system procedure extends the Model to
    support signals and enables the environment to transmit parameters to or
    from another, previously initiated procedure without relinquishing control
    of the call:

            SGNLPROCEDURE (tid,  yourtid, parameters)
                           INDEX BOOLEAN  LIST

    Like the TAKEPROCEDURE procedure already described, its arguments include
    the identifier TID of the affected transaction, an indication YOURTID of
    from whose name space the identifier was assigned, and the PARAMETERS
    themselves.

    This new procedure enables the environment to make available to its
    applications program a primitive that has a calling sequence similar to that
    of the system procedure but which does not require YOURTID as an argument.
    Its implementation requires only that the environment identify the remote
    process via its internal tables and invoke SGNLPROCEDURE in that process.

                                        -17-

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

    By requesting the acknowledgment of each call to SGNLPROCEDURE and, if
    necessary, delaying subsequent calls affecting the same transaction until
    the acknowledgment arrives, the invoking environment effects a crude form of
    flow control and so prevents the remote process' buffers from being overrun.

    6.3  Soliciting Help from Superiors

    As in conventional programming systems, remotely callable procedures within
    a distributed system will sometimes call upon others to carry out portions
    of their task.  Each procedure along the "thread of control" resulting from
    such nested calls is, in a sense, responsible to not only its immediate caller
    but also to all those procedures that lie above it along the control thread.
    To properly discharge its responsibilities, a procedure must sometimes
    communicate with these "superiors."

    Occasionally a procedure reaches a point in its execution beyond which it
    cannot proceed without external assistance.  It might, for example, require
    additional resources or further direction from the human user upon whose
    behalf it is executing.  Before reaching this impasse, the procedure may
    have invested considerable real and/or processing time that will be lost
    if it aborts.

    Adding to the Protocol the following system procedure minimizes such
    inefficiencies by enabling the environment to solicit help from a callee's
    superiors:

            HELPPROCEDURE (tid,  number, information -> solution)
                           INDEX INDEX   any            any

    Its arguments include the identifier TID of the affected transaction (the
    direction of the control transfer being implicit in this case), a NUMBER
    identifying the problem encountered, and arbitrary supplementary
    INFORMATION.

    The primitive that this new procedure enables the environment to provide
    its applications program has an identical calling sequence.  Its implementation
    requires only that the environment identify the remote process from its
    internal tables and invoke HELPPROCEDURE in that process.

    The search for help begins with invocation of HELPPROCEDURE in the caller's
    environment.  If the caller understands the problem (that is, recognizes

                                         -18-

    Network Working Group                                           James E. White
    Request for Comments:  708         Elements of a Distributed Programming Model
                                 Supporting a Richer Spectrum of Control Transfers

    its number) and is able to solve it, HELPPROCEDURE will simply return whatever
    SOLUTION information the caller provides.  Otherwise, HELPPROCEDURE must give
    the next superior an opportunity to respond by calling itself recursively in
    that process.  The search terminates as soon as a superior responds positively
    or when the end of the control thread is reached.  In the latter case, each of
    the nested HELPPROCEDURE procedures returns unsuccessfully to indicate to its
    caller that the search failed.

    6.4  Reporting an Event to Superiors

    A procedure sometimes witnesses or causes an event of which its superiors
    should be made aware (for example, the start or completion of some major
    step in the procedure's execution).  Adding to the Protocol the following
    system procedure enables the environment to notify a callee's superiors of an
    arbitrary event:

            NOTEPROCEDURE (tid,  number, information)
                           INDEX INDEX   any

    Like HELPPROCEDURE, its arguments include the identifier TID of the
    transaction it affects, a NUMBER identifying the event being reports, and
    arbitrary supplementary INFORMATION.

    The primitive that this new procedure enables the environment to provide its
    applications program has an identical calling sequence.  Its implementation
    requires only that the environment identify the remote process from its
    internal tables and invoke NOTEPROCEDURE in that process.

    By requesting acknowledgment of each call to NOTEPROCEDURE and, if necessary,
    delaying subsequent calls that affect that transaction until the acknowledgment
    arrives, the invoking environment effects a crude form of flow control and so
    prevents the remote process' buffers from being overrun.

    Notification of the procedure's superiors begins with invocation of
    NOTEPROCEDURE in the caller's process and works its way recursively up the
    thread of control until the top is reached.

                                         -19-

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

    7.  Aborting Executing Procedures

    Conventional systems that accept commands from the user sometimes permit him
    to cancel an executing command issued inadvertently or with erroneous
    parameters, or one for whose completion he cannot wait.  This ability is
    particularly important when the command (for example, one that compiles a
    source file) has a significant execution time.  In a distributed system, the
    execution of such a command may involve the invocation of one or more remote
    procedures.  Its cancellation, therefore, requires the abortion of any
    outstanding remote procedure calls.

    Adding to the Protocol the following system procedure provides the basis
    for a command cancellation facility by enabling the environment to abort
    another, previously invoked procedure:

            ABRTPROCEDURE (tid)
                           INDEX

    Its sole argument is the identified TID of the transaction it affects.

    The primitive that this new procedure enables the environment to make
    available to the applications program has an identical calling sequence.
    Its implementation requires only that the local environment identify the
    remote process from its internal tables and invoke ABRTPROCEDURE in that
    process.

                                     -20-

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

                                  CONCLUSION

    The EXPANDED Protocol and Model that result from the extensions proposed in
    the present paper are summarized in Appendixes B and C, respectively.
    Needless to say, many additional forms and aspects of process interaction,
    of which Appendix D suggests a few, remain to be explored.  Nevertheless,
    the primitives already made available by the run-time environment provide
    the applications programmer with a powerful and coherent set of tools for
    constructing distributed systems.

                                      -21-

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

                               ACKNOWLEDGMENTS

    Many individuals within both SRI's Augmentation Research Center (ARC) and the
    larger ARPANET community have contributed their time and ideas to the
    development of the Protocol and Model described in this and its companion
    paper.  The contributions of the following individuals are expressly
    acknowledged:  Dick Watson, Jon Postel, Charles Irby, Ken Victor, Dave Maynard,
    Larry Garlick of ARC; and Bob Thomas and Rick Schantz of Bolt, Beranek and
    Newman, Inc.

    ARC has been working toward a high-level framework for network-based
    distributed systems for a number of years now [2].  The particular Protocol
    and Model result from research begun by ARC in July of 1974.  This research
    included developing the Model; designing and documenting, and implementing
    a prototype run-time environment for a particular machine [4, 5], specifically
    a PDP-10 running the Tenex operating system developed by Bolt, Beranek and
    Newman, Inc. [6].  Three design iterations were carried out during a 12-month
    period and the resulting specification implemented for Tenex.  The Tenex RTE
    provides a superset of the capabilities proposed in this paper.

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

                                       -22-

    Network Working Group                                           James E. White
    Request for Comments:  708        Elements of a Distributed Programming System
                            Appendix A:  Transmission Formats for PCP Data Objects

                                  APPENDIX A

                  TRANSMISSION FORMATS FOR PCP DATA OBJECTS

    Data objects must be encoded in a standard transmission format before they can
    be sent from one process to another via the Protocol.  An effective strategy
    is to define several formats and select the most appropriate one at run-time,
    adding to the Protocol a mechanism for format negotiation.  Format negotiation
    would be another responsibility of the environment and could thus be made
    completely invisible to the applications program.

    Suggested below are two transmission formats.  The first is a 36-bit binary
    format for use between 36-bit machines, the second an 8-bit binary, "universal"
    format for use between dissimilar machines.  Data objects are fully typed in
    each format to enable the environment to automatically decode and internalize
    incoming parameters should it be desired to provide this service to the
    applications program.

    PCPB36, For Use Between 36-Bit Machines

            Bits  0-13 Unused (zero)
            Bits 14-17 Data type
               EMPTY  =1  INTEGER=4  LIST=7
               BOOLEAN=2  BITSTR =5
               INDEX  -3  CHARSTR=6
            Bits 18-20 Unused (zero)
            Bits 21-35 Value or length N
               EMPTY       unused (zero)
               BOOLEAN     14 zero-bits + 1-bit value (TRUE=1/FALSE=0)
               INDEX       unsigned value
               INTEGER     unused (zero)
               BITSTR      unsigned bit count N
               CHARSTR     unsigned character count N
               LIST        unsigned element count N
            Bits 36-   Value
               EMPTY    unused (nonexistent)
               BOOLEAN  unused (nonexistent)
               INDEX    unused (nonexistent)
               INTEGER  two's complement full-word value
               BITSTR   bit string + zero padding to word boundary
               CHARSTR  ASCII string + zero padding to word boundary
               LIST     element data objects

                                        -23-

    Network Working                                               James E. White
    Request for Comments:  708      Elements of a Distributed Programming System
                          Appendix A:  Transmission Formats for PCP Data Objects

    PCPB8, For Use Between Dissimilar Machines

            Byte    0  Data type
               EMPTY  =1  INTEGER=4  LIST=7
               BOOLEAN=2  BITSTR =5
               INDEX  =3  CHARSTR=6
            Bytes 1-   Value
               EMPTY      unused (nonexistent)
               BOOLEAN    7 zero-bits + 1-bit value (TRUE=1/FALSE=0
               INDEX      2 byte unsigned value
               INTEGER    4-type two's complement value
               BITSTR     2-byte unsigned bit count N + bit string
                           + zero padding to byte boundary
               CHARSTR    2-byte unsigned character count N + ASCII string
               LIST       2-byte element count N + element data objects

                                           -24-

    Network Working Group                                         James E. White
    Request for Comments:  708      Elements of a Distributed Programming System
                               Appendix B:  The Expanded Procedure Call Protocol

                                  APPENDIX B

                     THE EXPANDED PROCEDURE CALL PROTOCOL

    The Protocol that results from the extensions proposed in this paper is
    summarized below.  The reader should note the concise syntactic description
    made possible by the underlying notion of PCP data types.

    Parameter list masks have been included not only as additional parameters
    of the CALL message, as proposed in the paper, but as arguments of the
    TAKEPROCEDURE and SGNLPROCEDURE system procedures as well.  Throughout the
    Protocol description, "MASK" is shorthand for:

            [LIST (variable [CHARSTR], ...)]

    Messages

            LIST (route INDEX, opcode INDEX CALL=1, tid [INDEX],
                  pkh [INDEX], procedure CHARSTR, arguments LIST,
                  argumentlistmask MASK, resultlistmask MASK)
            LIST (route INDEX, opcode INDEX RETURN=2, tid INDEX,
                  outcome BOOLEAN, results LIST)

               If OUTCOME is FALSE
                  RESULTS is LIST (error INDEX, diagnostic CHARSTR)

    Process-Related System Procedures

            INIPROCESS (program CHARSTR,
                        credentials LIST (error CHARSTR, password CHARSTR,
                                          account CHARSTR))
            ALOPORT    (-> ph INDEX, computer CHARSTR, port)
            CNNPORT    (ph INDEX, computer CHARSTR, port)
            DCNPORT    (ph INDEX)
            CRTROUTE   (mycode INDEX, oldcode [INDEX]
                        -> code INDEX, ph INDEX)
            DELROUTE   (yourcode INDEX)

    Package-Related System Procedures

            OPNPACKAGE (packages LISTofCHARSTRs -> pkhs LISTofINDEXs)
            CLSPACKAGE (pkhs LISTofINDEXs)

                                          -25-

    Network Working Group                                         James E. White
    Request for Comments:  708      Elements of a Distributed Programming System
                               Appendix B:  The Expanded Procedure Call Protocol

    Variable-Related System Procedures

            CRTVARIABLE (variable CHARSTR, value)
            DELVARIABLE (variable CHARSTR)
            RDVARIABLE  (pkh INDEX, variable CHARSTR,
                         substructure [LISTofINDEXs] -> value)

    Procedure-Related System Procedures

            TAKEPROCEDURE (tid INDEX, yourtid BOOLEAN, parameters LIST,
                           argumentlistmask MASK, resultlistmask MASK)
            SGNLPROCEDURE (tid INDEX, yourtid BOOLEAN, parameters LIST,
                           parameterlistmask MASK)
            HELPPROCEDURE (tid INDEX, number INDEX, information -> solution)
            NOTEPROCEDURE (tid INDEX, number INDEX, information)
            ABRTPROCEDURE (tid INDEX)

                                         -26-

    Network Working Group                                           James E. White
    Request for Comments:  708               Elements of a Distributed Programming
                                            Appendix C:  Summary of RTE Primitives

                                  APPENDIX C

                          SUMMARY OF RTE PRIMITIVES

    The DPS primitives made available to the applications program as a result of
    the Model extensions proposed in this paper are summarized below.
    Collectively, they provide the applications programmer with a powerful
    and coherent set of tools for constructing distributed systems.  Some of
    the primitives (for example, CRTPROCESS and DELPROCESS) are necessary elements
    for a "network operating system (NOS)," into which DPS may itself one day
    evolve.

            CRTPROCESS (computer, program, credentials -> PH)
            DELPROCESS (ph)
            ITDPROCESS (ph1, ph2 -> ph12, ph21, ih)
            SEPPROCESS (ih)

    Packages

            OPNPACKAGE (ph, packages -> pkhs)
            CLSPACKAGE (ph, pkhs)

    Variables

            CRTVARIABLE (ph, variable, value)
            DELVARIABLE (ph, variable)
            RDVARIABLE  (ph, pkh, variable, substructure -> value)
            WRTVARIABLE (ph, pkh, variable, substructure, value)

    Procedures

            CALLPROCEDURE (ph, pkh, procedure, arguments, argumentlistmask,
                           resultlistmask, -> outcome, results, tid)
            LINKPROCEDURE (tid, arguments, argumentlistmask,
                           resultlistmask, -> outcome, results)
            SGNLPROCEDURE (tid, parameters, parameterlistmask)
            HELPPROCEDURE (tid, number, information -> solution)
            NOTEPROCEDURE (tid, number, information)
            ABRTPROCEDURE (tid)

                                        -27-

    Network Working Group              Elements of a Distributed Programming System
    Request for Comments:  708      Appendix D:  Additional Areas for Investigation

                                  APPENDIX D

                      ADDITIONAL AREAS FOR INVESTIGATION

    Although the expanded distributed programming system developed in this paper
    and summarized in the previous appendix is already very powerful, many
    additional aspects of process interaction remain, of course, to be explored.
    Among the additional facilities that the Protocol must eventually enable the
    environment to provide are mechanisms for:

            (1)  Queuing procedure calls for long periods of time (for
                 example, days).

            (2)  Broadcasting requests to groups of processes.

            (3)  Subcontracting work to other processes (without remaining
                 a middleman).

            (4)  Supporting brief or infrequent inter-process exchanges
                 with minimal startup overhead.

            (5)  Recovering from and restarting after system errors.

                                        -28-

    Network Working Group           Elements of a Distributed Programming System
    Request for Comments:  708                                        References

                                  REFERENCES

    1.  White, J. E., "A High-Level Framework for Network-Based Resource Sharing,"
        submitted for publication in the AFIPS Conference Proceedings of the 1976
        National Computer Conference.

    2.  Watson, R. W., Some Thoughts on System Design to Facilitate Resource
        Sharing, ARPA Network Working Group Request for Comments 592, Augmentation
        Research Center, Stanford Research Institute, Menlo Park, California,
        November 20, 1973 (SRI-ARC Catalog Item 20391).

    3.  White, J. E., DPS-10 Version 2.5 Implementor's Guide, Augmentation
        Research Center, Stanford Research Institute, Menlo Park, California,
        August 15, 1975 (SRI-ARC Catalog Item 26282).

    4.  White, J. E., DPS-10 Version 2.5 Programmer's Guide, Augmentation Research
        Center, Stanford Research Institute, Menlo Park, California, August 13,
        1975 (SRI-ARC Catalog Item 26271).

    5.  White, J. E., DPS-10 Version 2.5 Source Code, Augmentation Research
        Center, Stanford Research Institute, Menlo Park, California, August 13,
        1975 (SRI-ARC Catalog Item 26267).

    6.  Bobrow, D. G., Burchfiel, J. D., Murphy, D. L., Tomlinson, R. S., "TENEX,
        a paged Time Sharing System for the PDP-10," Communications of the ACM,
        Vol. 15, No. 3, pp. 135-143, March 1972.

                                        -29-

    Network Working Group           Elements of a Distributed Programming System
    Request for Comments:  708                                       Figure List

                                 FIGURE LIST

    Fig. 1  Interfacing distant applications programs via their run-time
            environments and an IPC channel.

    Fig. 2  Two processes that can only be introduced via a logical channel.

    Fig. 3  A logical channel.

                                          -30-