This is a copy of a paper that was presented at the Third International Conference on Computer Communication, Toronto, Canada, August 3-6, 1976. You can find it in the proceedings of that conference on pages 432-440.

The content in this paper was initially published in an internal LLNL document:

J. E. Donnelley, "DCAS" - A Distributed Capability Access System, Lawrence Livermore Laboratory Report UCID-16903, August 1975.

This online version of the refereed publication from the third ICCC resulted from scanning and OCRing a computer generated original. Since the optical character recognition is certainly not perfect, if you notice any errors, please let me (<> know. Thanks!

A note on the references - to jump to the references section of the paper to look at a citation, click on the numeric reference entry in bracketed references. E.g. in "[Bal71-1]" click on the 1.

A note on the figures - since the figures were also scanned in, they are certainly not perfect. In case you are unable to read some of the detail on the versions included with the text, you can click on the figures themselves to see somewhat larger versions where more detail is visible.

If you are somehow looking at a hardcopy version of this paper and wish to view it on the WWW, you can find it at the URL:

Publication date: August 3, 1976. Last update to this HTML version, August 18, 2006 --Jed

A Distributed Capability Computing System (DCCS)

James E. (Jed) Donnelley
Lawrence Livermore National Laboratory, Livermore, California, USA
"James E (Jed) Donnelley" <>
One component of the resource sharing problem, that of designing protocols and mechanisms to access standardized resources, is solved. The first step in the solution is the definition of a standardized computer resource based on a set of interprocess communication primitives that are introduced. Building upon these primitives, this paper presents a mechanism for sharing the standardized resources that is independent of the resource types. Applications are presented which provide transparent network resource optimization and an automated money exchange.

Distributed, Capability, Network, Protocol, Process, Port, Communication, Synchronization


The motivation for the Distributed Capability Computing System (DCCS) is the advancement attainable through resource sharing. There are many components of the problem of resource sharing that will always be with us: creation of effectively standardized resources, optimization of the available communication channels, minimization of the effects of hardware errors, translation between semantically equivalent resources to increase their availability, etc. The tenet of this paper is that one portion of the computer resource sharing problem, that of designing protocols and mechanisms to allow access to standardized resources through standardized communication channels, can be isolated and solved.

Solving this portion of the resource sharing problem involves two components: defining a standard resource and constructing a mechanism for sharing such a resource across system boundaries. The definition of the standard resource can be viewed as an integration and extension of several ideas that have appeared in the literature.


The concept of a software "port" [1, 2] is analogous to that of a hardware port (Fig. 1). Just as physical ports allow processors to communicate via hardware channels, logical ports allow processes to communicate via connections which may or may not span processors. Unlike hardware ports, however, where access is granted by an engineer, access to software ports is generally granted by the supporting operating system. The function of maintaining a list describing the ports and other resources available to a process is common to all operating systems. By the time the generally accepted name of such a list emerged as capability list or C-list [3]. capability-based interprocess communication had extended beyond the synchronization and communication primitives usually associated with ports.


As motivation for extending the port concept to that of a capability, consider the communication between a process and its supporting operating system. The operating system can not only communicate information to the process, but can also grant the process other ports. If we are to model the communication between a process and its supporting operating system with ports, we must allow ports as well as information to pass over the connection. When so extended, a port becomes a capability [3 - 7].

The Capability Computing System (CCS)

To introduce the interprocess communication primitives needed to implement the DCCS mechanism in a type-independent manner, a simplified capability-based operating system, CCS, is described below.

A CCS process consists of two parts: its memory and its C-list. When a process is started, it executes instructions from its memory much like a commercial processor. The analogs to input/output instructions are termed invocations on capabilities. A process is encapsulated by its C-list just as a processor is by its I/O devices.

This key concept of invocation can be further clarified by the hardware analogy to ports. When a processor reads from or writes to a port, it first specifies a memory area to be used in the information transfer. By analogy, a capability invocation must specify both memory and C-list areas for the passed and returned parameters. The CCS invocation instruction contains two numbers: the index of the invoked capability and the address of a parameter template. The parameter template contains 8 numbers consisting of a base address and a count to specify each of 4 areas: information to pass, capabilities to pass, information to receive, and capabilities to receive.

In this paper we describe the CCS capabilities using the following syntax:

[letter]. [info passed];[caps passed]>[info received];[caps received]

Each of the lettered lines represents a valid invocation of the capability being described, and names the parameters of each type that are passed and received. The individual areas are often broken up with commas to convey semantic information. For example, the invocation

x. II, 12; > I3; C1

indicates that two data items, Il and I2, are passed, and that one data item and one capability are returned. The empty field indicates that no capabilities are passed. Items enclosed in quotes signify literal strings.

Process Capability

a. "Read", address; > data;
b. "Write", address, data; > ;
c. "Take", index; > ; capability
d. "Give", index; capability > ;
e. "Find", index, count; capability > result, index;
f. "Start"; > ;
g. "Stop"; > ;

Semantics: The "Read" and "Write" operations allow access to the process's memory. For example, in the "Read" operation, the literal string "Read" (or a recognizable OP code) is passed along with an address. The data word at the address is returned. The "Give" and "Take" operations allow access to the process's C-list. For example, the "Give" operation passes the string "Give", an index into the C-list, and a capability to be stored at the passed index. Such a stored capability could be invoked by the process if it were "Start"ed.

The "Find" operation allows a slightly optimized sort of compare operation for capabilities. The process's C-list is searched, starting at the passed index, for the passed capability until either:

  1. The passed capability is found in the C-list. In this case, the operation returns "Yes" and the first index where the capability was found, or

  2. The count is exhausted. In this case the operation returns "No" and the passed index plus count.

Nil Capability

When a process is initially created its C-list contains only Nils. These are empty place holders. Nil always returns "Empty"

The CCS Extension Capabilities

These capabilities allow a process to set itself up to service invocations on capabilities that it can create. The mechanism is somewhat analogous to the "Well-Known Port" concept in Ref. 2. One capability is needed to start things off: the server capability.

Server Capability

Two capabilities were introduced above besides the server: the requestor and request capabilities. These capabilities will be described as the invocations on the server are described.

The "Create requestor" invocation creates and returns a requestor capability. The number that is passed is associated with the requestor. The requestor capability is the new capability being created. Any sort of invocation can be performed on a requestor. This is their whole reason for existence. A process with a server capability can make any of its requestors look like any kind of capability.

The "My requestor?" invocation can be used to determine whether a capability is a requestor on the invoked server. It returns either:

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

The last invocation "Wait"s until something that requires the server's attention happens. There are two important events that a service routine needs to be notified about. If the last capability to a requestor is overwritten so that the requestor cannot again be invoked until a new one is created, the "Wait" returns:

"Deleted", requestor number, 0; Nil

The last two parameters, O and Nil, are just filler for the two unused parameters. When a "Wait" returns "Deleted", the service routine can recycle any resources being used to service the numbered requestor (e.g., the requestor number).

The most important event that causes a "Wait" to return is when one of the requestors for the server is invoked. In this case the server returns:

"Invoked", requestor number, PD; request

The third parameter, labeled PD, stands for Parameter Descriptor. It describes the number of each kind of parameter passing each way during a requestor invocation. It consists of four numbers: data bits passed, capabilities passed, data bits requested, and capabilities requested. These correspond to the count portions of the parameter template.

The last parameter received; the request capability, is used by the serving process to retrieve the passed parameters and to return the requested parameters to the requesting process. Accordingly, it has the following invocations:

Request Capability

a. "Read parameters"; > (The passed parameters)
b. "Return", (The return parameters) > ;

The "Return" invocation has the additional effect of restarting the requesting process. In both the above invocations mismatched parameters are truncated or padded with 0s and Nils.

Note that in the server mechanism the invoking process and the serving process are completely protected from one another. To illustrate this feature by analogy, consider the outside teller windows often seen at banks. These windows usually contain a drawer that can be opened by the teller or by the customer, but not by both. Except for this drawer the teller and customer are physically separated. The drawer in the requestor mechanism is the request capability. The customer must trust the teller with an endorsed check passed through the drawer, but not with a wallet or purse still outside. The teller must trust the customer with the money returned, but not with the rest of the bank's cash on hand.

Also, invocations on a server's requestors are queued until the server is "Wait"ed upon. This is one reason that a request is given a separate capability. The serving process can, if it chooses, give the request to some other process for servicing, while it goes back and waits on its server capability for more requests. The corresponding situation in the teller window analogy would be the case in which the teller gives the endorsed check to someone else in the bank or even in some other bank for service so that the teller can return to waiting customers. The request capability points back to the requesting process so that the return can be properly effected.

Consider the well known semaphore [8]. The semaphore service routine keeps a table containing the semaphore values for each semaphore that it is servicing. It also keeps a list of queued requests that represent the processes waiting for the semaphore to be "V"ed. The invocations on a semaphore are given below.


a. "P"; > ;
b. "V"; > ;

A diagram and flow chart for the semaphore serving process are given in Figs. 2 and 3. All the flow charts that are given include most of the basic capability invocations, but do not include detailed descriptions of table searches. The table structure for the semaphore service routine includes entries for each supported semaphore. Each entry contains the semaphore value and a link into a list of pointers to the requests queued in the semaphore (if any). When a capability invocation is included in a flow chart, it is given as the capability name followed by a colon and then the invocation parameters.


The CCS needs some capabilities that create the primitive capabilities. It must also account for such services.

Account Capability

a. "Deposit", amount; account > result;

The "Deposit" invocation moves money from the passed account into the invoked account and returns:

  1. "Invalid" if the passed capability is not a valid account. The servicing process can determine validity with the "My requestor?" invocation on the account server capability.
  2. "Exhausted" if there is not enough money left in the invoked account.
  3. "OK" if the transfer was effected.

Using these account capabilities, creator capabilities can be set up as follows.

[type] Creator Capability

a. account> result; [type] capability

A capability of the specified [type] (e.g., process, server, etc.) is created if possible and charged to the account. A typical capability servicing routine would "Deposit" money from the passed account capability into its own account to charge for services. If the "Deposit" ever fails, the serving routine can recycle the resources being used for the service and begin returning "Empty" or "Pay up!" to requests on the overdrawn capability.

The Insertion Property

The insertion property for ports [2] asserts that a process can be transparently inserted into the connection between any two other processes (Fig. 1). A similar property for capabilities would assert that a process can always be transparently inserted between a serving process and a requesting process. In the CCS, such an insertion property would require that a process be able to make a requestor look like any other capability. A CCS process cannot, in general, perform such emulation. For example, the ability of an account server to validate a passed account with the "My requestor?" invocation is needed to stop attempts to counterfeit accounts. The places where such exact emulation is possible, however, play an important role in the DCCS implementation. The DCCS mechanism can make any remote capability look exactly (except for timing) as if it were local.

A DCCS Implementation

To construct a mechanism for invoking remote capabilities from a CCS system, a communication facility is needed.

Network Capability

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

It is assumed that the "Input" invocation waits until a message is available and that the "Output" invocation returns immediately after queueing the message for output.

The following description of the DCCS implementation is broken into two parts. A brief overview of the important mechanisms is followed by a more complete description.

The intent of the DCCS mechanism is to allow capabilities on one host to be invoked by processes on other hosts having the appropriate capabilities. To do this each host keeps a list of capabilities that it supports for use by other hosts. Each host also supports a server which gives requestors to local processes that are made to appear as if they were corresponding capabilities supported by remote hosts. When one of these emulated requestors is invoked, its parameters are passed by the emulating host through the network to the supporting host. The supporting host then sees to it that the proper capability is invoked and passed the parameters. When the invoked capability on the supporting host returns, the return parameters are passed back through the network to the emulating host. The emulating host then returns the return parameters to the requesting process

For example, take the "Read" request on a process diagrammed in Fig. 4. When the emulated process (a requestor) is invoked, the emulating process receives "invoke", requestor number, PD; request. The requestor number that is returned is actually a descriptor consisting of two numbers: host number and capability number. These descriptors are called Remote Capability Descriptors (RCDs). An RCD identifies a host and a capability supported by that host. After receiving a request, the emulating process reads the parameters passed by the requesting process and sends them along with the parameter Descriptor to the remote host in an "Invoke" message.

When the remote host receives this information, it passes the parameters to the supported process capability by invoking it and specifies the proper return parameters as noted in the Parameter Descriptor. When the invoked process returns, the returned data is passed back through the network to the emulating host in a "Return" message. The returned data is then returned to the requesting process by performing a "Return" invocation on the request capability initially received by the emulating host. When the requesting process is awakened by the return, it will appear exactly as if a local process had been "Read".

This works fine when the parameters being passed and returned consist simply of information, but what happens when there are capabilities involved? In this case the routines use the existing remote capability access mechanism and pass the appropriate descriptors. As an example, the "Take" invocation on a process is diagrammed in Fig. 5. The only essential difference is the fact that a capability has to be returned. When the capability is returned on the supporting host , it is added to the supported capability list and a new descriptor is returned to the emulating host. When the emulating host receives the descriptor, it creates a new requestor with the returned descriptor as its requestor number and returns the requestor to the invoking process. The requestor so returned acts as the capability taken from the remotely accessed process and can be invoked exactly as if it were the capability "Take"n from the remote process.

Issues To Be Resolved

In a complete DCCS implementation, there are several issues that must be resolved. These are presented below.

Timing (blocking)

Invocations can take a very long time to complete. The emulating host can handle the problem of blocking later requests by adding the received request capability to a list of pending requests after sending the "Invoke" message. On the supporting side it can be handled by setting up an invocation process to actually invoke the capability and to return the parameters when they are available.

These additional mechanisms add the complication of multiple requests active between hosts. These requests are identified by a Remote Request Number (RRN). The RRN is an index into the list of pending requests.


If host A is requested to pass a capability to host B, A must first ensure that the capability is not already local to B. This can be done by ensuring that the capability is not already a requestor that A is servicing. When such a requestor is to be passed, the RCD sent indicates to B that the capability is in its support list and can be passed directly.


If B tries to invoke a capability in A's supported list, should A allow B 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 if it has been granted through the standard invocation mechanism, each host must maintain a bit vector indicating which hosts have access to a given capability.


This variation on the Loop problem comes up when A passes a capability to B who then wants to pass it to C. B may unambiguously specify which capability is to be passed by sending C the Remote Capability Descriptor (RCD) that A knows it by. The RCD indicates that the capability is supported on A. If C then tries to invoke the capability, however, A might not believe that C should have access to it.

B must tell A, "I, who have access to your capability, want to grant it to host C." To do this, another message type, the "Give" message, is used.


If B sends the "Give" message to A and then sends the RCD to C, C may try to use the RCD before the "Give" is received by A. 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.


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

a. Delete A's validation bit in the bit vector for tile specified capability, and
b. Delete the capability from the supported capability list if there are no hosts left that require its support

This function requires a "Delete" message.

DCCS Message Formats and Flow Charts

The following is a summary of the DCCS message formats:

a. "Invoke", Cap. No., RRN, PD, data, RCD list
b. "Return", RRN, data, RCD list
c. "Give", Cap. No., Host. No.
d. "Ack"
e. "Delete", Cap. No.
f. "Error", message

The flow charts in Figs. 6, 7, 8, 9, and 10 give the logical essentials of the DCCS mechanism. Issues such as system restart and recovery, network malfunctions, message size limitations, resource problems, etc., are not included. These issues are not unique to the DCCS and their solutions are not pertinent here. In the flow charts, abbreviations are used to indicate the processes used as C-lists: CSL - Capability Support List, RRL - Remote Request List, and IPL - Invocation process List.

The table manipulation is not 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. The final table is a message buffer containing the pending "Invoke" and "Return" requests. To avoid hazards in 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.


Network Resource Optimization

An application that graphically demonstrates the flexibility of the DCCS is the sort of automatic network optimization that it facilitates. To illustrate, suppose that a user on one system has accounts on several others. Further suppose that each system supports a file capability for data storage that is often used by the user's programs. For such capabilities, there are at least three components that can be optimized: cost, reliability, and interactivity.

To automatically optimize these components, the user can create a process to emulate a file creator capability. There are two kinds of optimization that such an emulated file creator can perform: static and dynamic.

Static Optimization

When a new file is requested, the emulator can create it on the system with what is currently the least cost per bit, on the system that is currently the most interactive, or on the most reliable system. Such a statically optimized file can be given directly to the user's requesting program.

Dynamic Optimization

Instead of giving out such a statically optimized file directly, the emulating process can give an emulated file that it can then dynamically move around to optimize under changing network conditions. Such a simulated file can even be maintained on several systems for reliability. The CCS requestor mechanism allows this emulation to be done transparently to the user's program.

Automated Money Exchange

An interesting application of the DCCS is the setting up of a process to implement a money exchange service. When a routine needs a resource on host B, but only has an account on host A, it could invoke the money exchanger as follows.

Money Exchanger Capability

a. "Current rate", "B", amount; A account> result; B account
b. "Stop order", "B", amount, value; A account> result; B account

The first invocation requests a B account exchange for the amount specified from the A account at the current rate. The second invocation requests that such an exchange take place only when the value of a B unit relative to an A unit rises above the passed value. All of the other typical Wall Street transactions are possible.

An Implementation Note

The DCCS mechanisms defined in this paper are currently being implemented on a CCS-like system [4] for use as an experimental protocol on the ARPA computer network [9]. The DCCS protocol will also form the basis for a gateway between the ARPA network and the Energy Research and Development Agency's CTR network [10].

It is the author's hope that the DCCS mechanism will hasten the approach of the kind of networks that are needed to create a truly free market in computational resources.


The author would like to thank the administrators and staff of the Computer Research Project at the Lawrence Livermore Laboratory for creating the kind of environment conducive to the ideas presented in this paper. Special thanks are due to Charles Landau for many of the C-list ideas as implemented in the current RATS system [4].

This work was supported in part under Environmental Protection Agency contract #EPA-IAG-D5-E681-DB and in part under Department of Transportation contract #[RA] 76-12. The work was performed under the auspices of the U.S. Energy Research and Development Administration under contract No. W-7405-Eng-48.


1. [Bal71]
R. M. Balzer,
"Ports - A Method for Dynamic Interprocess Communications and Job Control,"
Proc. SJCC, 1971, Vol. 38.
2. [Akk75]
F. A. Akkoyunlu, K.Ekanadham, R. V. Huber,
"Some Constraints and Tradeoffs in the Design of Network Communications," Proceedings of the Fifth Symposium on Operating System Principles, 1975, Vol. 9, No. 5, pp. 67-74.
3. [DeV66]
Dennis J. B., and E. C. Van Horn,
"Programmed Semantics for Multiprogrammed Computations," March, 1966, Communications of the ACM, Vol. 9 No. 3, pp. 143-145.
4. [Lan75]
C. R. Landau, The RATS Operating System, Lawrence Livermore Laboratory, Report UCRL-77378 (1975).
5. [Lam69]
B. W. Lampson, "On Reliable and Extendable Operating Systems,"
Techniques in Software Engineering, NATO Sci. Comm. Workshop Material, Vol. II (1969).
6. [Wul74]
W. Wulf et. al., "Hydra: The Kernel of a Multiprocessor Operating System," Computer Networks 3, 389 (1979). Also in Proc. Fourth Communications of the ACM 17, 6 (1974).
7. [Neu74
P. Nuemann, et. al., "On the Design of a Provably Secure Operating System," International Workshop on Protection in Operating Systems, IRIA (1974).
8. [Dij68]
E. W. Dijkstra,
"Cooperating Sequential Processes," published in Programming Languages, F. Genuys, editor (Academic Press, 1968), pp. 43-112. Lawrence Livermore Laboratory Report UCRL-52000-75-12, December 1975.
9. [RoW70]
L. G. Roberts and B. D. Wessler,
"Computer Network Development to Achieve Resource Sharing," AFIPS Conference Proceedings, 3, 1970, 36, pp. 543-549. Lawrence Livermore Laboratory Report UCRL-52000-75-12, December 1975.
10. [CTR75]
"National CTR Computer Center," Lawrence Livermore Laboratory Energy and Technology Review, Lawrence Livermore Laboratory Report UCRL-52000-75-12, December 1975.

Author Biography

James E. [Jed] Donnelley: was born in Palo Alto, California, on July 5, 1948. He received a B.S. degree in Mathematics (1970), a B.A. degree in Physics (1970), and an M.S. degree in Mathematics (1972) from the Davis campus of the University of California.

He has been a member of the Computer Research Project at the Lawrence Livermore Laboratory (LLL) since 1972. He has participated in several research projects including predominately the Research In Secured Operating Systems (RISOS) project; has served as the LLL technical liaison to the ARPA computer network; and has participated in the design and development of a capability list operating system. He is currently a co-principal investigator for a contract with the Department of Transportation to develop a Transaction Controller to manage interactions between distributed computer resources.

Mr. Donnelley is a member of the Association for Computing Machinery and the IEEE Computer Society.

Contact the author for comments about this page.