Syndicated Actors for Conversational Concurrency

About this project

Could there be a better way to program communicating systems?

Functional programs are easy to write, but programs that interact with each other and the outside world are much harder.

Programming models like the Actor model and the Tuplespace model make great strides toward simplifying programs that communicate. However, a few key difficulties remain.

The Syndicated Actor model addresses these difficulties. It is closely related to both Actors and Tuplespaces, but builds on a different underlying primitive: eventually-consistent replication of state among actors. Its design also draws on widely deployed but informal ideas like publish/subscribe messaging.

Three big ideas fit together to yield the complete vision:

A few smaller pieces of the puzzle exist alongside the main ideas:

Syndicated Actors

The Syndicated Actor model is a new model of concurrency, closely related to the actor, tuplespace, and publish/subscribe models.

The Syndicated Actor model is, at heart, a mechanism for sharing state among neighboring concurrent components. The design focuses on mechanisms for sharing state because effective mechanisms for communication and coordination follow as special cases.

You can think of it as concurrent object-oriented programming with intrinsic publish/subscribe support.

It is based around actors which not only exchange messages, but publish (“assert”) selected portions of their internal state (“assertions”) to their peers in a publish/subscribe, reactive manner.

A dataspace is a special kind of actor which relays messages and replicates published state from peer to peer. State replication subsumes Erlang-style links and monitors, publish/subscribe, tuplespaces, presence notifications, directory/naming services, and more.

Securing syndicated interaction

Access control is expressed using a generalization of object capabilities to express control over state replication and observation of replicated state as well as ordinary message-passing and RPC. Long-lived capabilities based on Macaroons allow secure delegation and attenuation of authority.

Object capabilities are a natural fit for Actor-style systems (as demonstrated by E and subsequent research and systems based on it), so it makes sense that they would work well for the Syndicated Actor model. The main difference to capabilities for plain Actors is that syndicated capabilities express pattern-matching-based restrictions on the assertions that may be directed toward a given peer, as well as the messages that may be sent its way.

The Syndicated Actor model in context

See here for more on comparisons of syndicated actors with other programming models.

The closest relatives to the Syndicated Actor model are Actors, Tuplespaces, and Pub/Sub:1

In short, despite the fact that the same patterns of interconnection, naming, routing and layering keep reappearing in all sorts of software, our programming models and languages don’t do well at letting us express these patterns. Likewise, firewalls, membranes and system boundaries are ubiquitous, but remain unrepresented and implicit in most approaches to concurrency.

Bringing these concepts into our programming models and programming languages helps eliminate language patterns, simplifying our programs.3

Conversational Concurrency

The purpose of communication is to share state

When programs are written with concurrency in mind, the programmer reasons about the interactions between concurrent components or agents in the program. This includes exchange of information, as well as management of resources, handling of partial failure, collective decision-making and so on.4

These components might be objects, or threads, or processes, or actors; or larger units still, such as whole machines or clusters; or even some more nebulous and loosely-defined concept—a group of callbacks, perhaps. The programmer has the notion of an agent in their mind, which translates into some representation of that agent in the program.

We think about the contexts (because there can be more than one) in which agents exist in two different ways. From each agent’s perspective, the important thing to think about is the boundary between the agent and everything else in the system.

But from the system perspective, we often think about conversations between agents, whether it’s just two having an exchange, or a whole group collaborating on some task. Agents in a conversation play different roles, join and leave the group, and build shared conversational state.

Each act of communication contributes to a shared understanding of the relevant knowledge required to undertake some task common to the involved parties.

That is, the purpose of communication is to share state: to replicate information from peer to peer.

Conversational Concurrency in brief

The idea of Conversational Concurrency can be summarised as follows:5

  1. Agents collaborate to achieve some shared task.
  2. Each task is delimited by a conversational frame.
  3. Within that frame, components share
    1. knowledge related to the domain of the task at hand, and
    2. knowledge related to the knowledge, beliefs, needs, and interests of the various participants in the collaborative group.
  4. Conversations are recursively structured by shared knowledge of (sub-)conversational frames, defined in terms of any or all of the types of knowledge we have discussed.
  5. Some conversations take place at different levels within a larger frame, bridging between tasks and their subtasks.
  6. Components are frequently engaged in multiple tasks, and thus often participate in multiple conversations at once.
  7. The knowledge a component needs to do its job is provided to it when it is created, or later supplied to it in response to its interests.

Existing programming languages lack linguistic support for conversational concurrency, leaving the programmer to fend for themselves. The Syndicated Actor model, the idea of dataspaces, and their supporting DSL are a response to this lack.

Conversational frames, conversational knowledge

Components, tasks, and conversational structure

The conversational state that accumulates as part of a collaboration among components can be thought of as a collection of facts. First, there are those facts that define the frame of a conversation. These are exactly the facts that identify the task at hand; we label them “framing knowledge”, and taken together, they are the “conversational frame” for the conversation whose purpose is completion of a particular shared task.

Just as tasks can be broken down into more finely-focused subtasks, so conversations can be broken down into sub-conversations. Part of the conversational state of an overarching interaction describes a frame for each sub-conversation, within which sub-conversational state exists. The knowledge framing a conversation acts as a bridge between it and its wider context.

If domain knowledge is “what is true in the world” for the purposes of a given conversation, and epistemic knowledge is “who knows what”, the third piece of the puzzle is “who needs to know what” in order to effectively make a contribution to the shared task at hand.

Knowledge of the various interests in a group allows collaborators to plan their communication acts according to the needs of individual components and the group as a whole. In conversations among people, interests are expressed as questions; in a computational setting, they are conveyed by requests, queries, or subscriptions.

The interests of components in a concurrent system thus direct the flow of knowledge within the system.

Language support: Syndicate DSL

The Syndicated Actor model, taken alone, explains communication and coordination among components but does not offer the programmer any assistance in structuring the internals of components.

A handful of Domain-Specific Language (DSL) constructs, together dubbed Syndicate, expose the primitives of the Syndicated Actor model, the features of dataspaces, and the concepts of conversational concurrency to the programmer in an ergonomic way.

See the Syndicate DSL documentation for details of the syntax and meaning of the constructs that Syndicate adds to each underlying programming language.

The language constructs offered by the Syndicate DSL extend the underlying programming language that is used to write a component. They bridge between the language’s own computational model and the style of interaction offered by the Syndicated Actor model.

Each interactive component needs some way of

  1. representing the conversations it is engaged in
  2. mapping incoming events to these conversations
  3. managing the shared understanding that it builds as it works towards the overall program’s goal
  4. cleaning up shared state after partial failure of a component
  5. scoping interactions and shared state inside the program

Facets represent (sub-)conversations

To address these requirements, Syndicate represents conversations with a language construct called a facet. Facets are similar to the “nested threads” of Martin Sústrik’s idea of Structured Concurrency (see also Wikipedia).

Every actor has at least one (root) facet, and all its facets form a tree. Generally speaking, one facet corresponds to one conversation, framing (in the sense of Conversational Concurrency) its children, which each correspond to some sub-conversation within the frame of their parent.

When a parent facet is shut down, all its children are shut down in an orderly fashion, making management of conversational state straightforward.

Each facet publishes (“asserts”) relevant pieces of state (“assertions”) to relevant peers. As its internal state changes, its published assertions are re-evaluated, and any changes are automatically propagated to peers.

Facets also subscribe to assertions emanating from their peers. They do this in a unique way: by asserting their interest in particular fact(s) to the publishing peer. That is, an expression of interest is itself an assertion that can be seen and reacted to by peers.

When a facet terminates, whether normally or as the result of an exception, all the assertions it has published are guaranteed to be withdrawn. Assertions thus subsume Erlang-style monitors/links, “presence” notifications (as seen in, for example, XMPP), and pub/sub mechanisms for optimizing message delivery based on subscriber presence or absence.

A taste of the Syndicate/js DSL

To give some of the flavour of working with Syndicate DSL constructs, here’s a program written in JavaScript extended with Syndicate constructs:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

function chat(initialNickname, sharedDataspace, stdin) {
  spawn 'chat-client' {
    field nickName = initialNickname;

    at sharedDataspace assert Present(this.nickname);
    during sharedDataspace asserted Present($who) {
      on start console.log(`${who} arrived`);
      on stop  console.log(`${who} left`);
      on sharedDataspace message Says(who, $what) {
        console.log(`${who}: ${what}`);
      }
    }

    on stdin message Line($text) {
      if (text.startsWith('/nick ')) {
        this.nickname = text.slice(6);
      } else {
        send sharedDataspace message Says(this.nickname, text);
      }
    }
  }
}

Polyglot and networked programming: Preserves

Interoperation among programming languages and across network links demands a shared data language and a common network protocol.

For components to communicate, they need a common vocabulary.

When Syndicate is used to organise concurrency within a single program, in a single programming language, that language’s own data structures suffice.

But when Syndicate is used to organise larger systems, perhaps written as separate, interoperating programs in many different languages, perhaps communicating via network links (e.g. Bluetooth, Ethernet, or TCP/IP), a common data language is needed.

A new data language called Preserves plays the role of common data language in this project, and a network protocol built using Preserves allows expression of syndicated-actor actions and events across network links.

Preserves: a data model with associated syntax

See the Preserves website for more about Preserves.

From the introduction to the Preserves specification document:

Preserves supports records with user-defined labels, embedded references, and the usual suite of atomic and compound data types, including binary data as a distinct type from text strings. Its annotations allow separation of data from metadata such as comments, trace information, and provenance information.

Preserves departs from many other data languages in defining how to compare two values. Comparison is based on the data model, not on syntax or on data structures of any particular implementation language.

Preserves supports schemas for describing the structure and interesting content of Preserves documents. It has multiple syntaxes for different purposes: one is human-readable, and looks a lot like JSON; another is a compact binary format, suitable for canonicalization and hashing.

Here are some example Preserves documents, written in Preserves text syntax:

Syndicated Actor network protocol

See the protocol specification for more on syndicated communication across network links.

The following Preserves schema describes turns, which are messages to be sent across a network link expressing assertions, retractions of previous assertions, the sending of messages, and synchronization with some remote party.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

version 1 .
embeddedType WireRef .

Assertion = any .
Handle    = int .
Event     = Assert / Retract / Message / Sync .
Oid       = int .
Turn      = [TurnEvent ...].
TurnEvent = [@oid Oid @event Event].

Assert = <assert @assertion Assertion @handle Handle>.
Retract = <retract @handle Handle>.
Message = <message @body Assertion>.
Sync = <sync @peer ref>.

# Definition of Caveat omitted here

WireRef = @mine <MyRef @oid Oid]>
        / @yours <YourRef @oid Oid @attenuation Caveat ...>.

Who I am

I’m Tony Garnock-Jones; tonyg@leastfixedpoint.com; @leastfixedpoint; tonyg on Libera.Chat and HN. I’m a computer science researcher and software developer. I’ve used Linux since the mid-1990s, contributed to open-source software since the late 1990s, and I have a PhD in, well, Syndicate!

See also my personal website.

  1. You might also be interested in chapter 3 of my dissertation, which digs into the concurrency design landscape within which the Syndicated Actor model exists, and considers several other models of computation not discussed here. ↩

  2. I’ve written about various expressions of the Actor model here, and this is a really good survey paper:
    De Koster, Joeri, Tom Van Cutsem, and Wolfgang De Meuter. “43 Years of Actors: A Taxonomy of Actor Models and Their Key Properties.” In Proc. AGERE, 31–40. Amsterdam, The Netherlands, 2016. https://doi.org/10.1145/3001886.3001890. ↩

  3. Chapter 9 of my dissertation goes into lots more detail on this claim, discussing exactly what I mean by “pattern”, “eliminate” and “simplify”. ↩

  4. This section contains edited excerpts from chapter 2 of my dissertation, which goes into the idea of Conversational Concurrency in more detail. It also contains edited excerpts from a talk I gave in 2017 on Conversational Concurrency to Matthias Felleisen’s “History of Programming Languages” seminar class. ↩

  5. Again, see chapter 2 of my dissertation for more. ↩

  6. Yes, there’s a meta-schema available. ↩