From 4bfd864f10b68b71482b35c818559068ef8d5797 Mon Sep 17 00:00:00 2001 From: Thomas Voss Date: Wed, 27 Nov 2024 20:54:24 +0100 Subject: doc: Add RFC documents --- doc/rfc/rfc708.txt | 1708 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 1708 insertions(+) create mode 100644 doc/rfc/rfc708.txt (limited to 'doc/rfc/rfc708.txt') diff --git a/doc/rfc/rfc708.txt b/doc/rfc/rfc708.txt new file mode 100644 index 0000000..4b83469 --- /dev/null +++ b/doc/rfc/rfc708.txt @@ -0,0 +1,1708 @@ + + + +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- \ No newline at end of file -- cgit v1.2.3