Demand Monitors – Heart and Soul of RDP

The demand monitor is perhaps one concept that motivates the rest of Reactive Demand Programming, and distinguishes it from nearly all other programming models. The idea is extremely simple: we can aggregate incoming demands, and observe the demands at any given instant as a set. The idea of demand corresponds to a request, command, or query that is maintained over continuous time, modeled in RDP as a signal.

A demand monitor is modeled in RDP as a tightly coupled pair of behaviors, `de` and `mon`. They work as follows:

  • one can make demands on `de`, one at a time. (de :: (sig x) ~!> (sig ()))
  • one can observe the set of demands using `mon`. (mon :: (sig ()) ~!> (sig (set x)))

For Haskell, the type-class SigSelect, mentioned in my signals article, is required for a signal type to support demand monitors. I use a simple list [x] for the set type because I don’t want to overly constrain the Haskell types, and developers are simply expected to apply some self-discipline and treat this as a set. The notation (~!>) is one I’m experimenting with to indicate an RDP behavior type (it’s clearer to my eyes than (~>)).

History

Demand monitors were part of my initial conception of RDP, except I had first envisioned them as a single capability, which I had called a ‘mirror’. (mirror :: (sig x) ~!> (sig (set x))). My earliest formulation of RDP was essentially a statement of the form:

when F(X), F(Y), F(Z) are evaluated synchronously (in overlapping time), the meaning of F(X) can be a function of the form F’(X,{X,Y,Z}). And, similarly, F(Y) is F’(Y,{X,Y,Z}), and F(Z) is F’(Z,{X,Y,Z}). In these cases, {X,Y,Z} is the set of arguments to F, such that if X=Y then F(X) = F(Y) is assured, and the spatial organization or histories F(X), F(Y), and F(Z) are not relevant. These are desirable properties for reasoning about a system, and optimizing it. If we must distinguish F(X) from F(Y), it is sufficient to guarantee that X and Y are different values, perhaps by use of a GUID.

The simplest, most primitive example of this behavior would be where F strictly returns the set of synchronous inputs – i.e. where F’(x,xyz) = xyz, such that F(X)={X,Y,Z} when F(Y) and F(Z) are synchronously active. Given suitable access to set manipulation or query operations, all stateless behaviors could be built from pure functions and this primitive that returns its entire set of inputs. I.e. this is the notion of identity without state – like a perfect ‘mirror’, the state we observe depends entirely on the observers.

Agents interacting with such a mirror can observe, communicate, coordinate with their fellow agents, even without a direct reference between them. There are other advantages to this model, when compared to queueing – i.e. the set-based aggregation allows agents to decide which requests have highest priority, or to arrange their behaviors so as to solve many problems at once. Use of fine-grained mirrors can be an effective, securable basis for open distributed constraint programming.

Mind you, this was in early April 2010, months before I considered temporal semantics or decided to model the signals more formally and explicitly.

It turns out the ‘mirror’ notion has a lot of issues that I did not like very much, that ultimately led to development of the ‘demand monitor’.

  1. Terminology. The word ‘mirror’ is associated with reflection, both for the obvious reasons and Gilad Bracha’s paper Mirrors: Design Principles for Meta-level Facilities of Object-Oriented Programming Languages where ‘mirrors’ provide a capability-secure approach to language reflection (I do recommend this paper).
  2. Simplicity. A lot of my pseudocode sketches had developers using a sort of ‘sentinel’ value for querying the mirror, so that the value could be filtered out. This seemed like a lot of unnecessary pain.
  3. Security. By splitting the mirror into separate facets for issuing demands vs. monitoring them, it is much easier to control access using the principles of object capability security.
  4. Feedback. RDP’s equivalent to divergence is a fixpoint feedback loop that does not settle. A good analogy is placing a microphone near a speaker. Fortunately, this sort of problem is usually quite obvious (like microphone feedback, such problems tend to ‘scream’). Feedback can be valuable, but we do not want it to happen by accident. Separating demand and monitor facets reduces risk of accidental feedback loops, and makes static analysis easier. I would like to see explicit annotations where developers aim to leverage feedback.
  5. Optimization. Separation simplifies optimization, and reduces need for it. We are not logically a set around for each input. We can eliminate dead code and specialize if either the demand or monitor facet is provably unused or constant. With a mirror, we would depend much more heavily on an intelligent optimizer.

The above conditions led me to separate the input and observation facets, and thus to ‘demand monitors’.

Aside: I decided on the word ‘demand’ for demand monitors and RDP for several convergent reasons. First was its connotations with the market and other demand-driven systems – i.e. demand is something we typically understand as changing, rising, and falling continuously over time, and to which we can react. Second, ‘demand’ in English means roughly ‘authoritative request’; that demands are ‘authoritative’ corresponds to the object capability model. Third, I was tickled to have (de,mon)s in my language. (You could flip this around into (mon,de)s if you prefer the world to supernatural entities. >;^)

Roles of Demand Monitors

  • broadcast communications – By sharing the `mon` facet and keeping the `de` facet private, we have one-to-many broadcasts (like radio). By sharing `de` and keeping `mon` private, we can support many-to-one communications (like e-mail). By sharing both, we get many-to-many communication (like wikis or bulletin boards).
  • plug-in extensible systems – adding external services and resources to an existing system in a secure manner requires sharing capabilities. However, RDP does not allow behavior into state (the ‘no looking back‘ property). This leaves only one option: demand monitors.
  • simple concurrent constraints – by observing demands and environment simultaneously, a developer can easily prioritize them, and build a plan that meets many constraints. RDP does not directly support constraint modeling, but modeling constraints with a demand monitor is very natural.
  • map-reduce filtering – by using fine-grained demand monitors per key, plus a monitor for the set of keys, we can easily partition inputs into different sets for further processing. Live, reactive forms of map-reduce are feasible, assuming a suitable implementation for the demand-monitor discovery mechanism.

How to Obtain a Demand Monitor

The basic idea is that we model an abstract, infinite space of demand monitors. This ‘abstract space’ is nothing special – just a function or behavior that allows two manipulations: partitioning, and fetching a demand-monitor. An initial abstract space is provided from the runtime to each application.

dmsRoot :: DemandMonitorSpace  
(rootde,rootmon) <- getDemandMonitor dmsRoot "foo"
dmsBar <- getPartition dmsRoot "Bar"
(barde,barmon) <- getDemandMonitor dmsBar "foo"

In this case, barde is distinct from rootde despite having the same name (“foo”) because they come from different zones. In a sense, we have `/foo` vs. `/Bar/foo` – a sort of minified filesystem, minus the special ‘.’ and ‘..’ mechanisms.

Security is achieved by asymmetric path construction – i.e. the holder of ‘dmsBar’ has no way to construct ‘dmsRoot’. The creator of dmsBar can easily wrap the capability with auditing and revocation mechanisms.

Distributed systems raise the challenge slightly, since we must still have security (cryptographically unguessable capabilities) but we must also ensure that two subsystems granted the same ‘DemandMonitorSpace’ and using the same guessable names (“Bar”, and “foo”), will generate the exact same capabilities. One interesting way to achieve this is by use of an HMAC mechanism starting from a large secure-random number: GUID of dmsBar might be HMAC(GUID of dmsRoot, “BarPartition”). The initial GUID is then supplied by the IDE or runtime per application. (Of course, the simple way to achieve it is by calling home. The HMAC mechanism is only useful if you need some sort of partitioning tolerance as well.)

Note: we cannot ask for ‘new’ partitions or ‘new’ demand monitors (where I use ‘new’ in the OOP sense). Asking for ‘new’ things does not make sense in RDP, since (a) we can’t remember old things (no looking back), and (b) everyone who asks must receive the same values (due to spatial commutativity and spatial idempotence). So we instead model demand monitors as having always existed, and we are just ‘discovering’ them. A similar mechanism is used to access state.

About these ads
This entry was posted in Concurrency, Language Design, Modularity, Open Systems Programming, Reactive Demand Programming, State. Bookmark the permalink.

3 Responses to Demand Monitors – Heart and Soul of RDP

  1. David, if you use notation like (de :: (sig x) ~!> (sig ())), could you please add a short English description of what it means? Thanks.

  2. Pingback: Sirea RDP Progress Update: Demand Monitors are Working | Awelon Blue

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s