[cap-talk] Information Flow in Object-Capability Systems

Bill Frantz frantz at pwpconsult.com
Tue Mar 31 16:52:03 EDT 2009

toby.murray at comlab.ox.ac.uk (Toby Murray) (the author below) on Tuesday,
March 31, 2009 quotes an anonymous reviewer:

>The author claims that buffered data-diodes (concurrent facets with
>shared state) would be the "natural" way to implement data-diodes in
>(a-synchronous) concurrent systems. That claim can be contradicted by
>example.  Simply stateless, message-forwarding capabilities for either
>reading or writing to a file capability (via synchronous or
>a-synchronous message passing) can be provided in many languages. Such
>simple forwarding-capabilities are immune to plan-interference if the
>language's concurrency mechanism respects the causal order of messages,
>like E does (explained in Miller's "Robust Composition"). Of course, the
>author considers building object-capability systems rather than
>programming languages, but then:
>- either an E-like causal order should be imposed to the asynchronous
>messages at the OS level (which is fairly easy to do)
>- or else the state should be shared only at the OS level and its
>effects should be completely hidden to the application layers
>The author provides a useful and interesting solution for the latter

In KeyKOS, EROS, and CapROS, it may seem easy to provide something as
strong as "E-like causal order", but it isn't and none of these systems
actually provide it. An explanation:

These systems do not queue messages, instead they queue senders in FIFO
order. When a domain/process becomes available, the process at the head of
the queue is restarted. Most of the time, it will re-issue its "send
message" instruction, and the message will be sent in causal order.

However, there are a number of cases where it won't re-issue the "send
message" instruction, including a stopped meter, and changes to the state
made with a domain key. In KeyKOS, these cases are handled with a bit of
kernel logic called the worrier. If the receiving domain has not been sent
a message within a fixed period, the next domain on the queue is restarted.
Should the worrier restart a second domain, there could be two running
domains trying to send, and the one that will succeed is the first one to
be dispatched.

But wait, there's more. When restarting from a checkpoint, all order
information is lost. It is a free-for-all among all the queued
domains/processes. The first one dispatched sends its message, and the rest
are queued in dispatch order. (Servicing page faults can affect this order,
but that is only another source of non-causal queuing order.)

I'm not sure what "the state should be shared only at the OS level" means,
but that's the option to use with KeyKOS, EROS, and CapROS.

Cheers - Bill

Bill Frantz        | Airline peanut bag: "Produced  | Periwinkle
(408)356-8506      | in a facility that processes   | 16345 Englewood Ave
www.pwpconsult.com | peanuts and other nuts." - Duh | Los Gatos, CA 95032

More information about the cap-talk mailing list