Lost in the flood #1: programming, Japanese gardens, music, machine learning

The problem: an ever expanding set of Chrome tabs of read/study/watch/respond-to later material. I’m trying a new solution: put the links in a blog post, write why I haven’t closed the tabs, close the tabs. (And come back to them later. Maybe.)

Let’s go.

What is embodied programming? blog post by Alex McLean (@yaxu). Alex is trying to give a name to something he’s calling embodied programming. From a quick skim I think it’s related to programming in a cyber-physical loop with the machine. But I need to read Alex’s post properly to be sure.

I first encountered the term cyber-physical in a paper by Andrew Sorensen (@digego). Programming With Time – Cyber-physical programming with Impromptu (Sorensen and Gardner 2010). Andrew Sorensen recently posted a video of his latest work: Physics Playroom at QUT’s new Science & Technology precinct, and gave a detailed technical description on the extempore mailing list. Physics Playroom is an impressive piece of interactive programming making use of a huge aggregated video wall, a cluster of computers, and bank of multi-touch screens capable of simultaneously interacting with a hoard of school kids. Playroom is developed in Andrew’s latest live coding system extempore. (If you’re reading this Andrew, thanks very much for answering my question in such detail!)

Emotional responses to music: The need to consider underlying mechanisms (Juslin and Västfjäll 2008). Related to my recent emotional response on the music-dsp mailing list.

One thing I did find time to watch was Dream Window: Reflections on the Japanese Garden (1992) a stunning documentary. IMDb describes it as “Exquisite exploration of landscape and Toru Takemitsu’s music for a Japanese moss garden.” Highly recommended.

My interest in Japanese gardens arose from an ongoing reflective process concerning software design. I was thinking about the concept of negative space — the space around things — the “anti-object”. This lead me to the related (but I don’t think synonymous) Japanese word “ma(here’s another definition of “ma”, and an interesting discussion about Ma at Metafilter). In the process I found MA: Space/Time in the Garden of Ryoan-Ji a video artwork by Takahiko Iimura. The artist’s notes about the work provide an interesting insight into the compositional process. I would like to know more about ma.

Generic programming with C++ concepts and Haskell type classes—a comparison (J.F. Bernardy et al 2010). Lately I’ve been writing C++ code that is better expressed using compile-time polymorphism (templates) than C++’s good old runtime polymorphism (virtual functions). I’ve been thinking about the not-yet-extant C++ concept specifications, which lead me to the linked paper. My knowledge of Haskell is limited. The relation between C++ templates and Haskell type classes has been on my radar since I encountered Bartosz Milewski’s Monads in C++ blog post a couple of years back.

The Fast Cauchy Transform and Faster Robust Linear Regression (K.L. Clarkson et al 2012) paper at arXiv.org and summary at Nuit Blanche (via @IgorCarron). Fast, Robust, Randomised, what more could you want? Fast L1 regression is a hobby of mine. If nothing else this paper will give me a chance to practice my Linear Algebra.

Machine learning – Random forests video of lecture by Nando de Freitas. Random forests, aka decision forests, and ensemble methods. Seems like something I should know more about.

NI have released Traktor DJ for iPad. I am intrigued by the UI design.

Striking it Richer: The Evolution of Top Incomes in the United States (Updated with 2011 estimates) by Emmanuel Saez (via @accessjames). My version of following the movie stars.

A brief meditation on two-party message exchange

When two parties communicate, what are the possible patterns of message exchange?

Here’s what I’ve come up with so far:

(Updated June 22, 2013 with causality arrows, failure modes, sequences and reordering, streams, non-deterministic communication.)

Send


Send

Also known as: procedure call, one-way, unidirectional, post, fire and forget, In-Only, Out-Only, request (R), trigger, event, notification, command, producer-consumer.

At this level “sending a message” is the ultimate primitive (although it decomposes into: prepare, post, transport, deliver, receive).

Send failure modes

Send, transmission failure

Send, receiver failure

Also known as: unreliable transport.

A message may fail to be delivered, or the receiver may fail to process it (either intentionally or unintentionally). Sometimes message transport and processing is guaranteed to be reliable and these failure modes don’t arise.

Sequence (in order, out of order)

Sequence, in order

Sequence, out of order

Order of arrival may or may not be guaranteed.

Stream

Infinite stream:

Infinite stream

Finite stream:

Finite stream

Also known as: Rx IObserver protocol.

Request-Reply


Request-Reply

Also known as: function call, round-trip, request/response (RR), In-Out, Out-In, call-response, request-result, remote procedure call, polling, solicit-response, query-response.

The reply may provide useful information, or simply acknowledge receipt of the request. The reply might be optional (“In Optional-Out”). Spector (1982) also considers the three message exchange: request/response/acknowledge-response (RRA) . This may not be necessary when message transport is reliable.

Request-Multi-reply


Request-Multi-reply

A single request results in a number of reply messages.

Also known as: progress callback.

Each reply reflects a phase of a progressive process.

Subscribe-Notify


Subscribe-Notify

Also known as: observer, periodic timer, streaming updates, event driven, Hollywood principle.
Note that this is not the same as the multi-point publish-subscribe distribution pattern.

The final acknowledgement is required for the subscriber to be sure that it won’t receive any further notifications.

An implicit subscription variant exists where notifications are sent without the client subscribing (like spam). Maybe that’s called Advertising.

One-shot notification

Normal case:
One-shot notification

Canceled case:

One-shot notification (canceled)

Also known as: one-shot timer, delay, asynchronous completion notification, future, cancelable-future, callback.

Non-deterministic communication

Non-deterministic exchange

If both parties simultaneously send a message to the other there can’t be any guarantee about the order of arrival at each site. For example, a cancellation message could be sent while a notification is already in-flight, as shown below.

Cancellation after notification

?

Do you know other patterns? Let us know in the comments.

What’s this?

I’m musing about message exchange patterns. Specifically, those relevant to reliable asynchronous message exchange between two threads in a concurrent shared memory system. I wrote this in an attempt to abstract the message exchange aspect of this post. I’ve focused here on message exchange events, ignoring the details of the items being exchanged. When you also consider the items being exchanged, higher-level patterns emerge (consider juggling patterns for example).

There are many areas of computing that study or use message exchange. They include: protocol design, real-time systems, distributed computing, SOAP MEP, MPI, bus communication protocols, and process calculi. I am not an expert in these fields but I am interested in what they can teach me about message exchange. There are some links to related resources at the end.

Additional reflections

Acknowledged assumptions

I have assumed that the two parties outlive the message exchange.

I have assumed that the two parties know how to address messages to each other — although often it is enough that the requestor know the address of the respondent, since the requestor can provide a return address to the respondent as part of the request.

Conversations

Request-Reply, Request-Multi-reply and/or Send sequences can be concatenated to form longer back-and-forth conversations. Certain transactions such as two and three-phase commit require multiple request-reply pairs.

Symmetry/asymmetry


Symmetry/asymmetry

The relationship between endpoints may be symmetric: either party may be the initiator in the above exchanges; or asymmetric (as in master-slave, client-server relationships etc.).

WCF has a related concept called Service Contracts. WCF defines three types: Request-Reply, One-Way and Duplex.

Party visibility

Does the receiver know the identity of the sender? Does the message provide this information?

A reply is only possible if the receiver knows the sender’s identity. Sender could provide a return address, or receiver may already know the address. Are sender and receiver knowing participants in a fixed (or dynamic) topology? Does receiver retain or store sender’s identity? When does receiver need to do this? (Subscriptions are one case.)

Message bus architectures distribute events to subscribers without the sender knowing the identity of the receiver. Anonymizing servers provide a route between requestor and respondent without revealing the identity of the requestor to the respondent.

Message semantics

Some writers (eg. Spector 1982) are concerned with efficient and minimal primitives for message transport. SOAP Message Exchange Patterns are similarly concerned with mechanism.

You can also consider the purpose or role of a message. For example, a unidirectional message may be a command to perform an action, or it may be a notification that something has happened. Notifications can be further subdivided into those provided for informational purposes (“last lap of the race”) and those that require action (“evacuate now”).

This post from i8c on Basic Message Exchange Patterns makes an argument for considering more expressive patterns that capture the abstract purpose of a message exchange. It lists 10 communication patterns from SAP, broken into two layers: service communication patterns (query/response, request/confirmation, information, notification) and transaction communication patterns (information, notification, query, response, request, confirmation).

This article on Messaging Patterns in Service-Oriented Architecture also presents “higher level” patterns. For example, when considering unidirectional messages it distinguishes between Command messages, Event messages (notifications) and Document messages (information transfer).

Consider the difference between a command (sent with intent) and an event/notification (interpreted by the receiver).

Also consider command-query separation (and here).

Reactive vs. dataflow

Some message passing systems are concerned with managing the flow of data between processors in a computation (eg. HPC systems based on MPI), whereas others are concerned with reacting to external events or processing transactions (eg. operating system kernels, interactive systems).

Stateful vs. stateless protocols

By focusing on message exchange I have sidestepped the perspective of stateful protocols. Stateful protocols are (usually?) modeled as communicating state machines. Messages drive state transitions and the current state determines which messages are legal. (Searching for “communicating state machines” is a good place to start reading about this.)

Non-software processes

I am interested in applying these patterns to messages passed between communicating computer programs, but the patterns appear in the real world too. Real-world examples include: sending a postcard, an exchange of letters in a legal or bureaucratic process, patterns of business communication, types of business transactions, subscribing to a periodical, marketing email workflows, customer service processes, and so on.

Am I missing something?

Please let me know in the comments if you can think of other patterns, book recommendations, good links or a more abstract (domain-neutral) treatment of this material.

I tried the following searches. Can you suggest other keywords or terms I have overlooked?

communication patterns | two party communication patterns | service communication patterns | transaction communication patterns | message passing theory | message exchange | message exchange theory | packet exchange theory | message exchange protocols | two party message exchange protocols | message communication theory | event driven patterns | event interaction ontology | event exchange patterns

Responses from the Twitterverse

Here are the suggestions for additional message exchange patterns that I’ve received so far (updated January 9, 2013):

Alex McLean @yaxu tweets:

how about scissors-paper-stone voting?

Me: good one. how to draw the picture? +not sure of utility since it is either biased (w/ defaults on ties) or non-wait-free (w/ retries)
on further thought it’s just a request-reply unless you have shared memory, in which case it’s not a message exchange.
reqest/reply: A proposes game along with “sealed” vote, B replies with it’s vote, then opens the seal. B must be honest.

The replies should be simultaneous though / or be received/processed after they’ve all been sent.
There may be similar constraints around time sync protocols.. E.g. data not in the message but in time between send and reply

Me: Indeed time sync protocols are something to consider. As for rock-paper-scissors and timing: www.youtube.com/watch?v=3nxjjztQKtY
Yeah that’s related to Thor’s diplomatic reading between the lines too.

ok how about DNA message that creates a third party?

thor magnusson @thormagnusson tweets:

Also: communication based on not willing to communicate: ignoring messages & breaking protocols. (Eg. Middle east & N-irland)
Also, Austin’s book “How to Do Things with Words” on speech acts, might be an interesting read. (BTW good #openresearch!)

Damian Stewart @damian0815 tweets:

Telephone pictionary. It’s just unreliable Send, but after several transmissions the unreliability becomes the message.

See also

My Interaction Diagrams board on pinterest.

Background reading (for you and me)

Transport level

Programming models

Operating systems

Enterprise, SOA, SOAP, EIP

MPI

Interaction ontology

  • Gerrit Niezen, “Ontologies for interaction: enabling serendipitous interoperability in smart environments” PhD TU/e repository.tue.nl/735539 [pdf]

Communication theory

This is getting a bit lateral, but it might be useful…

Thanks for reading!