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:
http://www.webstart.com/jed/papers/DCCS/.
Publication date: August 3, 1976. Last update to this HTML version, August 18, 2006 --Jed
"James E (Jed) Donnelley"
<jed@webstart.com>
http://www.webstart.com/jed/
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.
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.
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:
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:
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 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.
a. "Deposit", amount; account > result;
The "Deposit" invocation moves money from the passed account into the invoked account and returns:
Using these account capabilities, creator capabilities can be set up as follows.
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 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.
To construct a mechanism for invoking remote capabilities from a CCS system, a communication facility is needed.
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.
In a complete DCCS implementation, there are several issues that must be resolved. These are presented below.
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.
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.
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.
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.
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.
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.
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.
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.
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.
