RFC 712

RFC 712: A Distributed Capability Computing System (DCCS) 🎀

• Network Working Group 🌸
• Request for Comments: 712 💖
• Author: J.E. Donnelley, Lawrence Livermore Laboratory ✨
• Date: February 1976 📅
• Category/status: not stated in the header 🤷‍♀️
• Obsoletes/Updates: nothing listed in the header 🧚

This paper was prepared for submission to the international Conference on Computer Communication, ICCC-76, August 3, 1976, Toronto, Canada. 🇨🇦✨

Okay, so this is a preprint of a paper meant for publication in a journal of proceedings. Changes might happen before it's published, so it's shared on the understanding that it won't be cited without the author's permission 🙈🫶

The work here was supported partly under contract #EPA-IAG-D5-E681-DB with the Environmental Protection Agency, and partly under contract #[RA] 76-12 with the Department Of Transportation. The report was prepared for the U.S. Energy Research and Development Agency under contract #W-7405-Eng-48. 💼💅

This paper is about a distributed computing system, and it's giving big brain energy 🧠💜 The first part introduces an idealized operating system called CCS (Capability Computing System). The second part defines the DCCS protocols and describes the processes needed to run the DCCS on a CCS. The rest of the paper covers using the DCCS protocol in a computer network with heterogeneous systems, and it presents a couple of applications. Those applications are about optimally solving the single copy problem for distributed data access, and building a transparent network resource optimization mechanism. Iconic 👑🔥

The Capability Computing System (CCS) 💅

Okay, the CCS isn't exactly like any operating system that already exists, but it's very similar to some of the capability list (C-list) operating systems written about in the literature [1-7] 📚 A lot of the CCS features come from a proposed modification to the RATS operating system [1-3] 🦋

Bestie, if you read the docs for most computer systems, you'll see tons of references to different kinds of objects. Typical examples are files, processes, jobs, accounts, semaphores, tasks, words, devices, forks, events, etc. etc. 🍓 One big goal of C-list systems is to give you one uniform way to access all of these objects. Because every CCS object goes through that same mechanism, DCCS can be built in a type-independent way. That's lowkey genius 🧚✨

The CCS is a multiprocessing system, and its active element is called a process. For most purposes, whatever you already picture when you hear "process" will do just fine 💖 A process can run instructions like the ones on commercially available computers. It has a memory area and some status indicators, like "RUN" and "WAIT" 🌈 In C-list systems, though, a process also has a capability list (C-list). This list is an area where pointers to the objects the process is allowed to access are kept. The system protects these pointers, so the process can only use its C-list in two ways: as a source of capabilities it uses to access things, and as a place to store capabilities it's been given. No cap, that's a strict vibe 🔒

Figure 1 shows a few typical processes that come up later on. In those diagrams, the left half of a process box is the C-list, and the right half is the memory 🎀

The key to the uniform access method in the CCS is the invocation mechanism 👑 This is how a process makes a request on a capability in its C-list. An invocation is super similar to a subroutine call on most computer systems. When a request is made, the invoking process passes some parameters to a service routine, and it gets some parameters back in return 💅

There are a few major differences between the invocation mechanism and the usual subroutine calling mechanisms, though. 😭

1. The service routine being called is usually not in the process's memory space. The protected capability points to it, and it can be implemented in hardware, in microcode, in system kernel code, in another arbitrary process, or, as we'll see with the DCCS, in another computer system. In Fig. 1, for example, the serving process is handling an invocation on the semaphore requestor. 🦋
2. When you invoke a capability, other capabilities can be passed and returned along with plain data parameters. In the DCCS, capabilities and data can also travel through a communication network. 🌸
3. The last important distinction is best explained with the outside teller windows you see at banks. Those windows usually have a drawer that the customer can open, but the customer and the teller can't both open it at the same time. Apart from that drawer, the customer and the teller are physically isolated 🏦 With the invocation mechanism, the invoking process explicitly passes certain capabilities and information to the service routine. It also names the C-list locations and memory areas where the return parameters go. Apart from those parameters, the invoking process and the serving routine stay isolated from each other. In the DCCS, this protection extends across a whole network of systems 🛡️✨

In the CCS, invoking a capability is the only way a process can pass or receive information or capabilities. Everything often called a system call on a typical operating system is an invocation on the right capability in the CCS 💜 Also, a CCS C-list envelopes its process. You need this fact to transparently move processes, which is what the second application on network optimization (page 23) is about 🧚🎀

The CCS Extension Mechanism ✨

okay so there is ONE more basic capability mechanism we need for the CCS version of the DCCS 💅 it lets processes set themselves up to create new capabilities that they can service 🎀 C-list systems do this really differently from each other, so we're describing one mechanism that works. And we need one more primitive capability to get things started 🌸

5. Server Capability

a. "Create requestor", requestor number; > ; requestor

b. "My requestor?"; capability> answer, requestor number;

c. "Wait"; > reason, requestor number, PD; request

So besides the server, we get two more capabilities: the requestor and the request 🦋 we'll explain them as we go through what you can do with a server.

The first invocation makes and returns a requestor capability. The number you pass in gets tied to that requestor 💖 The requestor capability is the brand new one being created. You can do ANY kind of invocation on a requestor, that's literally its whole reason for existing 😭 A process holding a server capability can make a requestor look like any kind of capability it wants. Main character energy 👑

"My requestor?" tells you whether a capability is a requestor on the server you invoked. It gives back either:

"Yes", requestor number; or "No",0;

The last invocation is "Wait" 🧚 It blocks until something needing the server's attention happens. There are two big events a service routine has to know about. First, if the last capability to a requestor gets overwritten, so that requestor can't be invoked again until a new one is created, the "wait" returns:

"Deleted", requestor number, 0; Nil

The last two parameters, 0 and Nil, are just filler for the returned PD and request (see 5c) 🙈 When a "wait" returns "Deleted", the service routine can recycle whatever resources it was using to serve that numbered requestor (like the requestor number itself) ♻️

The most important event is when one of the server's requestors gets invoked. Then the server returns:

"Invoked", requestor number, PD; request

The third parameter, PD, stands for Parameter Descriptor 🍓 It describes how many of each kind of parameter get passed in each direction during a requestor invocation. To be specific, it's four numbers: data bits passed, capabilities passed, data bits requested, and capabilities requested.

The last parameter the server gets, the request capability, is how the serving process pulls out the passed parameters and sends the requested ones back to the requesting process 🫶 So it has these invocations:

6. Request Capability

a. "Read parameters"; > {The passed parameters

b. "Return", {The return parameters}> ;

The "Return" invocation has an extra effect: it restarts the requesting process 🔥

Something to note about the server mechanism: invocations on a server's requestors get queued until the server is "wait"ed upon 👀 That's one reason a request gets its own separate capability. The serving process can hand the request off to some other process for servicing, then go right back to waiting on its server for more requests 💅 In the outside bank window analogy, this is the teller passing the request to someone else so they can get back to the customers in line. And the request capability points back at the requesting process, so the return can be properly carried out 🎀

A sample service is the well known semaphore [8] service routine 🦋 It keeps a table with the semaphore value for each semaphore it's serving. It also keeps a list of queued requests, representing the processes that get stuck in the semaphore by "P"ing it when its value is less than or equal to zero 😭 The invocations on a semaphore are:

7. Semaphore

a. "P"; > ;

b. "V"; > ;

Figures 1. and 2. show a diagram and a flow chart for the semaphore serving process 🌈 The flow charts include most of the basic capability invocations, but they don't include detailed descriptions of table searches 🙈 The table for the semaphore service routine has an entry for each supported semaphore. Each entry holds the semaphore value and a link into a list of pointers to the requests hung in that semaphore (if there are any) 💜

---

The most important feature of the server mechanism is that, by using it, the functioning of any capability can be emulated 🤯 This property is similar to the insertion property discussed in [9], and it's the cornerstone of the DCCS 👑 The basic idea is that the server "wait"s for requests and passes them on to the capability being emulated. Figure 3 flow charts this single-capability emulation ✨ The emulation shown is just an overview, and it doesn't handle every situation correctly. For example, a capability may not return to invocations in the same order they came in 😳 Those situations also show up in the DCCS, so we'll talk about how they're handled there instead of here 🧚 Important bit: except for delays from processing and communication, the emulation done in the DCCS is exact 💖

The DCCS Implementation ✨

Okay bestie, so the DCCS is going to be described on a network of CCS systems 🌐. We're just going to assume a network capability exists, and it's giving foundation 💅:

8. Network Capability

• a. "Input"; > Host no., message;
• b. "Output", Host no., message > ;

It's assumed that the "Output" invocation returns immediately after queuing the message for output, and that the "input" invocation waits until a message is available 📬.

For pedagogical purposes (aka so we don't get lost 🧚), the DCCS description is split into two parts. First there's a quick overview of the important mechanisms. The overview glosses over some important issues, and those get properly resolved in the more complete description that comes after it 🎀.

The whole point of the DCCS is to let capabilities on one host be referenced by processes on other hosts that have the right capabilities 🦋. So each host keeps a list of the capabilities it supports for other hosts to use. Each host also runs a server, which hands out requestors that are made to look exactly like the matching capability on the remote host 👑. When one of these emulated requestors gets invoked, the emulating host sends its parameters over the network to the supporting host. The supporting host then makes sure the proper capability gets invoked and passed those parameters. When the invoked parameters come back through the network to the emulating host, the emulating host returns the return parameters to the requesting process 💅.

Let's look at the "Read" request on a file, which is diagrammed in figure 4 📖. When the emulated file (a requestor) is invoked, the emulating process receives "invoke", requestor number, PD; request. The requestor number that gets returned is actually a descriptor with two numbers: Host number, capability number. These descriptors are called Remote Capability Descriptors (RCDs) 🫧. An RCD identifies a host and a capability in the list of capabilities that host supports. After it gets a request, the emulating process reads the parameters the requesting process passed in, then sends them along with the Parameters Descriptor to the remote host in an "invoke" message 📨.

When the remote host gets this info, it passes the parameters to the supported file capability by invoking it, and it specifies the proper return parameters as noted in the Parameter Descriptor. When the invoked file returns, the returned data travels back through the network to the emulating host in a "Return" message 💌. The emulating host then hands that data back to the requesting process by doing a "Return" invocation on the request capability it originally received. Once the requesting process wakes up from the return, it'll look exactly like it invoked a local file. Iconic 🌸.

Now, this works fine when the parameters and return values are just information. But what about when capabilities are involved? 👀 In that case, the routines use the existing remote capability access mechanism and pass the appropriate descriptor. For example, the "Take" invocation on a directory is diagrammed in figure 5 🗂️. The only real difference is that a capability has to be returned. When the invoked directory (or whatever it really is) returns the capability, the supporting host allocates a new slot in its supported capability list for it, and sends a new descriptor back to the emulating host. When the emulating host gets that descriptor, it creates a new requestor using the returned descriptor as its requestor number, and returns that requestor to the invoking process. The requestor that comes back acts as the capability taken from the remote directory, and it can be invoked exactly as if it were the real capability 🦄.

Here's the thing I find so cute about this design: neither the emulating host nor the supporting host needs to know what kind of capabilities they're supporting. The mechanism doesn't care about their type 🧠. Also, neither host needs to trust the other with anything beyond the capabilities it has been rightfully granted. Even the DCCS processes only need to be trusted with the network capabilities and the supported capabilities. And finally, no secret passwords (the kind that could get disclosed) are needed for security 🔐. The DCCS directly extends the CCS protection mechanisms,

A more complete description of the DCCS is coming up next. To avoid unnecessary complication, though, several issues are not discussed: error indications, system restart and recovery, network malfunctions, message size limitations, resource problems, etc. These issues aren't unique to the DCCS, and their solutions aren't pertinent here 🙈.

As noted earlier, the complete DCCS has to address several issues that were glossed over in the overview 🧩. As we discuss these, several message types get introduced beyond the "Invoke" and "Return" messages from the overview. The formats for all the DCCS messages are summarized in figure 6 📋.

A. Timing

Invocations can take a very long time to complete 🐢. We saw an example with the semaphore capability earlier. An even more dramatic example would be a clock capability that was requested to return nothing AFTER 100 years had passed 💀. Clearly we don't want the emulating process to wait until it receives a "Return" message from the remote host before servicing more invocations.

So what happens in the emulating host is that it adds the request capability to a list of pending requests after sending the "invoke" message to the supporting host (this is kind of like the semaphore example from earlier 🚦). The emulator can then go back and wait for more local requests.

There's a similar problem on the supporting side. We don't want the process waiting on the network input capability to just invoke the supported capability and sit around waiting for the return 🙅‍♀️. What it must do is set up an invocation process to actually invoke the supported capability, so that pending network input can be promptly serviced ⚡. The invoking process must then return the parameters after it receives them.

These extra mechanisms add complexity in the form of multiple requests being active between hosts 🌀. These requests are identified by a Remote Request Number (RRN). The RRN is an index into the list of pending requests.

B. Loops

Imagine host A passes a capability to host B, and B gets asked to pass the requestor that's being used to emulate that capability back to host A. Should B simply add the requestor to its support list and let A access it remotely? 🤔 If it did, then when the new requestor got invoked on A, the parameters would be passed to B, where they'd be passed to the requestor by the invoking process. Invoking the requestor would then send the parameters back through the network to A, where the real capability would finally be invoked. After that, the return parameters would have to go through the reverse procedure to get back to A via B. Honestly, this is clearly not an optimal mechanism 😩.

The solution makes use of the "My requestor?" invocation on a server capability, described in 5b. When B checks a capability that is about to be returned to A with the "My requestor?" invocation, and finds that the capability is one of its requestors with a requestor number indicating that it's supported on A, it can simply return the requestor number to A (recall that this is really a Remote Capability Descriptor, RCD). That tells A that the capability is local to A, and gives A the index to the capability in its supported capability list ✨.

C. Security

The mechanism in B. brings up a bit of a security issue 🚨. If B tries to invoke a capability in A's supported list, should A just let B have access without question? If it did, any host on the network could maliciously invoke any capability supported by any other host 😱. To allow access only when it has been granted through the standard invocation mechanism, each host can maintain a bit vector indicating which hosts have access to a given capability 🗝️. If a host does receive an invalid request, it's an error condition.

D. Indirection

There's an additional twist on the Loop problem noted in B. 🌪️ This variation comes up when A passes a capability to B, who then wants to pass it on to C. Here again, B can unambiguously specify which capability is to be passed by simply sending the Remote Capability Descriptor (RCD) that it knows the capability by. The RCD does indicate that the capability is one A has, though. A probably wouldn't believe that C should have access to it 🙃.

So B has to tell A: "1, who have access to your 1'th capability, want to grant it to host C". To do this, another message type is used. The "Give" message specifies the supported capability and the host it should be given to (refer to figure 6) 🎁. Again, giving away a capability you don't have is an error condition.

E. Acknowledgement

There's one last problem with the "Give" message 😬. If B sends the "Give" message to A and then continues on to send the Remote Capability Descriptor (RCD) to C, C might try to use the RCD before A has received the "Give". For this reason, B must wait until A has "ACK"nowledged the "Give" message before sending the RCD to C 🛑. This mechanism requires that hosts queue un"ACK"nowledged "Give"s. The format for an "ACK" is given in figure 6. This queueing may be avoided for most "Give"s after the first one for a given RCD, but only at the cost of a lot of additional memory and broadcasting "Delete"s (See F. below) 🫠.

F. Deletion

If all the requestors on A for a given capability supported on B are deleted, A may tell B about it so that B may:

• a. Delete A's validation bit in the bit vector for the specified capability, and
• b. If there are no hosts left that require support of the given capability, delete the capability from the supported capability list 🧹.

This function requires a new "Delete" message 🗑️.

---

Figure 6 is a summary of the message formats. Figure7-11 flow chart the complete DCCS 📊. In the flow charts, abbreviations are used to indicate the directories:

• CSL - Capability Support List
• RRL - Remote Request List
• IPL - Invocation Process List

The table manipulation isn't given in detail 🙈. Three tables are needed. The first is associated with the CSL and contains the bit vectors indicating access, as noted in C. above. The second table is associated with the RRL. It contains a host number for each active request. An attempted return on a request by a host other that the requested host is an error 🚫. The final table is a message buffer containing the pending "Invoke" and "Return" requests 📦.

To avoid hazards when referencing the CSL and its table, a semaphore called the CSLS is used 🔒. A message buffer semaphore, MBS, is similarly used to lock the message buffer. For the RRL and IPL, no locks are needed with the algorithms given 💜.

Generalization and Application ✨

okay so to actually build the DCCS, we assumed there was a whole network of CCS systems 🖥️. The CCS specs were kinda vague though 🙈. No mention of instruction sets at all! Any CCS-like implementation could use these mechanisms to snare their objects 🪤. Like, a process passed to a system with a different instruction set could be used as an efficient emulator 🧚.

The most important generalization is that a given implementation has no idea what kind of host it's talking to over the network 👀. Any sort of host could implement the protocol using the messages given. For example, a single user system could let its user do arbitrary invocations on remote capabilities and keep a table of the returned capabilities 💅. That system could also support some kind of standard terminal capability that gets handed to remote processes 🖥️✨. On a multi-user system, the same functions could be performed for each user 🫶.

In a sense, any system implementing the DCCS protocol becomes a C-list system 👑. The single user system could, for example, set up remote processes servicing remote server capabilities that hand out requestors to the single user system or any other systems 🌈. Returns from invocations could appear on the single user's terminal by remote invocation of the terminal capability, etc.. 💖

Implementing the DCCS on non-C-list systems is kinda similar to what happened with some host-to-host protocol implementations on the Department Of Defense's ARPA network [10] 🦋. The ARPA network host-to-host protocols let a process on one system talk to a process on another. A bunch of the ARPA net protocol implementations ended up introducing local process-to-process communication into hosts that formerly had none 💜.

---

Applications

I. Single Copy

The first application is a solution to what I've dubbed the single copy problem for information resources 🌸. Whenever a process receives information from an information resource, it can only receive a local copy of that information. This is obvious when the information comes from a distributed database, but it's also true in tightly coupled virtual memory situations, where information from shared memory has to be copied into local registers for processing 🧠. Once a process has a local copy, it might want to make sure the information stays current, i.e., that it's the single copy 🔒.

The traditional fix is to lock the information resource with a semaphore before making a local copy, then invalidate the local copy before unlocking the resource 😬. The problem is that, even when other processes aren't requesting the copied data, the data still has to be unlocked quickly just in case. That can result in a lot of needless copies being made 🙃.

What's needed is a mechanism that invalidates local copies exactly when requests by other processes would force invalidation ✨. To offer that, an information resource can have, in addition to the usual reading and writing invocations, the following:

"White lock", portion; > ; write notify
"RW lock", portion; >; RW notify

The important invocation on the notify capabilities is:

"Wait for notification"; > reason;

The basic idea is to let a process ask to be notified if someone tries to invalidate its copy 🔔. If the copy is only used for reading, the process only needs to request notifications of attempted modifications of the data ("Write lock"). When a process gets notified, it's expected to invalidate its copy and delete its write notify capability, which tells the information resource server that the pending write access may proceed 🏃‍♀️.

In the read write lock case, the RW notify capability can also be used for reading and writing the portion. Any other access to the portion will cause notification. When notified, the process holding the RW notify capability is expected to write back the latest copy of the information before deleting its RW notify capability 💾.

Space doesn't permit presenting more details for this mechanism 🥲. The important thing to notice is that it lets an information resource be shared so that, even though the information may be widely distributed, it's made to appear as a single copy 🫧. This has important applications to distributed databases 💅.

II. Network Resource Optimization

The application that probably best shows how useful the DCCS is comes from the sort of network optimization capability that can be used to create at least the primitive capabilities introduced earlier 📈:

9. Account Capability

a. The invocation looks like this:

"Create", type; >; capability

The passed type parameter could at least be any of: "File", "Directory", "Process", or "Server". The appropriate type of capability would be returned. The resources used for the capability are charged to that particular account 💸.

Now suppose a user on one CCS system within a DCCS network has remote access to account capabilities on several other CCS systems 🌐. That user could create what might be called a super account capability to optimize their use of network resources 👑. The super account capability would actually be a requestor serviced by a process, and the optimization desired would be completely under user control. A few of the more obvious examples are presented:

1. Static Object Creation Optimization
   • a. When a new file is requested, create it on the system with the fastest access or the least cost per bit 📂.
   • b. When a process is requested, create it on the system with the fastest current response or with the least cost per instruction 🚀.
2. Dynamic optimization.

To do dynamic optimization, the super account would not give the requesting process the capability it received from the remote account after static optimization. Instead, it would give out a requestor that it makes function like the actual capability, except optimized 🪄.

• a. When network conditions or user needs charges, files can be moved to more effective systems. Changes in cost conditions might result in file movement. Charges in reliability conditions might result in movement of files and/or in addition or deletion of multiple copies 🗂️.
• b. If system load conditions or CPU charges change, it might be effective to relocate a process. The super account service process could create a new process on a more effective system, stop the old process, move the old C-list and memory to the new process, and start the new process up. The emulation process given to the user would never appear to change 🧚‍♀️.
• c. Similar optimizations can be done on any other capabilities 🌈.

Such a super account can automatically optimize a user's network resources to suit that user's needs without changing the functional characteristics of the objects being optimized 🎀.

Final Note 🎉

The DCCS mechanisms defined in this paper are currently being implemented on a Digital Equipment Corporation PDP-11/45 computer, for use as an experimental protocol on the ARPA computer network [10] 🖥️. The DCCS protocol will also form the basis for a gateway between the ARPA network and Energy Research and Developement Agency's CTR network [11] 🌉. It's the author's hope that the DCCS mechanism will hasten the arrival of the kinds of networks needed to create a truly free market in computational resources 💜✨.

Acknowledgements 🫶

The author would like to thank the administrators and staff of the Computer Research Project at the Lawrence Livemore Laboratory for creating the kind of environment conductive to the ideas in this paper 🌷. Special thanks are due to Charles Landau for many of the C-list ideas implemented in the current RATS system 👏.

References 📚

1. C. R. Landau, The RATS Operating System, Lawrence Livermore Laboratory, Report UCRL-77378 (1975)
2. C. R. Landau, An Introduction to RATS (RISOS/ARPA Terminal System): An Operating System for the DEC PDP-11/45, Lawrence Livermore Laboratory, Report UCRL-51582 (1974)
3. J. E. Donnelley, Notes on RATS and Capability List Operating Systems, Lawrence Livermore Laboratory, Report UCID-16902 (1975)
4. B. W. Lampson, "On Reliable and Extendable Operating Systems", Techniques in Software Engineering, NATO Sci Comm. Workshop Material, Vol. II (1969)
5. W. Wulf, et. al., "HYDRA: The Kernel of a Multiprocessor Operating System", Communications of the ACM 17 6 (1974)
6. P. Neumann et. al., "On the Design of a Provably Secure Operating System" International Workshop on Protection in Operating Systems, IRIA (1974)
7. R. S. Fabry, "Capability-Based Addressing", CACM 17 7 (1974)
8. E. W. Dijkstra, "Cooperating Sequential Processes", published in Programming Languages, F. Genuys, editor, Academic Press, pp. 43-112 (1968)
9. F. A. Akkoyunlu, et. al., "Some Constraints and Tradeoffs in the Design of Network Communications", Proceedings of the Fifth Symposium on Operating System Principles, Vol. 9 No. 5 pp. 67-74 (1975)
10. L. G. Roberts and B. D. Wessler, "Computer Network Development to Achieve Resource Sharing", AFLPS Conference Proceedings 36, pp. 543-549 (1970)
11. "National CTR Computer Center", Lawrence Livermore Laboratory Energy and Technology Review, Lawrence Livermore Laboratory UCRL-52000-75-12, December (1975)

The figures are not included in the online version. Interested readers can obtain a hardcopy version of the documents, including the figures, by requesting a copy of UCRL-77800 from:

Technical Information Department, Lawrence Livermore Laboratory, University of California, Livermore, California 94550

Questions or comments would be appreciated and should be directed to the author 💌:

Though the U.S. mail:

James E. Donnelley, Lawrence Livermore Laboratory L-307, P. O. Box 808, Livermore, California 94550

By telephone: (415)447-1100 ext. 3406

Via ARPA net mail: JED@BBN

"This report was prepared as an account of work sponsored by the United States Government. Neither the United States nor the United States Energy Research & Development Administration, nor any of their employees, nor any of their contractors, subcontractors or their employees, makes any warranty, express or implied, or assumes any legal liability or responsibility for the accuracy, completeness or usefulness of any information, apparatus, product or process disclosed, or represents that its use would not infringe privately-owned rights."