\documentstyle[a4,11pt]{article}

\title{A Beginner's Guide to Mailboxes}
\author{Damian Chu \\
Dept. of Computing \\
Imperial College of Science, Technology and Medicine \\
180 Queen's Gate \\
London  SW7 2BZ \\
email: dac@doc.ic.ac.uk}
\date{August, 1992}

\newcommand{\imagine}{{\tt IMAGINE}\ }
\newcommand{\lo}{{L\&O}}
\newcommand{\lando}{{Logic \& Objects}}
\newcommand{\prolog}{{Prolog}}
\newcommand{\icp}{{IC-Prolog ][}}
\newcommand{\readp}{{\tt read}}
\newcommand{\readwrite}{{\tt read\_write}}
\newcommand{\none}{{\tt none}}
\newcommand{\writep}{{\tt write}}
\newcommand{\uphat}{{\tt \^\/}}



\begin{document}

\maketitle



\begin{abstract}
This document is not completed yet.
\end{abstract}

% \newpage

\section{Introduction}
The recent trend in computing is towards Distributed Systems.  With
the widespread use of personal computers and high-powered
workstations, the days of the monolithic mainframes are over.  Data
and processing power are now typically spread over a set of machines
connected by a Local Area Network.  Although many tasks may be
carried out on a single machine, the proliferation of processors
means that there is a greater opportunity and need for programs on
separate machines to cooperate.  Before we can cooperate, we first
must be able to communicate.  This document is about proposing a
model for communication.

\subsection{Client-Server Model}
A well-known model for communication is the Client-Server model.  In
this scenario, a group of machines require shared access to a global
resource.  This resource may be hardware, such as a printer or
typesetter, or it may be data, for example a database.  One of the
machines (or more accurately, a process on this machine) is given
overall control of this resource and is designated as the Server
because it provides a service.  Users of this service are called
Client processes.  Although we usually think of Clients as residing
on other machines, there is no reason that a Server and Client cannot
both be on the same machine.

Typically the Server process is started first and after some
initialisation, goes to sleep waiting for Clients.  When a Client
requires the service, it sends a message to the Server.  The
Server wakes up to handle the request and there may be further
two-way communication between the two processes.  When the session
is over, the Server process goes back to waiting for the next Client.

\subsection{TCP}
This Client-Server model is the basis of TCP (Transmission Control
Protocol).  TCP is the most popular communciation protocol and it is
implemented on most machines.  TCP works well for applications which
naturally map onto the Client-Server model.  There is an asymmetry
between the Clients and the Server.  However, in the simple case of
two processes having a conversation, it seems to be an unnecessary
overhead and confusing complication to force one process to be the
Server and somehow provide a service to the Client, when it is much
more natural to think of them as two symmetrical processes.

In TCP, the instrument of communication is a socket.  A socket is one
end of a communication channel.  To set up a channel between a Server
and a Client, two sockets are created (one by the Server and the
other by the Client) and are then connected to each other.  This is
analogous to a telephone conversation where two telephones are
required to set up a connection.  As with telephones, TCP
communication is strictly one-to-one.  There are no facilities to set
up one-to-many or many-to-one conversations.

In TCP, every communication channel set up between a Server and a
Client is a separate network connection.  The system overheads of
creating sockets and setting up connections over the network become
significant if the conversations are short and there are many such
conversations.  For example, if ten processes on one machine are
talking to ten processes on another machine, there will be ten
network connections between the two machines.

These disadvantages can be overcome by providing a higher level
abstraction that is more powerful and simpler to use.  Mailboxes
provide such an abstraction.

\section{The Mailbox Model}
In the mailbox model, the instrument of communication is a mailbox.
A mailbox is simply a repository for messages.
Mailboxes may be created freely by any process.
Messages can be sent
to and removed from a mailbox.  Instead of having
to create two sockets to communicate, we now need to create only
one mailbox.  For two processes to communicate, the sender
places a message in the mailbox, and the receiver removes it from
the same mailbox.  A mailbox can store multiple messages.  Messages
are kept in arrival order so that it naturally simulates stream
communication.

\subsection{Message Peeking}
When a message is read from a mailbox, there is an option to
not remove it.  The message can remain in the mailbox.  This
is so that a receiving process can determine whether it should
be left for another process to handle.  This can occur because
multiple processes may be reading from the same mailbox.  When
a message is being checked in this way, further reads from this
mailbox must wait until a decision has been made regarding the
message.  The options are to commit the read and remove the
message, or to discard the read and leave it in the mailbox.

\subsection{Two-way Communication}
Messages in a mailbox may be read by any process, including the
process that sent it.  This makes it difficult (though not
impossible) to implement two-way communication using only one
mailbox.  Mailboxes are best used when only one receiver reads
messages from it.  Since there is very little cost associated
with creating new mailboxes, two-way communication should be
carried out using two mailboxes.

\subsection{Multi-way Communication}
A link may be established between two mailboxes.  When a message
is sent to the first mailbox, the message is automatically
forwarded to the second mailbox.  Note that the link is
uni-directional only - messages sent directly to the second mailbox
will not by forwarded to the first.  The second mailbox remains
an ordinary mailbox while the first becomes a `linked' mailbox.
Linked mailboxes do not store any messages, only addresses of
links.  A mailbox may be linked to many mailboxes.  In this
case, messages sent to the linked mailbox will cause a copy
of the message to be forwarded to each and every link.  This
is how we can configure one-to-many communication.  Note
that there is a distinction between the case where multiple
receivers each receive copies of all messages, and the case
where only one of the multiple receivers receive each message.
In the former case, we can use linked mailboxes but in the
latter case, one mailbox is sufficient.

Many-to-one communication can also be configured by linking
multiple mailboxes to the same mailbox.  Indeed, any
arbitrary communication topology may be built up using 
links.

\subsection{Mailbox Server}
All the above pre-supposes that a mailbox can be uniquely
identified in a network and can be accessed by all machines
on the network.  This can be guaranteed by ensuring that
when a mailbox is created, the identifier returned is a
combination of the process number and the number of the
mailbox in that process.  The process number is allocated
by an external mailbox server program.  Note that the
process number is a generalisation of the machine number
since a machine may run many processes.

When a process requires the use of mailboxes, it first 
registers with the mailbox server which allocates a process
number to it.  The mailbox server replies by sending the
process numbers and physical network addresses of all the
other registered processes.  It also notifies existing
registered processes that there is a new process.  By
keeping all processes up-to-date with this information,
processes may communicate with each other directly without
contacting the mailbox server again.  The mailbox server
does not become a bottleneck in the system and in fact
mailbox communication can continue even if the server
program is terminated.  Of course in this case, any further
changes to the registered process list will not be reflected.

Using a mailbox server, a set of processes can cooperate
and communicate with each other by registering with this
server.  The set of processes is called a mailbox group.
A completely different mailbox group can exist if there is
another mailbox server program running.  In general, there
is no limit to the number of mailbox groups.  Each group
is a completely independent system.

\subsection{Registering Mailbox Names}
In the model presented above, we can see how it would be
possible to communicate if we know the mailbox identifier.
However the bootstrapping problem of finding out the relevant
identifier still remains.

If a process is willing to accept incoming communication,
it should create a mailbox and register a name along with
the mailbox identifier.  This registration is done by
sending a message to the mailbox server program (the mailbox
server has a pre-defined address).  Thereafter, when another
process wishes to talk to the named process, it can query
the mailbox server program for the mailbox identifier.  This
is very similar to telephone directories.  The correspondence
between names and telephone numbers is stored in a telephone
directory.  If you do not know the number, you look up the
name.  The mailbox server program provides this necessary
directory lookup service.

\section{The Mailbox primitives}
We list below the mailbox primitives as used in IC-Prolog.  The
primitives are implemented in C and loaded into IC-Prolog using
the foreign code interface facility.

In the description below, input parameters are denoted by `?' and
output parameters by `\uphat'.

\begin{description}
\item[mbx\_create(Id\uphat)]
This creates a mailbox, returning its global address as an Id.

\item[mbx\_send(Id?, Term?)]
This sends a term to the mailbox specified by the global address Id. 
Sending is asynchronous (and therefore buffering is provided).

\item[mbx\_recv(Id?, Term\uphat)]
This reads a term from the mailbox specified by the global address Id. 
The primitive blocks until a message is received.

\item[mbx\_look(Id?, Term\uphat)]
This reads a term from the mailbox Id. 
The primitive blocks until a message is available.
A mbx\_look/2 call does not remove the message read. The mailbox is 
locked after such a call, so any other mbx\_read or mbx\_look calls 
suspend until the mailbox is unlocked. The reading process is supposed to test 
the message read and, depending on whether it is suitable or not, it should 
call mbx\_commit or mbx\_discard, both of which unlock the mailbox. 
mbx\_commit or mbx\_discard (whichever is chosen) should be run 
sequentially after mbx\_look, otherwise an error will occur.

\item[mbx\_commit(Id?)]
This unlocks the mailbox Id removing the message read, so the next reader
will read a different message.

\item[mbx\_discard(Id?)]
This unlocks the mailbox Id without removing the message read, so the next 
reader will read the same message.

\item[mbx\_check(Id?)]
This primitive checks whether there is a message available in the mailbox
specified. 
It is a non-blocking primitive.

\item[mbx\_close(Id?)]
This primitive closes the mailbox specified, breaking all the links from
or to it.

\item[mbx\_link(IdI?, IdO?)]
This links one mailbox (IdI) to another (IdO), allowing one to one, 
many to one, 
one to many or many to many communication. Link a 
mailbox to itself is not permitted.

\item[mbx\_unlink(IdI?, IdO?)]
This breaks the link between IdI and IdO.

\item[mbx\_getlinks(Id?, Links\uphat)]
This returns the links of the specified mailbox. Links is a list with two 
elements, the first is a list with the addresses of mailboxes to which Id 
is linked to, and the second element is a list with the addresses of 
mailboxes linked to Id.

\item[mbx\_clear(Id?)]
This removes all the unread message in the specified 
mailbox.

\item[mbx\_bind(Id?, Atom?)]
This binds a global mailbox address to a global service in the mailbox
server, making the address accessible to the whole system. There can be 
different services (Atom) with the same address (Id), but not 
one service with different addresses.

\item[mbx\_getid(Atom?, Id\uphat)]
This returns the global mailbox address associated with the global service 
specified. If the service is not recorded in the mailbox server, the 
primitive fails.

\item[mbx\_getname(Id?, Atom\uphat)]
This returns the global service associated with the global mailbox address 
specified. If the address is not recorded in the mailbox server, the 
primitive fails.

\item[mbx\_initdb(Pt\uphat)]
This initializes the mailbox server reading pointer, allowing 
sequential access to it using the mbx\_getdb/3  primitive.  It returns an 
identifier for the initial pointer.

\item[mbx\_getdb(Pt?, Atom\uphat, Id\uphat)]
This returns the global service and the global mailbox address associated with
it, reading sequentially from the mailbox server. The next call to this 
primitive will return the next entry. Pt is the identifier for 
the internal pointer.

\item[mbx\_closedb(Pt\uphat)]
This closes the mailbox server reading pointer created by 
mbx\_initdb/1. 
\end{description}


\section{Advanced Features}
\subsection{Out of Band Data}
\subsection{Polling and Time Outs}
\subsection{Security}
Restricted access can be ensured for the database and the mailboxes.
It is implemented in two layers. 

The first layer is a user level restriction. At mailbox creation time, 
read and write permissions can be defined for the user, group and others.

The second layer is a process level restriction, it filters the processes that 
pass the first layer. At mailbox creation time, a read password and/or a 
write password can be defined and every process wishing to access the mailbox 
must supply the correct password. 

These restrictions can be used for the internal data base as well, restricting 
the access to the services supplied.

The following primitives provide the services described (permissions can be
\readwrite, \readp, \writep or \none :

\begin{description}
\item[mbx\_create(Id\uphat, User?, Group?, Others?, RPas?, WPas?)]
\item[mbx\_send(Id?, Flag?, TimeOut?, Term?, WPass?)]
\item[mbx\_recv(Id?, Flag?, TimeOut?, Term\uphat, RPass?)]
\item[mbx\_look(Id?, Flag?, TimeOut?, Term\uphat, RPass?)]
\item[mbx\_commit(Id?, Flag?, TimeOut?, RPass?)]
\item[mbx\_discard(Id?, Flag?, TimeOut?, RPass?)]
\item[mbx\_check(Id?, Flag?, TimeOut?, RPass?)]
\item[mbx\_close(Id?, TimeOut?, RPass?)]
\item[mbx\_link(IdI?, RPass?, IdO?, WPass?, TimeOut?)]
\item[mbx\_unlink(IdI?, RPass?, IdO?, WPass?, TimeOut?)]
\item[mbx\_getlinks(Id?, TimeOut?, RPass? , Links\uphat)]
\item[mbx\_clear(Id?, Flag?, TimeOut?, Pass?)]
\item[mbx\_bind(Id?, TimeOut?, Atom?, RPass?)]
\item[mbx\_getid(Atom?, TimeOut?, Id\uphat, Pass?)]
\item[mbx\_getname(Id?, TimeOut?, Atom\uphat, Pass?)]
\item[mbx\_initdb(Ptr\uphat, TimeOut?)]
\item[mbx\_getdb(Pt?, TimeOut?, Atom\uphat, Id\uphat, RPass?)]
\item[mbx\_closedb(Ptr?, TimeOut?)]
\end{description}

The simpler primitives (as defined in a previous section) create
mailboxes with user \readwrite, group \writep and others \writep 
permissions, 0 read password and 0 write password and they always
supply 0 as the password.  These defaults have the effect of
disabling the security features.

\section{Implementation}
The design and implementation of mailboxes has been carried
out by Vincente Benjumea.  It is a completely self-contained
package written in C with its own internal data structures.
Hooks into the package are provided.  This makes the
implementation highly portable.

More details about the implementation to follow ...

\section{Examples}

\end{document}
