Join-pattern


Join-patterns provides a way to write concurrent, parallel and distributed computer programs by message passing. Compared to the use of threads and locks, this is a high level programming model using communication constructs model to abstract the complexity of concurrent environment and to allow scalability. Its focus is on the execution of a chord between messages atomically consumed from a group of channels.
This template is based on join-calculus and uses pattern matching. Concretely, this is done by allowing the join definition of several functions and/or channels by matching concurrent call and messages patterns. It is a type of concurrency pattern because it makes easier and more flexible for these entities to communicate and deal with the multi-threaded programming paradigm.

Description

The join-pattern is like a super pipeline with synchronisation and matching. In fact, this concept is summarise by match and join a set of message available from different message queues, then handles them all simultaneously with one handler. It could be represented by the keywords to specify the first communication that we expected, with the to join/pair other channels and the to run some tasks with the different collected messages. A constructed join pattern typically takes this form:

j.When.And.....And.Do

More precisely, when a message matches with a chain of linked patterns causes its handler to run otherwise the message is queued until one of its patterns is enabled; if there are several matches, an unspecified pattern is selected.
Join-pattern is defined by a set of pi-calculus channels that supports two different operations, sending and receiving, we need two join calculus names to implement it: a channel name for sending, and a function name for receiving a value. The meaning of the join definition is that a call to returns a value that was sent on a channel. Each time functions are concurrently, triggers the return process and synchronizes with other joins.

J ::= //join patterns

In most of cases, the order of synchronous calls is not guaranteed for performance reasons. Finally, during the match the messages available in the queue could be stolen by some intervening thread; indeed, the awakened thread may have to wait again.

History

π-calculus – 1992

The π-calculus belongs to the family of process calculi, allows mathematical formalisms for describing and analyzing properties of concurrent computation by using channel names to be communicated along the channels themselves, and in this way it is able to describe concurrent computations whose network configuration may change during the computation.

Join-Calculus – 1993

Join patterns first appeared in Fournet and Gonthier’s foundational join-calculus, an asynchronous process algebra designed for efficient implementation in a distributed setting. The join-calculus is a process calculus as expressive as the full π-calculus. It was developed to provide a formal basis for the design of distributed programming languages, and therefore intentionally avoids communications constructs found in other process calculi, such as rendezvous communications.

Distributed Join-Calculus – 1996

The Join-Calculus is both a name passing calculus and a core language for concurrent and distributed programming. That's why the Distributed Join-Calculus based on the Join-Calculus with the distributed programming was created on 1996. This work use the mobile agents where agents are not only programs but core images of running processes with their communication capabilities.

JoCaml, Funnel and Join Java – 2000

and Funnel are functional languages supporting declarative join patterns. They present the ideas to direct implement a process calculi in a functional setting.
Another extensions to Java, JoinJava, were independently proposed by von Itzstein and Kearney.

Polyphonic C# – 2002

Cardelli, Benton and Fournet proposed an object-oriented version of join patterns for C# called Polyphonic C#.

Cω – 2003

Cω is adaptation of join-calculus to an object-oriented setting. This variant of Polyphonic C# was included in the public release of Cω in 2004.

Scala Joins – 2007

Scala Joins is a library to use Join-Pattern with Scala in the context of extensible pattern matching in order to integrate joins into an existing actor-based concurrency framework.

JErlang – 2009

is a language which natively supports the concurrent, real time and distributed paradigm. Concurrency between processes was complex, that's why the project build a new language, using based on the Join-calculus.

Join-pattern in classic programming literature

"Join-patterns can be used to easily encode related concurrency idioms like actors and active objects."

using Microsoft.Research.Joins;
class SymmetricBarrier


using Microsoft.Research.Joins;
Join j = Join.Create;
Synchronous.Channel hungry;
Asynchronous.Channel chopstick;
j.Init;
j.Init;
for


using Microsoft.Research.Joins;
class Lock


using Microsoft.Research.Joins;
class Buffer


using Microsoft.Research.Joins;
class ReaderWriterLock


using Microsoft.Research.Joins;
class Semaphore

Fundamental features and concepts

  • Join-calculus : The first apparition of the Join-Pattern comes out with this process calculus.
  • Message passing : Join-pattern works with a message passing system for parallel reason.
  • Channel : Channels are used to synchronize and pass messages between concurrently executing threads. In general, a channel may be involved in more than one join pattern, each pattern defines a different continuation that may run when the channel is invoked.
  • Synchronous : The join-pattern could use a synchronous channel which return a result. The continuation of a synchronous pattern runs in the thread of the synchronous sender.
  • Asynchronous : It could also use an asynchronous channel which return no result but take arguments. The continuation of an asynchronous pattern runs in a newly spawned thread. A join pattern may be purely asynchronous, provided its continuation is a subroutine and its When clause only lists asynchronous channels.
  • Combine synchronous and asynchronous : Merging the declarations of synchronous and asynchronous buffer would yield a module that supports the two communication type of consumers.
  • Scheduler : There is a scheduling between join patterns.
  • Design patterns : The join-pattern is first of all a behavioral and a concurrency pattern.
  • Concurrent programming : It's execute in a concurrent way.
  • Pattern matching : The join-pattern works with matching tasks.
  • Parallel programming : It performs tasks in parallel.
  • Distributed programming : Jobs could be scatter on different agent and environments with this pattern.
  • Software transactional memory : Software transactional memory is one of the possible implementation for the communications between joint.
  • Overlapping : The pattern could allow patterns declared on overlapping sets of channels.

    Application domain

Mobile agent

A mobile agent is an autonomous software agent with a certain social ability and most importantly, mobility. It is composed of computer software and data which can move between different computers automatically while continuing their executions.
The mobile agents can be used to match concurrency and distribution if one uses the Join-calculus. That's why a new concept named "distributed Join-calculus" was created; it's an extension of Join-calculus with locations and primitives to describe the mobility.
This innovation use agents as running processes with their communication capabilities to allow an idea of location, which is a physical site expressing the actual position of the agent. Thanks to the Join-calculus, one location can be moved atomically to another site.
The processes of an agent is specified as a set which define its functionality including asynchronous emission of a message, migration to other location. Consequently, locations are organized in a tree to represent the movement of the agent easier. With this representation, a benefit of this solution is the possibility to create a simple model of failure. Usually a crash of a physical site causes the permanent failure of all its locations. But with the join-calculus a problem with a location can be detected at any other running location, allowing error recovery.
In 2007, an extension of the basic join calculus with methods which make agents proactive has come out. The agents can observe an environment shared between them. With this environment, it is possible to define shared variables with all agents.

Compilation

Join-languages are built on top of the join-calculus taken as a core language. So all the calculus are analysed with asynchronous processes and the join pattern provides a model to synchronize the result.

To do this, it exists two Compilers:
  • Join Compiler: A compiler of a language named "join langage". This language has been created only for the join calculus
  • : A compiler of an extension of Objectif Caml created to use the join calculus.
This two compiler works with the same system, an automaton.

let A | B = P
and A | C = Q
;;

It represents the consumption of message arrive at a completed join model. Each state is a possibly step for the code execution and each transitions is the reception of a message to change between two steps. And so when all messages are grab, the compiler execute the body join code corresponding to the completed model joint.
So in the join-calculus, the basic values are the names like on the example is A,B or C. So the two compiler representing this values with two ways.

Join compiler use a vector with Two slots, the first to the name it-self and the second to a queue of pending messages.

Jocaml use name like a pointer on definitions. This definitions store the others pointer of the others names with a status field and a matching date structure by message.

The fundamental difference is when the guard process is executed, for the first, it was verify if all names are the pending messages ready whereas the second use only one variable and access at the others to know if the model is completed.
Recent research describe the compilation scheme as the combination of two basic steps: dispatching and forwarding. The design and correctness of the dispatcher essentially stems from pattern matching theory, while inserting an internal forwarding step in communications is a natural idea, which intuitively does not change process behavior. They made the observation that ''the worth observing is a direct implementation of extended join-pattern matching at the runtime level would significantly complicate the management of message queues, which would then need to be scanned in search of matching messages before consuming them.''