Towards a primitive higher order calculus of broadcasting systems.
Ethernet-style broadcast is pervasive style of computer communication.In this style,the medium is single nameless channel.Previous work on modelling such systems proposed .rst order process calculus called CBS.In this paper, we propose fundamentally different calculus called HOBS.Compared to CBS, HOBS 1) is higher order rather than first order, 2) supports dynamic subsystem encapsulation rather than static,and does not require an "underlying language" to be Turing-complete. Moving to higher order calculus is key to increasing the expressivity of the primitive calculus and alleviating the need for an underlying language. The move, however, raises the need for significantly more machinery to establish the basic properties of the new calculus.This paper develops the basic theory for HOBS and presents two example programs that illustrate programming in this language. The key technical underpinning is an adaptation of Howe's method to HOBS to prove that bisimulation is congruence. From this result, HOBS is shown to embed the lazy -calculus.
INTRODUCTION
Ethernet-style broadcast is a pervasive style of computer
communication. The bare medium provided by the Ethernet
is a single nameless channel. Typically, more sophisticated
programming idioms such as point-to-point communication
or named channels are built on top of the Ethernet. But
using the Ethernet as is can allow the programmer to make
better use of bandwidth, and exploit broadcast as a powerful
and natural programming primitive. This paper proposes
a primitive higher order calculus of broadcasting systems
(HOBS) that models many of the important features of the
bare Ethernet, and develops some of its basic operational
properties.
1.1 Basic Characteristics of the Ethernet
The basic abstractions of HOBS are inspired by the Ethernet
protocol:
The medium is a single nameless channel.
Any node can broadcast a message, and it is instantaneously
delivered to all the other nodes.
Messages need not specify either transmitter or receiver

The transmitter of a message decides what is transmitted
and when.
Any receiver has to consume whatever is on the net,
at any time.
Only one message can be transmitted at any time.
Collision detection and resolution are provided by the
protocol (for HOBS, the operational semantics), so the
abstract view is that if two nodes are trying to transmit
simultaneously, one is chosen arbitrarily to do so.
All nodes are treated equally; their position on the net
does not matter.
HOBS renes and extends a previously proposed system
called the calculus of broadcasting systems (CBS) [16]. Although
both HOBS and CBS are models of the Ethernet,
the two systems take fundamentally dierent approaches to
subsystem encapsulation. To illustrate these dierences, we
take a closer look at how the Ethernet addresses these issues.
1.2 Modelling Ethernet-Style Encapsulation
Whenever the basic mode of communication is broadcast,
encapsulating subsystems is an absolute necessity. In the
Ethernet, bridges are used to regulate communication between
Ethernet subsystems. A bridge can stop or translate
messages crossing it, but local transmission on either side is
unaected by the bridge. Either side of a bridge can be seen
as a subsystem of the other.
CBS models bridges by pairs of functions that lter and
translate messages going in each direction across the bridge.
While this is an intuitively appealing model suitable for
many applications, it has limitations:
1. CBS relies on a completely separate \underlying lan-
guage". In particular, CBS is a rst order process cal-
culus, meaning that messages are distinct from pro-
cesses. A separate, computationally rich language is
needed to express the function pairs.
2. CBS only provides a static model of Ethernet architec-
tures. But, for example real bridges can change their
routing behaviour. CBS provides neither for such a
change nor for mobile systems that might cross bridges.
3. Any broadcast that has to cross a bridge in CBS does
so instantly. This is unrealistic; real bridges usually
buer messages.
HOBS addresses these limitations by:
Supporting rst-class, transmittable processes, and
Providing novel encapsulation primitives.
Combined, these features of HOBS yield a Turing-complete
language su-cient for expressing translators (limitation 1
above), and allow us to model dynamic architectures (lim-
itation 2). The new encapsulation primitives allow us to
model the buering of messages that cannot be consumed
immediately (limitation 3).
1.3 Problem
Working with a higher order calculus comes at a cost to
developing the theory of HOBS. In particular, whereas the
denition of behavioural equivalence in a rst order language
can require an exact match between the transmitted mes-
sages, such a denition is too discriminating when messages
involve processes (non-rst order values). Thus, behavioural
equivalence must only require the transmission of equivalent
messages.
Unfortunately, this syntactically small change to the notion
of equivalence introduces signicant complexity to the
proofs of the basic properties of the calculus. In particu-
lar, the standard technique for proving that bisimulation
is a congruence [11] does not go through. A key di-culty
seems to be that the standard technique cannot be used directly
to show that the substitution of equivalent processes
for variables preserves equivalence (This problem is detailed
in Section 4.1.)
1.4 Contributions and Organisation
The main contributions of this paper are the design of
HOBS and formal verication of its properties.
After presenting the syntax and semantics of HOBS (Sec-
tion 2), we give the formal denition of applicative equivalence
for HOBS (Section 3).
A key step in the technical development is the use of
Howe's method [10] to establish that applicative equivalence
for HOBS is a congruence (Section 4). As is typical in the
treatment of concurrent calculi, we also introduce a notion
of weak equivalence. Essentially the same development is
used to develop this notion of equivalence (Section 5).
As an application of the these results, in section 6 we use
them to show that HOBS embeds the lazy -calculus [1],
which in turn allows us to dene various basic datatypes.
This encoding relies on the fact that HOBS is higher order.
Possible encodings of CBS and the -calculus [12] are discussed
brie
y (More details can be found in the extended
version of the paper [14]). Two examples, one dealing with
associative broadcast [2] and the other dealing with database
consistency [2] are presented in Section 7.
These results lay the groundwork for further applied and
theoretical investigation of HOBS. Future work includes developing
implementations that compile into Ethernet or Internet
protocols, and comparing the expressive power of different
primitive calculi of concurrency. We conclude the paper
by discussing the related calculi and future works (Sec-
tion 8).
Remarks
No knowledge is assumed of CBS or any other process
calculus. The formal development in this paper is self-contained

For readers familiar with CCS [11], CHOCS [18] and CBS:
Roughly, HOBS is to CBS what CHOCS is to CCS.
The extended version of the paper (available online [14])
gives details of all denitions, proofs and some additional
results.
2. SYNTAX AND SEMANTICS
HOBS has eleven process constructs, formally dened in
the next subsection. Their informal meaning is as follows:
- 0 is a process that says nothing and ignores everything
it hears.
- x is a variable name. Scoping of variables and substitution
is essentially as in the -calculus.
receives any message q and becomes p1 [q=x].
- p1 !p2 can say p1 and become p2 . It ignores everything
it hears.
becomes p3 except if it hears
something, say q, whereupon it becomes p1 [q=x].
- p1 jp2 is the parallel composition of p1 and p2 . They
can interact with each other and with the environment,
p1 jp2 interacts as if it were one process.
countable set of names
Ground-terms
Guarded Choice
Composition
Buers f 2 F ::= p / p Feed Buer
Messages
Actions a 2 A ::= m! m?
Contexts
Syntax indexed by a set of free-variables L

Figure

1: Syntax
is the in-lter construct, and behaves as p1
except that all incoming messages are ltered through
p2 . This in-lter is asymmetric; p2 hears the environment
and p1 speaks to it. A nameless private channel
connects p2 to p1 . This construct represents an in-
lter that is waiting for an incoming message. Process
p1 can progress independently.
represents in-lter in a busy state. Process
p1 is suspended while p2 processes an input message.
Later p2 sends the processed message to p1 and p1 is
resumed.
is the out-lter construct, and behaves as
p2 except all outgoing messages from p2 are ltered
through p1 . This out-lter is also asymmetric; p2 hears
the environment and p1 speaks to it. A nameless private
channel connects p2 to p1 . This ltering construct
represents out-lter in passive state waiting for p2 to
produce an output message. Process p2 can progress
independently.
represents out-lter in busy state. Process
p3 is suspended while p1 processes an output message.
After processing, p1 sends the message to the envi-
ronment, and p3 is resumed. In case process p1 fails
to process the message before the environment sends
some other message, out-lter will \roll-back" to its
previous state represented by process p2 .
is the feed construct, and consists of p1 being
\fed" p2 for later consumption as an incoming mes-
sage. It cannot speak to the environment until p1 has
consumed p2 .
Thus, HOBS is built around the same syntax and semantics
as CBS [16], but without a need for an underlying language.
Instead, the required expressivity is achieved by adding the
ability to communicate processes (higher-orderness), as well
as the feed and ltering constructs.
2.1 Formal Syntax and Semantics of HOBS
The syntax of HOBS is presented in Figure 1. Terms are
treated as equivalence classes of -convertible terms. The
set PL is a set of process terms with free variables in the set
L, for example P? is the set of all closed terms.
Remark 1 (Notation). The names ranging over each
syntactic category are given in Figure 1. Thus process terms
are always p, q or r. Natural number subscripts indicate
subterms. So p1 is a subterm of p. Primes mark the result
of a transition (or transitions), as in p q?

Figure

2 denes the semantics in terms of a transition
relation   !   P?  A?  P? . Free-variables, substitution
and context lling are dened as usual (see [14] for
details). The semantics is given by labeled transitions, the
labels being of the form p! or p? where p is a process. The
former are broadcast, speech, or transmission, and the latter
are hearing or reception. Transmission can consistently be
interpreted as an autonomous action, and reception as controlled
by the environment. This is because processes are
always ready to hear anything, transmission absorbs reception
in parallel composition, and encapsulation (ltering)
Receive Transmit
Silence
Nil
Input x?p1 q?
Output p1 !p2 q?
Choice
Compose
Out-Filter
Internal

Figure

2: Semantics
can stop reception but only hide transmission. For more
discussion, see [16].
The lter constructs required careful design. One diculty
is that lters should be able to hide messages. Tech-
nically, this means that lters should be able to produce
silent messages as a result. But \silence" message  is not
a process construct. Therefore, each lter produces a \mes-
senger" process as a result, and this messenger process then
sends the actual result of ltration and is then discarded.
This way the messenger process can produce any message
(that is any process or silent  ).
The transition relation
fails to
be a function (in the rst two arguments) because the composition
rule allows arbitrary exchange of messages between
sub-processes. The choice construct does not introduce non-determinism
by itself, since any broadcast collision can be
resolved by allowing the left sub-process of a parallel composition
to broadcast.
However, the calculus is deterministic on input, and is
input enabled. That is,
This is easily shown by induction on the derivation p m?
For further discussion of these and other design decisions
we refer the reader to the extended version of the paper [14].
3. APPLICATIVE BISIMULATION
There are no surprises in the notions of simulation and
bisimulation for HOBS, and the development uses the same
techniques as for channel-based calculi [11].
Because the transition relation carries processes in labels,
and because notions of higher order simulation and bisimulation
have to account for the structure of these processes,
we use the following notion of message extension for convenience

be a relation on process terms. Its message extension R
M M is dened by the following rules
TauExt
MsgExt
Thomsen's notion of applicative higher order simulation
[18] is suitable for strong simulation in HOBS, because we
have to take the non-grounded (higher order) nature of the
messages into account.
(Applicative Simulation). A relation
R  P?  P? on closed process terms is a (strong, higher
applicative simulation, written S(R), when
1:
2:
We use a standard notion of bisimulation:
Definition 3 (Applicative Bisimulation). A relation
R  P? P? on closed process terms is an applicative
bisimulation, written B(R), when both S(R) and S(R 1 )
hold. That is,
Using standard techniques, we can show that the identity
relation on closed processes is a simulation and a bisimula-
tion. The property of being a simulation, a bisimulation re-
spectively, is preserved by relational composition and union.
Also, the bisimulation property is preserved by converse.
Two closed processes p and q are equivalent, written p
q, if there exist a bisimulation relation R such that (p; q) 2
R. In other words, applicative equivalence is a union of all
bisimulation relations:
Definition 4 (Applicative Equivalence). The applicative
equivalence is a relation  P?  P? dened as a
union of all bisimulation relations. That is,
RP?P?
Proposition 1.
1. B(), that is,  is a bisimulation.
2.  is an equivalence, that is,  is re
exive, symmetric
and transitive.
The calculus enjoys the following basic properties:
Proposition 2. Let
Input
1. x?0  0
Parallel Composition
1. pj0  p
2. p1 jp2  p2 jp1
3. p1 j(p2 jp3)  (p1 jp2)jp3
Filters
1.
2. (p1 - p2
3. x?p -0  0
4. hx?p1
Choice
1.
2. hx?p1+p2 !p3 ijx?p4  hx?(p1 jp4 )+p2 !(p3 jp4 [p2 =x])i
4. EQUIVALENCE AS A CONGRUENCE
In this section we use Howe's method [10] to show that
the applicative equivalence relation  is a congruence. To
motivate the need for Howe's proof method, we start by
showing the di-culties with the standard proof technique
[11]. Then, we present an adaptation of Howe's basic development
for HOBS. We conclude the section by applying
this adaptation to applicative equivalence.
An equivalence is a congruence when two equivalent terms
are not distinguishable in any context:
be an
equivalence relation on process terms. R is a congruence
when
Comp Nil p1 R q1 p2 R q2
R q1 !q2
Comp Out p1 R q1 p2 R q2
Comp InFilter
Rx
Comp Var p1 R q1 p2 R q2
R q1 jq2
Comp Comp p1 R q1 p2 R q2
R q1  q2
Comp InFilterB
Comp In p1 R q1 p2 R q2
R q1 / q2
Comp Feed p1 R q1 p2 R q2
Comp OutFilter
Comp Choice p1 R q1 p2 R q2 p3 R q3
Comp OutFilterI

Figure

3: Compatible Renement
4.1 Difficulty with the Standard Proof Method
The notion of compatible renement b
R allows us to concisely
express case analysis on the outermost syntactic constructor

Definition 6 (Compatible Refinement). Let R
P P be a relation on process terms. Its compatible rene-
ment b
R is dened by the rules in Figure 3.
The standard congruence proof method is to show, by
induction on the syntax, that equivalence  contains its
compatible renement b
. The standard method for proving
congruence centers around proving the following lemma:
Lemma 1. Let R  P  P be an equivalence relation on
process terms. Then R is a congruence i b
R  R.
The standard proof (to show b
proceeds by case
analysis. Several cases are simple (nil 0, variable and output
x?). The case of feed  /  is slightly more complicated.
All the other cases are problematic (especially composition
j), since they require substitutivity of equivalence  where
substitutivity is dened (in a usual way) as:
Definition 7 (Substitutivity). Let R  P  P be a
relation on process terms. R is called substitutive when the
following rule holds
p1 [p2=x] R q1 [q2 =x]
Rel Subst
In HOBS, the standard inductive proof of substitutivity
of equivalence  requires equivalence to be a congruence.
And, we are stuck. Attempt to prove substitutivity and
simultaneously does not work either, since a term's
size can increase and this makes use of induction on syntax
impossible. Similar problems seem to be common for higher
order calculi (see for example [18, 7, 1]).
4.2 Howe's Basic Development
Howe [10] proposed a general method for proving that
certain equivalences based on bisimulation are congruences.
Following similar adaptations of Howe's method [9, 7] we
present the adaptation to HOBS along with the necessary
technical lemmas. We use the standard denition of the
restriction R? of a relation R to closed processes (cf. [14]).
Extension of a relation to open terms is also the standard
one:
Definition 8 (Open Extension). Let R  P  P be
a relation on process terms. Its open extension is dened by
the following rule
8:
The key part of Howe's method is the denition of the
candidate relation R  :
Definition 9 (Candidate Relation). Let R  P
P be a relation on process terms. Then a candidate relation
is dened as the least relation that satises the rule
Cand
The denition of the candidate relation R  facilitates simultaneous
inductive proof on syntax and on reductions.
Note that the denition of the compatible renement b
R
involves only case analysis over syntax. And, inlining the
compatible renement b
R in the denition of the candidate
relation would reveal inductive use of the candidate relation
R  .
The relevant properties of a candidate relation R  are
summed up below:
Lemma 2. Let R  P?  P? be a preorder (re
exive,
transitive relation) on closed process terms. Then the following
rules are valid
Cand Ref p R - q
Cand Sim
R  q
Cand Cong p R  r r R - q
Cand Right
p1 [p2=x] R  q1 [q2 =x]
Cand Subst
Corollary 1. We have R   R
- as an immediate
consequence of rule Cand Subst and rule Cand Ref.
(eq.
c
r
c
r
where l  n

Figure

4: Transmit Lemma
Lemma 3. Let R  P  P be an equivalence relation.
Then R  is symmetric.
The next lemma says that if two candidate-related processes
are closed terms then there is a derivation
which involves only closed terms in the last derivation step.
Lemma 4 (Closed Middle).
R  r R - q
4.3 Congruence of the Equivalence Relation
Now our goal of is twofold: rst, to show that the candidate
relation   coincides with the open extension  - , that
is  and second, to use this fact to complete the
congruence proof.
First, we will x the underlying relation R to be . We
already know  -   from Lemma 2 (rule Cand Sim). To
show the converse we begin by proving that the closed restriction
of the candidate relation
? is a simulation. This
requires showing that the two simulation conditions of Definition
hold.
We split the proof into two lemmas: Lemma 5 (Receive)
and Lemma 6 (Transmit), which prove the respective condi-
tions. Similarly to the standard proof, the parallel composition
case is the most di-cult and actually requires a stronger
receive condition to hold. The rst lemma (Receive) below
proves a restriction of the rst condition. Then the second
lemma (Transmit) below proves the second condition and
makes use of the Receive Lemma.
Lemma 5 (Receive). Let p; q 2 P? be two closed processes
and p  q. Then 8m; n;
Proof. Relatively straightforward proof by induction on
the height of inference of transition . The only interesting
case is the case of rule x?p1 q?
p1 [q=x], which makes
use of the substitutivity of the candidate relation   .
Lemma 6 (Transmit). Let p; q 2 P? be two closed processes
and p   q. Then 8m;
n) (3)
Proof. First note that from Lemma 4 (Closed Middle)
we have that
Also, from the denition of equivalence  and the fact that
r and q are closed processes we know that
It remains only to prove that 8m;
Joining statements (5) and (4), and using Lemma 2 (rule
Cand Right) to infer p 0   q 0 and m   n gives us the
result. Figure 4 shows the idea pictorially (normal lines,
respectively dotted lines, are universally, respectively existentially
quantied).
To prove the statement (5) we proceed by induction on the
height of inference of transition We only describe
the most interesting case { parallel composition.
Compose There are two parallel composition rules. Since
the rules are symmetric we only show the proof for one
of them. We know that p  p1 jp2 , and we have four
related sub-processes: p1   r1 and p2   r2 . Now suppose
that m is a process, and that p made the following
0Since the candidate relation   contains its compatible
renement, it is enough to show that each sub-process
of r can mimic the corresponding sub-process
of p. For r1 , using the induction hypothesis we get
that r1 l! ! r 0and p 0  r 0, m   l. For r2 , if we
would use only the simulation condition, we would get
0, and this would not allow us to show that r
has a corresponding transition, since the inference of
a transition requires both labels to be the same. At
this point, we can use the stronger receive condition
of Lemma 5 and we get precisely what we need, that
is:
The case when m is  is
similar, but simpler since it does not require the use
of Lemma 5 (Receive).
With the two lemmas above we have established that the
restriction of the candidate relation
? is a simulation.
Also, using Lemma 3 we get that   ?
is symmetric, which
means that it is a bisimulation. To conclude this section, we
are now ready to state and prove the main proposition.
Proposition 3.  - is a congruence.
Proof. First we show that
(rule Cand Sim) we know  -   . From the two lemmas
above and Lemma 3 we know that   ?
is a bisimulation.
This implies
. Since open extension is
monotone we have   ?
- . By Corollary 1 we get
- , and so    - .
As  - is an equivalence, and it is equal to the candidate
relation, it contains its compatible renement ( c
Lemma 2 rule Cand Cong). By Lemma 1 this implies that
- is a congruence.
5. WEAK BISIMULATION
For many purposes, strong applicative equivalence is too
ne as it is sensitive to the number of silent transitions performed
by process terms. Silent transitions represent local
computation, and in many cases it is desirable to analyse
only the communication behaviour of process terms, ignoring
intermediate local computations. For example, the
strong applicative equivalence distinguishes the following
two terms that have the same communication behaviour:
Equipped with the weak transition relation
tion 10) we dene the weak simulation and weak bisimulation
in the standard way[11]. Weak equivalence  is also
dened in the standard way as a union of all weak bisimulation
relations. Just as for the strong equivalence, we prove
that  is a weak bisimulation and that it is an equivalence
(Proposition 4). Moreover, the technique used in proving
that strong equivalence is a congruence works also for the
equivalence (Proposition 5).
=) be the
re
exive transitive closure of  !
!. Then the weak transition
is dened as
a
=) if a   !
Proposition 4.
1.  is a weak bisimulation
2.  is an equivalence.
Proposition 5.  is a congruence.
Proof. The proof follows that of Proposition 3. An interesting
dierence is when the induction hypothesis is used
(for example in the case of parallel composition). When
using the induction hypothesis we get that the appropriate
subterms can perform weak transition a
=). Then we have to
interleave the  ! transitions before possibly performing the
action a. This interleaving is possible since every process
can receive  without any change to the process itself (see
rule Silence in Figure 2).
Expressions
Embedding

Figure

5: Syntax, semantics and embedding of
lazy -calculus.
6. EMBEDDINGS AND ENCODINGS
While a driving criterion in the design of HOBS is simplicity
and resemblance to the Ethernet, a long term technical
goal is to use this simple and uniform calculus to interpret
other more sophisticated proposals for broadcasting
calculi, such as the b-calculus [5]. Having HOBS interpretations
of hand-shake calculi such as -calculus, -calculus
with groups [3], and CCS could also provide a means for
studying the expressive power of these calculi.
In this section, we present the embedding of the lazy -
calculus and its consequences, and brie
y discuss possible
encodings of CBS and the -calculus.
6.1 Embedding of the -calculus
The syntax and semantics of the lazy -calculus, along
with a direct translation into HOBS, are presented in Figure
5. The function  !   E  E is the small-step
semantics for the language.
Using weak equivalence  we can prove that the analog
of -equivalence in HOBS holds. A simple proof of this
proposition using weak bisimulation up to  technique can
be found in the extended version of the paper [14].
Proposition 6.
Proposition 7. (Soundness) Let ' be the standard
-calculus notion of observation equivalence. Then
Being able to embed the -calculus justies not having
explicit construct in HOBS for either recursion or datatypes.
Just as in the -calculus there is a recursive Y combinator,
HOBS can express recursion by the derived construct rec
dened on the left below. This recursive construct has the
expected behaviour as stated on the right below.
rec x.p  Wx(p) / Wx(p) rec x.p  p[rec x.p=x]
From the point of view of the -calculus, it is signicant
that this embedding is possible. In particular, broadcasting
can be viewed as an impurity, or more technically as a computational
eect [13]. Yet the presence of this eect does not
invalidate the -rule. We view this as a positive indicator
about the design of HOBS.
6.2 Encodings of Concurrent Calculi
Having CBS as a precursor in the development of HOBS,
it is natural to ask whether HOBS can interpret CBS. First,
CBS assumes an underlying language with data types, which
HOBS provides in the form of an embedded lazy -calculus,
using the standard Church data encodings. Second, the CBS
translator is the only construct that is not present in HOBS.
To interpret it, we use a special parametrised queue con-
struct. The queue construct together with the parameter
(the translating function) is used as a one-way translator.
Linking two of these to a process (via lter constructs) gives
a CBS-style translator with decoupled translation.
Using Church numerals to encode channel names we can
easily interpret the -calculus without the new operator.
Devising a sound encoding of the full -calculus is more
challenging, since there are several technical di-culties, for
example explicit -conversion, that have to be solved.
For further discussion and proposed solutions see the extended
version of the paper [14]. The soundness proof for
these encodings is ongoing work.
7. EXAMPLES
HOBS is equiped with relatively high-level abstractions
for broadcasting communication. Because HOBS includes
the lazy -calculus, we can extend it to a full functional
language. This gives us tool for experimenting with broadcasting
algorithms. As the theory develops, we hope that
HOBS will also be a tool for formal reasoning about the
algorithms.
In this section we present an implementation of a coordination
formalism called associative broadcast [2], together
with an implementation of a database consistency algorithm
expressed in this formalism. Compared to previous implementations
of this algorithm (see for example [6]), the HOBS
implementation is generic, retains the full expressive power
of associative broadcast, and allows straightforward representation
of associative broadcast algorithms.
Our HOBS interpreter is implemented in OCaml. In addi-
tion, we also use an OCaml-like syntax for HOBS functional
terms and datatypes, and use just juxtaposition instead of
the feed construct symbol. For the purposes of this paper,
the reader can treat the typing information as simply comments

7.1 Associative Broadcast
Bayerdorer [2] describes a coordination formalism called
associative broadcast. This formalism uses broadcasting as
a communication primitive. In this formalism, each object
that participates in the communication has a prole. A
prole can be seen as a set of attribute-value pairs. A special
subset of these pairs contains values that are functions which
modify the prole. This subset is divided into functions that
are used in broadcasting, and those that are used locally.
Since associative broadcast is a coordination formalism, all
objects are locally connected to some external system, and
they can invoke operations on that system. Conversely, the
external system can invoke the local functions of the object.
Communication between objects proceeds as follows: each
broadcast message contains a specication of the set of re-
cipients, and an operation that recipients should execute.
The specication is a rst-order formula which examines a
prole. An operation is a call to one of the functions that
modify the prole. When a message is broadcasted by an
object, it is received by all objects including the sender.
Each object then evaluates the formula on its own prole
to determine whether it should execute the operation. The
operation is executed only if the prole satised the formula.
The generic part of associative broadcast is represented
by so called RTS (run time system), which takes care of
the communication protocol. The following are the basic
denitions needed for an implementation of RTS in HOBS:
type 'a operation = 'a -> ('a -> 'a) -> 'a;;
Message of 'a selector * 'a operation
| Internal of 'a operation;;
type 'a tag = In of 'a
| Out of 'a
let rec x?match x with
Out(p) -> (p!0)!p1
| In(p) -> (0 0)!p1
and
and x?match x with
Out(p) -> (0 0)!p3
| In(p) -> (p!0)!p3
and
Out(p) -> (In(p))!m
| In(p) -> m;;
let rec obj profile =
x?match x with
Message(sel,op) -> if (sel profile) then
op profile obj
else
obj profile
| Internal(op) -> op profile obj
Recipient specication formulas have type 'a selector, operations
have type 'a operation which should be viewed as
a function which takes a prole (type 'a) and a continuation
and returns a prole. Messages that an object can receive
have type 'a message. The key component of the RTS is
the representation of an object. In HOBS an object can be
implemented as:
where process obj executes the main object loop that runs
the protocol. The ltering processes p1, p2, p3, p4 and
the \mirroring" process m take care of the broadcast message
loopback, that is routing each message to all the other
objects and the object itself. Loopback routing uses simple
intuitive tagging of messages.
Having implemented the associative broadcast RTS, we
can implement any associative broadcast algorithms by creating
a prole required by the algorithm. To run the algorithm
we only need to create a parallel composition with the
appropriate number of objects with their proles.
7.2 Database Consistency
In a distributed database there may be several copies of
the same data entity, and ensuring the consistency of these
various copies becomes a concern. Inconsistency can arise if
a transaction occurs while a connection between two nodes
is broken. If we know that concurrent modications are rare
or that downtime is short, we can employ the following optimistic
protocol [2]: When a failure occurs, network nodes
are broken into partitions. While the network is down all
nodes log their transactions. After discovering a network re-connection
we construct a global precedence graph from the
log of all transactions. If this graph does not contain cycles,
then the database is consistent. A transaction t1 precedes
transaction
both t1 and t2 happened in one partition, and t2 read
data previously written by t1
both t1 and t2 happened in one partition, and t1 read
data later written by t2
t1 and t2 happened on dierent partitions, and t1 read
data written by t2
The algorithm represents each item (table, row, etc., depending
on the locking scheme) by an RTS coordination
object. This object will keep the log of all local transac-
tions, and so each object will hold a part of the precedence
graph. To connect these parts into the full graph each object
will broadcast a token to other objects along the precedence
graph edges. When an object receives a token it will
propagate the token along the precedence edges the object
already maintains. If a token returns to its originating object
then we have found an inconsistency. In parallel with
token propagation each object also sends a merge message
to actually merge (or update) values of the item in dierent
partitions. And, if an object that modied its item receives
merge message, it also declares inconsistency.
In what follows we present the key denitions in our im-
plementation. The code for the full implementation can be
found in Figure 6 on the last page. The prole used by each
object is dened as follows:
{oid:int;
mutable item_name: string;
mutable item_value: int;
mutable reads: transaction list;
mutable written: bool;
mutable partition: int;
mutable merged: bool;
mutable mcount: int;
mutable tw: transaction;
propagate: int -> int -> profile operation;
merge: int -> bool -> profile operation;
upon_partitioning: unit -> profile operation;
upon_commiting_transaction:
int -> profile operation;
upon_detecting_reconnection:
profile operation};;
Each object keeps a unique identier oid, the name of the
item it monitors, the value of that item, a set of transactions
reads, a
ag to signal if the item was written, and a partition
number. It also keeps a set of local attributes: merged
ag to
check whether the item values are already merged between
1 When an item is written it is also considered to be read.
partitions, number of merge messages received mcount, and
the last logged write transaction tw.
Each object has two broadcasting operations: propagate
to propagate a token along the precedence edges it contains,
and merge to possibly update the item to a new value. Each
object has three local operations: upon partitioning to
record the local partition number, upon commiting trans-action
to record committed transactions, and upon detecting
reconnection that starts the graph construction.
The functions that the external system is assumed to
provide are: local partition id to get a partition iden-
log to log transactions; modifies to check whether
a transaction modies an item; precedes to check (using
the local log) whether a transaction precedes other trans-
action; declare inconsistency to declare database incon-
delay transactions to pause the running trans-
actions; count objects to get the number of all objects;
count local objects to get the number of objects in a par-
tition; and write locked to check whether an item is locked
for writing.
8. RELATED WORK
In this section we review works related to our basic design
choices and the central proof technique used in the paper.
8.1 Alternative Approaches to Modelling Dynamic
Connectivity
One approach to modelling dynamic broadcast architectures
is to support special messages that can change bridge
behaviour. This corresponds to the transmission of channel
names in the -calculus [12]. Another approach is to allow
processes be transmitted, so that copies can be run elsewhere
in the system. This makes the calculus higher order,
like CHOCS [18]. This is the approach taken in this paper.
A preliminary variant of HOBS sketched in [15] retains the
underlying language of messages and functions. The resulting
calculus seems to be unnecessarily complex, and having
the underlying language seems redundant.
In HOBS, processes are the only entities, and they are
used to characterise bridges. Since processes can be broad-
casted, it will be interesting to see if HOBS can model some
features of the -calculus. Because arrival at a bridge and
delivery across it happen in sequence, HOBS avoids CBS's
insistence that these actions be simultaneous. This comes
at the cost of having less powerful synchronisation between
subsystems.
8.2 Related Calculi
The b-calculus [5] can be seen as a version of the -
calculus with broadcast communication instead of point-to-
point. In particular, the b-calculus borrows the whole channel
name machinery of the -calculus, including the operator
for creation of new names. Thus the b-calculus does not
model the Ethernet directly, and is not obviously a mobile
version of CBS. Reusing ideas from the sketched -calculus
encoding can yield a simple b-calculus encoding. Using l-
terss to model scopes of new names seems promising. More-
over, such an encoding might be compositional. We expect
that with an appropriate type system we can achieve a fully
abstract encoding of the b-calculus. The type system would
be a mixture of Hindley/Milner and polymorphic -calculus
systems.
The Ambient calculus [4] is a calculus of mobile processes
with computation based on a notion of movement. It is
equipped with intra-ambient asynchronous communication
similar to the asynchronous -calculus. Since the choice of
communication mechanism is independent from the mobility
primitives, it may be interesting to study a broadcasting
version of Ambient calculus. Also, broadcasting Ambient
calculus might have simple encoding in HOBS.
Both HOBS and the join calculus [8] can be viewed as extensions
of the -calculus. HOBS adds parallel composition
and broadcast communication on top of the bare -calculus.
The join calculus adds parallel composition and a parallel
pattern on top of the -calculus with explicit let. The relationship
between these two calculi remains to be studied.
The feed operator / is foreshadowed in implementations
of CBS, see [16], that achieve apparent synchrony while allowing
subsystems to fall behind.
8.3 Other Congruence Proofs
Ferreira, Hennessy and Jerey [7] use Howe's proof to
show that weak bisimulation is a congruence for CML. They
use late bisimulation. They leave open the question whether
Howe's method can be applied to early bisimulation; this
paper does not directly answer their question since late and
early semantics and bisimulations coincide for HOBS. A
proof for late semantics for HOBS is more elegant than the
one here, and can be found in the extended version of the
paper [14].
Thomsen proves congruence for CHOCS [18] by adapting
the standard proof, but with non-well founded induction.
That proof is in eect a similar proof to Howe's technique,
but tailored specically to CHOCS.
abandons higher order bisimulation for reasons
specic to point-to-point communication with private
channels, and uses context bisimulation where he adapts the
standard proof. His proof is of similar di-culty to the proof
presented here, especially in that the case of process appli-
cation, involving substitution, is di-cult.
9.

ACKNOWLEDGEMENTS

We would like to thank Dave Sands for bringing Howe's
method to our attention, Jorgen Gustavsson, Martin Wei-
chert and Gordon Pace for many discussions, and anonymous
referees for constructive comments.
10.



--R

The lazy lambda calculus.
Bryan Bayerdor
Secrecy and group creation.
Mobile ambients.
Expressivness of point-to-point versus broadcast communications
A broadcast-based calculus for communicating systems
Alan Je

Bisimilarity as a theory of functional programming: mini-course
Proving congruence of bisimulation in functional programming languages.
Communication and Concurrency.
Communicating and Mobile Systems: the
Notions of computation and monads.
Karol Ostrovsk
Status report on ongoing work: Higher order broadcasting systems and reasoning about broadcasts.
A calculus of broadcasting systems.
Expressing Mobility in Process Algebras: First-Order and Higher-Order Paradigms
Plain CHOCS: A second generation calculus for higher order processes.
The Polymorphic Pi-Calculus: Theory and Implementation
--TR
Communication and concurrency
Notions of computation and monads
The lazy lambda calculus
A calculus of broadcasting systems
Proving congruence of bisimulation in functional programming languages
The reflexive CHAM and the join-calculus
Communicating and mobile systems
Mobile ambients
Secrecy and Group Creation
Expressiveness of Point-to-Point versus Broadcast Communications

--CTR
Massimo Merro, An Observational Theory for Mobile Ad Hoc Networks, Electronic Notes in Theoretical Computer Science (ENTCS), 173, p.275-293, April, 2007
Patrick Eugster, Type-based publish/subscribe: Concepts and experiences, ACM Transactions on Programming Languages and Systems (TOPLAS), v.29 n.1, p.6-es, January 2007
semantics;ethernet;concurrency;broadcasting;calculi;programming languages