RFC 708

Elements of a Distributed Programming System

📅 published January 1976, from ietf

Elements of a Distributed Programming System 🎀

okay bestie, this one is a 1976 paper by James E. White from the Augmentation Research Center at Stanford Research Institute in Menlo Park, California 94025 🌸 His phone number was (415) 326-6200 X2960, which is so vintage I'm obsessed. It's dated January 5, 1976, and it's a paper that was going to be submitted to the Journal of Computer Languages. The original doesn't state a category or status, and it doesn't list anything it obsoletes or updates. It's a proposal, not a finished standard 💅 It also builds on a companion paper, cited as (27197), that describes a simpler Procedure Call Protocol.

The funding note says the work was supported by the Advanced Research Projects Agency of the Department of Defense, and by the Rome Air Development Center of the Air Force. ✨

INTRODUCTION 🦋

Okay so the companion paper, cited as [i], proposes a simple protocol and software framework that makes it easier to build distributed systems on a resource-sharing computer network. It does this by letting distant processes talk to each other at the procedure call level 🔥 It's already great, but this basic "distributed programming system (DPS)" only covers the core stuff of remote procedure calling. You can name the remote procedure, pass it arguments, find out whether it worked, and get the results back. That's it 🙈

This paper is the glow-up. It extends that simple procedure call model and standardizes other common kinds of process interaction, so the whole thing becomes more powerful and comprehensive. The author is very clear that these extensions are not dogma. They're meant as a stimulus for further research, and the hope is that they reveal what the DPS concept can do 🌈

The first section summarizes the basic distributed programming system derived in [1]. The second section describes the general strategy for extending it. The third section is the longest one. It identifies aspects of process interaction that are common enough to be worth standardizing, and it suggests ways to build them into the DPS model 💜

REVIEWING THE BASIC SYSTEM 💅

The distributed programming system derived in [1] assumes that a network-wide "inter-process communication (IPC)" facility already exists, and it's built on top of that. DPS has two parts. The first is a high-level model of computer processes. The second is a simple, application-independent "procedure call protocol (PCP)" that makes the model work by regulating the dialog between two processes connected through an IPC communication "channel." 🫶

DPS is implemented by an installation-provided "run-time environment (RTE)." It gets link loaded with each applications program, or otherwise made available to it ✨

The Model 🦋

The procedure call model, which the paper calls the Model from here on, sees a process as a collection of remotely callable subroutines, or "procedures." Each procedure gets invoked by name and can be given a list of arguments. When it finishes, it returns two things to its caller: a boolean outcome that says whether it succeeded or failed, and a list of results 🎀

The Model lets the process at either end of the IPC channel invoke procedures in its neighbor. It also lets a process accept two or more procedure calls to run concurrently. Main character energy 👑

The arguments and results of procedures are built from a small set of primitive "data types." Here they are:

LIST: A list is an ordered sequence of N data objects called "elements." Here and everywhere else in these descriptions, N is limited to the range [0, 2**15-1]. A LIST can contain other LISTs as elements, so you can build arbitrarily complex, composite arguments or results. Iconic 🧚
CHARSTR: A character string is an ordered sequence of N ASCII characters. It's perfect for lots of text stuff, from short user names all the way to whole paragraphs 📝
BITSTR: A bit string is an ordered sequence of N bits. That makes it a way to represent any binary data at all, like the contents of a word of memory 🔥
INTEGER: An integer is a fixed-point number in the range [-2**31, 2**31-1]. It's the go-to for numerical data, such as time intervals, distances, and so on 🌸
INDEX: An index is an integer in the range [1, 2**15-1]. Like its name and value range suggest, an INDEX can point to a particular bit or character in a string, or to an element in a list. A lot of the protocol extensions in this paper will also use INDEXES as handles for objects in the DPS environment, like processes and channels 💖
BOOLEAN: A boolean stores a single bit of information. It's either true or false 💜
EMPTY: An empty is a valueless placeholder inside a LIST that's acting as a parameter list 🙈

The Protocol 🎀

The procedure call protocol, which the paper calls the Protocol from here on, is what implements the Model. It defines a "transmission format" for each of the seven data types above. The paper points to the formats suggested in Appendix A. The Protocol also requires that parameters get encoded in that format whenever they're transported between processes. Think of it as the dress code for every message 💅

The Protocol also specifies the inter-process messages that invoke remote procedures. Here they are, symbolically:

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 message comes back in eventual response to the first. It reports the OUTCOME and RESULTS of the completed procedure ✨

Whenever OUTCOME shows that a procedure failed, the procedure's RESULTS are required to be an error number and a diagnostic message. The error number helps the invoking program figure out what to do next. The diagnostic message is for possibly showing the user 🙈

The CALL message can include an optional "transaction identifier (TID)." When it does, that's a request from the caller for an acknowledging RETURN message that echoes the identifier back. Lowkey really useful 🦋

Data types and their transmission formats are mainly there to carry the arguments and results of remote procedures. They work just as well for representing the messages that transmit those parameters. So the Protocol represents each of the two messages above as a PCP data object. Specifically, it's a LIST whose first element is an INDEX holding the message type 🌈

The concise statement of the Protocol looks like this:

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

In this and all the later protocol descriptions, elements inside square brackets are optional. That means they may be EMPTY. When a procedure fails, its RESULTS are represented like this:

LIST (error, diagnostic)
      INDEX  CHARSTR

The Run-Time Environment 🌸

The run-time environment, which the paper calls the environment from here on, connects the applications program to a remote process through an IPC channel. It gives the applications program a set of "primitives." These are implemented either as subroutines or as system calls, and the applications program uses them to manipulate the remote process at the other end of the channel. The environment carries out these primitives by sending and receiving protocol messages over the channel 💖

In its current rudimentary form, the Protocol lets the environment offer a single remote procedure calling primitive to the applications program. It looks like this:

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

This primitive invokes the named remote PROCEDURE with the ARGUMENTS provided, and returns its OUTCOME and RESULTS. It blocks the invoking applications program until the remote procedure returns. The paper also says a variant could be provided that just starts the call. The applications program would then collect the outcome and results in a second operation 🧚

The interface between the environment and the applications program depends on the machine, and maybe even on the language. So the environment-provided primitives can only be described symbolically in this paper. The PCP data types are a handy way to describe their arguments and results, so the paper uses them throughout. In practice, though, those parameters usually get passed between the environment and the applications program in some internal format 🎀

BOOTSTRAPPING THE NEW PROTOCOL FUNCTIONS 🧚

The Protocol already has a way to invoke arbitrary remote procedures. So the Model extensions proposed in this paper will be implemented as procedures whenever possible, not as extra messages. ✨ That's the bestie move 💅

These special "system procedures" are different from applications procedures. They get called and implemented by run-time environments, not by the applications programs they serve. The remote applications program can't reach them through the normal environment-provided remote procedure calling primitive. Even so, system procedures let the environment implement and offer new primitives to its applications program 🌈

The calling sequences of many of these new primitives will closely match those of the remote system procedures that implement them. Other primitives are more complex. They need calls to several system procedures, possibly spread across different processes. Throughout the paper, the author describes the Protocol additions each Model extension requires. The author also suggests calling sequences for the new primitives that the applications program gets access to 🦋

SOME POSSIBLE EXTENSIONS TO THE MODEL 👑

1. Creating Remote Processes 🌸

Before a program on one machine can use resources on another machine, it has to do one of two things. It can create a new process on the remote machine, or it can gain access to an existing one. Either way, the local process has to establish an IPC channel to a resident dispatching process inside the remote system. Then it has to specify the program to be started or contacted, and identify itself, so its access to the program can be set up and billing can happen. Once those preliminary steps are done, the requested process takes responsibility for the IPC channel, and the real communication begins 💖

How the environment carries out this scenario mostly depends on the IPC facility the distributed system is built on. If the IPC facility has a single primitive that does the whole job, the environment only needs to invoke that primitive ✨ If it only gives a way to establish a channel to the remote dispatcher, the way the ARPA computer Network (the ARPANET) does, then the Protocol itself has to include provisions for naming the program to be run and presenting the required credential 🫶

The environment adds the following system procedure to the Protocol. It lets the local environment give the remote dispatcher the information it needs, and the description picks up right there. 🌈

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 adds the notion of "creation" to the Model 🎀. It lets the environment offer these primitives to its applications program:

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

okay so the first primitive either creates a new process or connects you to an existing one 🦋. It does this by first creating a channel to the dispatcher within the indicated COMPUTER, then invoking the remote system procedure INIPROCESS with the specified PROGRAM name and CREDENTIALS as arguments. It returns a "process handle PH" that the applications program uses to refer to the new process in later dialog with the local environment. The PH can be an index into a table inside the environment, or anything else the implementor finds convenient 💅.

The second primitive "deletes" the process whose handle PH you pass in. It does this by deleting the IPC channel to the remote process and reclaiming any internal table space that was allocated to it 🧹.

2. Introducing Processes to One Another ✨

The simplest distributed systems start with a single process. That process uses CRTPROCESS, described above, to create one or more "inferior" processes whose resources it needs 🌸. Some or all of those inferiors might need other remote resources too, so they create their own inferiors. This can keep going to arbitrary depth in principle 🌳. The result is a tree structure, where the nodes are processes and the branches are IPC channels.

A distributed system can have an arbitrarily large number of processes, but each process only knows about the process that created it and the ones it creates itself. Those are its parent and sons 👀. So the radius a process can reach into the tree is artificially small 🙈. This limited sharing range gets in the way of lots of distributed systems. It can be fixed by extending the Model so that an arbitrarily complex network of communication paths is laid on top of the process tree 🕸️.

One of the many ways the Protocol can provide these communication paths is to let one process "introduce" two processes it already knows, so they know each other 💜. For example, that could be two of its sons, or its parent and a son. Once they're introduced, the two processes can call one another's procedures with the same freedom the introducing process has. They can also introduce each other to other processes, which builds even longer communication paths 🔗.

2.1. Introductions Within a Homogeneous Environment

If you stay inside a "homogeneous environment" (meaning the domain of a single IPC facility), introducing two processes takes very little more than forming an IPC channel between them 🥰. The Protocol gets three new system procedures that manipulate IPC "ports". With them, the run-time environment of the introducing process can negotiate that channel 🎀.

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

The exact calling sequences for these procedures are dictated by the IPC facility underneath the distributed system. So the ones above are only representative of what a particular network might need. They're only slightly less complicated than what's required within the ARPANET, for example 🙃.

To create the channel, the introducing process's run-time environment allocates a PORT in each target process using ALOPORT. Then it tells each process, using CNNPORT, to connect its port to the other's through the IPC facility 🔌. The process handle PH that ALOPORT returns first serves as a handle for the allocated port, and later as a handle for the process the attached channel gives access to. To "separate" the two processes, the introducing process's environment only has to invoke DCNPORT in each process. That dissolves the channel, releases the associated ports, and deallocates the process handles 💔.

Now that we have these three new system procedures, the environment can offer these new primitives to its applications program ✨:

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

The first primitive introduces the two processes whose handles PH1 and PH2 are specified. Each handle can designate one of three things. It can be a son, in which case the handle is one that CRTPROCESS returned. It can be the parent process, which always has a special handle (for example, 1) that must be defined. Or it can be a previously introduced process, in which case the handle came from an earlier call to ITDPROCESS 🧩.

ITDPROCESS returns handles PH12 and PH21, which the two processes use to know one another. It also returns an "introduction handle IH" that the applications program can later use to separate the two processes with SEPPROCESS 🫶. The applications program doing the introduction is responsible for telling each introduced applications program its handle for the other. That part's on you, bestie 💅.

2.2. Introductions Within a Heterogeneous Environment

An IPC channel is enough to introduce two processes to each other, but in a heterogeneous environment, creating that channel is impossible 😭. Picture Figure 2: processes P1 and P2 (in computers C1 and C2, respectively) are interconnected in a distributed system by a network IPC facility. Now say P2 also attaches another process, P3, which lives in a minicomputer M. M is attached to C2 but isn't formally part of the network 🤯. In this setup, P2 can't introduce P1 and P3 to each other by just establishing an IPC channel between them, because they aren't within the domain of a single IPC facility.

One way around this is to extend the Model with a composite, or "logical channel", made of two or more physical (meaning IPC) channels 🌈. A message that P1 sends over the logical channel to Pn (n=3 in the example above) gets relayed over each successive physical channel by the environments of the intermediate processes P2 through Pn-1. Logical channels cost more than physical ones, since each message has to cross at least two physical channels and be handled by every environment along the way 😤. Still, they let processes that otherwise couldn't reach each other access one another's resources. Relaying messages is the environment's job, so the applications program never has to know it's happening 🙌.

As Figure 3 shows, a logical channel would consist of table entries kept by the environment of each process P1 through Pn. It would also include the code in each environment that forwards messages arriving with a "routing code" that addresses the local table entry 🗺️. Each table entry holds the process handles for the two adjacent processes, along with the routing code each one recognizes. To send a message to its distant neighbor, the source process (say P1) transmits it over its IPC channel to P2, with a routing code that addresses the right table entry within P2. When P2 gets the message, it finds its table entry using the routing code. Then it updates the message with the routing code P3 recognizes and forwards the message to P3. Eventually the message reaches its final destination, Pn 🏁.

Adding these system procedures to the Protocol lets the environment build a logical channel like the one above 🧱:

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

The simplest logical channel (n=3) is created by P2. P2 invokes CRTROUTE in both P1 and P3, specifying in each case the routing code MYCODE that P2 assigned to its segment of the logical channel. In return, P2 receives the routing CODES and process handles PHs that the two processes assigned 🎯. OLDCODE isn't needed in this simple case, so it's EMPTY.

More complicated logical channels (n>3) are needed when one or both of the processes being introduced is already linked, by a logical channel, to the process doing the introduction 🌀. In that case, part of the new channel has to replicate the existing one. So the routing code OLDCODE, for the table entry that represents that channel within the target process, is passed as an additional argument to the system procedure. The target process has to call CRTROUTE recursively in the adjacent process to replicate the rest of the model channel 🪞.

The process Pi that creates a logical channel takes responsibility for making sure it's eventually dismantled 🧹. To delete the logical channel, Pi invokes DELROUTE in Pi-1 and Pi+1. Each of those propagates the call toward its own end of the channel 🫧.

3. Controlling Access to Local Resources

The process introduction primitive above effectively lets one process pass access to another process along to a third 💌. Any process P2 that already holds a handle to a process P1 can get a handle that a third process P3 can use. Once P1 and P3 have been introduced, P3 can freely call procedures in P1, and the other way around 🤝.

A process can stop its introduction to another process by aborting the ALOPORT system procedure. That prevents the introduction and limits which processes can reach it 🚫. Sometimes, though, you need finer access controls. For example, a process might house two separate resources. One should be available only to its parent, and the other to any process the parent introduces it to 🔐. To implement a strategy like that conveniently, the Model has to be extended so that access controls can be applied independently to individual resources inside a single process 🎀.

A single procedure can technically count as a resource. But it's more practical and convenient to think of larger, composite resources made of several related procedures 📦. A simple database management module is a good example. It has procedures for creating, deleting, assigning values to, reading, and searching data objects. Each procedure is useless on its own, but the whole family gives you a meaningful service 💖. This kind of "package" of logically related procedures might be the most reasonable object for the finer access controls to target 🌟.

Access controls can be applied to packages by requiring a process to first "open" a remote package and get a handle for it, before it can call any of the procedures inside 🚪. When a process tries to open a package, its right to do so can be checked, and the attempt can be aborted if necessary. Checking the open attempt is obviously cheaper than checking every single procedure call 💸. Opening a package is also a handy moment to initialize any package-dependent state information ✨.

Adding the following pair of system procedures to the Protocol lets the environment open and close packages inside another process. For

Efficiency is the name of the game here, bestie 💅 These procedures can handle an arbitrary number of packages in a single transaction ✨

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

So the first procedure opens packages and hands back "package handles PKHS" for the PACKAGES you name 🎀 The second one closes one or more packages and releases the PKHS handles you got for them. Bye bye, handles 👋

Adding these two system procedures isn't the whole story, though. The Protocol must further require that every CALL message carries a package handle right alongside the procedure name 🔥 An EMPTY handle is allowed and might be how you designate a system procedure. Here's the lowkey big deal: this requirement makes the package the domain where procedure names have to be unique. Main character energy for packages, no cap 👑

The system procedures above let the environment offer its applications program primitives with calling sequences that look a lot like the system procedures. The difference is that these primitives take the process handle of the target process as an extra argument 🦋 To implement them, the environment just has to find the remote process in its internal tables and invoke OPNPACKAGE or CLSPACKAGE in that process. Easy peasy 🌸

4. Standardizing Access to Global Variables ✨

Conventional systems often keep global "variables" that any module in the system can get to 🌈 People usually work with them using two primitives:

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

Those primitives are either built into the language or written as specialized procedures. The first approach is the one that encourages treating every variable in the system the same way 💖

Distributed systems that keep remotely-accessible variables also need to pick a strategy for the access primitives. Sure, those primitives could be written as specialized applications procedures. But adding the following new system procedures to the Protocol guarantees one uniform run-time access mechanism 🫶

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

These procedures basically define variables as named data objects, modeled on PCP data types, and they suggest clustering those variables in packages with related procedures 🧚 RDVARIABLE returns the VALUE of the VARIABLE whose name and package handle PKH you specify. WRVARIABLE does the opposite and sets it.

These new procedures let the environment offer its applications program primitives with calling sequences like the corresponding system procedures. Same deal as before: they also take the target process's handle as an extra argument 💅 These primitives give a suitably modified compiler a way to bring back the compile-time uniformity you get when you manipulate variables in conventional programming environments, which is so iconic. To implement them, the local environment identifies the remote process from its internal tables and invokes RDVARIABLE or WRVARIABLE in that process.

Most variables will restrict which data types and values can be assigned to them, and some may even be read-only 🔒 But since they're modeled on PCP data types, their values can, in principle, be arbitrarily complex. For example, a LIST of LISTS. Sometimes the programmer only wants to touch one element of the variable. Or, if that element is itself a LIST, just one of its elements, and so on, to arbitrary depth 🌳

To optionally manipulate a single element of a variable's composite value, you add the following argument to the calling sequences of the system procedures above:

    substructure
    (LISTofINDEXs)

At each successive level of the value's tree structure, you identify the INDEX of the element you want. The resulting list of indices identifies the SUBSTRUCTURE whose value gets returned or replaced ✨

5. Routing Parameters Between Procedures 🎀

In conventional programming systems, procedure results get used in a bunch of different ways, depending on the context of the calls 💭 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 how a result is meant to be used usually lives entirely inside the calling program. It looks at the results, passes them to a second procedure, or ignores them, whatever it likes 🙈

In a distributed system, shipping results from callee back to caller takes one or more inter-process messages, and that can be super expensive, especially when the results are large 😭 Data movement can be reduced in Cases 2 and 3 above by extending the Model so the intended disposition of each procedure result is known in advance by the callee's environment. In Case 2, if both callees live in the same process, the result can stay at its source and get supplied locally to the next procedure. In Case 3, the result can be thrown away at its source, maybe without even being computed, instead of being sent over and discarded at its destination 🍓

5.1. Specifying Parameters Indirectly 💅

Variables have the potential to get rid of the inefficiencies in Case 2 above. They give the callees' process a place to hold results from one procedure until another procedure needs them 🦋 The Protocol can be extended to allow this by letting the caller of any procedure include an optional "argument- and result-list mask" as an additional parameter of the CALL message. It looks like this:

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

A parameter list mask lets each parameter go either directly, through the parameter list, or indirectly, through a VARIABLE within the callee's process. So each element of the mask tells the callee's environment how to obtain or dispose of the matching parameter 🧠 To pass the result of one procedure as an argument to another, the caller just sets the matching elements of the result list mask in the first call and the argument list mask in the second call, respectively. If the procedure fails, the result list mask should be ignored, and the error number and diagnostic message come back directly to the caller 💀

5.2. Providing Scratch Variables for Parameter Routing 🌈

You could have each applications program provide its own variables for the stuff described above. But a more economical move is to extend the Model with special "scratch variables." The environment maintains these without any help from the applications program, and they get created and deleted as needed at run-time 🧚 Adding the following pair of system procedures to the Protocol lets the local environment create and delete these 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 let the environment offer its applications program primitives with calling sequences like those of the corresponding system procedures. They take the process handle of the target process as an extra argument 💖 Implementing them only requires that the environment find the remote process in its internal tables and invoke CRTVARIABLE or DELVARIABLE in that process.

5.3. Discarding Results 🫧

The inefficiencies from Case 3 above can be neatly eliminated. The caller identifies, via the result list mask (for example, with a zero-length CHARSTR), that a result will be ignored. That way the result doesn't need to be sent back to the caller at all 🙌

6. Supporting a Richer Spectrum of Control Transfers 🦋

Right now, the Model defines a procedure call as a simple two-stage dialog. First the caller describes the operation it wants performed. Then the callee performs it and reports how it went 💬 This simple dialog is enough to conveniently build a big class of distributed systems. Sometimes, though, you need more complex forms, and the Model can be extended to admit a variety of more powerful dialog forms. Four are described below, and they're just examples 🔥

6.1. Transferring Control Between Caller and Callee 🎀

Lots of conventional programming systems let the caller and callee swap control any number of times before the callee returns 🔄 These "coroutine linkages" are handy. For example, the callee can get help with a problem it ran into, or it can deliver the results of one suboperation and grab the arguments for the next one 🫶

Adding the following system procedure to the Protocol lets the environment set up a coroutine linkage between caller and callee. Its invocation gives up control of another, previously initiated procedure 🌷

    TAKEPROCEDURE (tid,  yourtid, parameters)
                INDEX BOOLEAN  LIST

Its arguments include the identifier TID of the affected transaction. They also include YOURTID, which says whose name space the identifier was assigned from (in other words, whether the process giving up control is the caller or the callee). And PARAMETERS, which the procedure surrendering control provides. By using something the Protocol already has (declining acknowledgment of its calls to TAKEPROCEDURE), the invoking environment can pull off the control transfer with a single inter-process message 🤯

Adding this new procedure to the Protocol lets the environment give its applications program the following new primitive:

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

This primitive assumes that the CALLPROCEDURE primitive is also modified. It has to return the pertinent transaction identifier if the callee starts a coroutine linkage instead of returning 💅 Calling LINKPROCEDURE then continues the dialog. It supplies ARGUMENTS and hands control to the remote procedure, then waits for the next transfer of control and the RESULTS that come with it. If the remote procedure returns instead of starting another coroutine linkage, the primitive reports its OUTCOME and invalidates the transaction identifier 💀

LINKPROCEDURE blocks the applications program until the remote procedure gives up control. But a variant can also be provided. It just starts the coroutine linkage, and then the applications program collects the outcome and results in a second operation 🌈

6.2. Signaling the Caller/Callee 📣

Sometimes a monolog works better than the dialog a coroutine linkage starts. Maybe the caller or callee wants to report an event it detected, or send large parameters piecemeal so it doesn't need a ton of buffering 🧃 Since no return parameters are needed in those cases, the initiating procedure only has to "signal" its partner. It keeps control of the call while it does that ✨

Adding the following system procedure to the Protocol extends the Model to support signals. It also lets the environment transmit parameters to or from another, previously initiated procedure without giving up 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, a YOURTID indication of whose name space that identifier was assigned from, and the PARAMETERS themselves 💖 This new procedure gives the environment a primitive for its applications program. Its calling sequence looks a lot like the system procedure's, except it doesn't need YOURTID as an argument 🎀. Under the hood, the environment only has to find the remote process in its internal tables and invoke SGNLPROCEDURE there ✨.

By asking for an acknowledgment on every SGNLPROCEDURE call, and holding back later calls on the same transaction until that ack shows up if needed, the invoking environment gets a scrappy kind of flow control 🛑. That keeps the remote process's buffers from getting overrun 💅.

6.3 Soliciting Help from Superiors ✨

As in conventional programming systems, remotely callable procedures in a distributed system will sometimes call on others to handle parts of their task 🧵. Every procedure along that "thread of control" from nested calls is, in a sense, accountable not just to its immediate caller but also to every procedure above it on the thread 👑. To handle that responsibility properly, a procedure must sometimes talk to these "superiors."

Sometimes a procedure reaches a point in its execution past which it can't go without outside help 🥺. It might need extra resources or more direction from the human user it's running on behalf of 🙈. Before hitting that impasse, though, it may have already sunk a lot of real and/or processing time into the work, and all of that is lost if it aborts 💀.

Adding to the Protocol the following system procedure cuts down on that waste by letting the environment ask a callee's superiors for help 🧚:

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

Its arguments are the TID of the affected transaction (the direction of the control transfer is implied in this case), a NUMBER identifying the problem encountered, and arbitrary supplementary INFORMATION 💜.

The primitive this new procedure gives the environment to offer its applications program has an identical calling sequence 🌸. Implementation only requires the environment to identify the remote process from its internal tables and invoke HELPPROCEDURE in that process.

The search for help starts when HELPPROCEDURE is invoked in the caller's environment 🔍. If the caller understands the problem (meaning it recognizes its number) and is able to solve it, HELPPROCEDURE just returns 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 ends as soon as a superior responds positively, or when the end of the control thread is reached 🏁. In that last case, each of the nested HELPPROCEDURE procedures returns unsuccessfully, telling its caller that the search failed 😭.

6.4 Reporting an Event to Superiors 🦋

A procedure sometimes witnesses or causes an event its superiors should know about, like the start or completion of some major step in its execution 📣. Adding to the Protocol the following system procedure lets the environment tell a callee's superiors about an arbitrary event:

        NOTEPROCEDURE (tid,  number, information)
                       INDEX INDEX   any

Just like HELPPROCEDURE, its arguments include the TID of the transaction it affects, a NUMBER identifying the event being reported, and arbitrary supplementary INFORMATION 💌.

The primitive this procedure gives the applications program has an identical calling sequence ✨. Implementation only requires that the environment identify the remote process from its internal tables and invoke NOTEPROCEDURE in that process.

Same flow-control trick as before: request an acknowledgment for each NOTEPROCEDURE call and, if necessary, delay subsequent calls that affect that transaction until the acknowledgment arrives 🛑. It's a crude form of flow control, but it stops the remote process's buffers from being overrun 💅.

Notifying the superiors starts with invoking NOTEPROCEDURE in the caller's process, then works its way recursively up the thread of control until the top is reached 🪜.

7. Aborting Executing Procedures 💅

Conventional systems that accept commands from the user sometimes let them cancel an executing command. That might be one they issued by accident or with messed-up parameters, or one they just can't wait around for 😩. This ability is especially important when the command has a significant execution time, like one that compiles a source file 🕰️. In a distributed system, running such a command may involve invoking one or more remote procedures, so cancelling it requires aborting any outstanding remote procedure calls 🛑.

Adding to the Protocol the following system procedure is the basis for a command cancellation facility, because it lets the environment abort another, previously invoked procedure 🙅‍♀️:

        ABRTPROCEDURE (tid)
                       INDEX

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

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

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 remain to be explored, and Appendix D suggests a few 🔭. Nevertheless, the primitives already made available by the run-time environment give the applications programmer a powerful and coherent set of tools for constructing distributed systems 🌈.

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 paper 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 ARC began in July of 1974 🗓️. That research included developing the Model, designing and documenting a prototype run-time environment, and implementing it for a particular machine [4, 5]: 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 was 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 🎀.

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 a mechanism for format negotiation to the Protocol 🤝. Format negotiation would be another responsibility of the environment, so it could be made completely invisible to the applications program 🫥.

Two transmission formats are suggested below 👀. The first is a 36-bit binary format for use between 36-bit machines, and the second is an 8-bit binary, "universal" format for use between dissimilar machines 🌍. Data objects are fully typed in each format, so the environment can 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

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

APPENDIX B — THE EXPANDED PROCEDURE CALL PROTOCOL 🌈

The Protocol that results from the extensions proposed in this paper is summarized below 📋. Watch how the underlying notion of PCP data types makes the syntactic description so concise 🧩.

Parameter list masks have been included not only as additional parameters of the CALL message, as proposed in the paper, but also as arguments of the TAKEPROCEDURE and SGNLPROCEDURE system procedures 🎭. 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)

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)

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

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

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)

Appendix C: Summary of RTE Primitives ✨

Okay so this appendix is the big recap, bestie 🧚. The DPS primitives that the applications program gets access to, thanks to the Model extensions proposed in this paper, are listed below. Together they hand the applications programmer a seriously powerful and coherent toolkit for building distributed systems. 💅 Some of them (CRTPROCESS and DELPROCESS, for example) are necessary pieces for a "network operating system (NOS)," and DPS might one day grow into one of those. 🌈

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)

Appendix D: Additional Areas for Investigation 🔥

Even though the expanded distributed programming system from this paper (the one summarized in the previous appendix) is already super powerful, there's still a lot of process interaction left to explore, obviously 🙈. The Protocol will eventually need to let the environment provide mechanisms for:

Queuing procedure calls for long periods of time (for example, days). ⏳
Broadcasting requests to groups of processes. 📣
Subcontracting work to other processes (without remaining a middleman). 🫶
Supporting brief or infrequent inter-process exchanges with minimal startup overhead. ⚡
Recovering from and restarting after system errors. 🩹

References ✨

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. 📚
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). 🌸
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). 🍓
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). 💜
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). 🧚
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. 🦋

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. 🌈

📦 where this page comes from

ietf: rfc708 1976-01
💖 girlified by claude-haiku-5-5 on 2026-10-18: a language model's rewrite of the original, under its terms