🚀 go-pugleaf

When is	an application ``distributed?''
=======================================

To answer this question, we will try to	find the borders of the
domain	of  distributed	applications.  It seems	to us that this
is better than describing an arbitrary point within the	 domain
by  summing  up	 some  properties that distributed applications
usually	have.  We will start by	naming four  extreme  examples,
each  running  on  two	processors.  We	take it	as self-evident
that there must	be at least two	processors involved in	a  dis-
tributed application.

Example	1.  One	processor calculates the odd-numbered  decimals
     of	 pi;  another the even-numbered	in parallel.  This is a
     distributed application.  Note that there is no communica-
     tion  involved, although there might be some in the end to
     merge the results.

Example	2.  We have a client process on	 one  processor	 and  a
     server process on another,	communicating using RPC.  There
     is	no parallelism,	 since	the  client  blocks  while  the
     server runs, but this still is a distributed application.

Example	3.  One	processor calculates decimals of pi; another is
     doing  a  compilation.  This is not a distributed applica-
     tion, although the	processors are running in parallel.

Example	4.  Two	unrelated processes communicate	while  contend-
     ing  for a	resource, such as a shared disk.  This is not a
     distributed application either, although there is communi-
     cation between the	processes.

The results can	be summarized as follows:

       example | distributed | parallel	| communication
       --------|-------------|----------|--------------
	  1    |     yes     |	yes	|      no
	  2    |     yes     |	no	|      yes
	  3    |     no	     |	yes	|      no
	  4    |     no	     |	maybe	|      yes

Examples 1 and 4 show that communication is neither a necessary
nor  a	sufficient property of distributed applications.  Exam-
ples 2 and 3 show that distribution  and  parallelism  are  not
directly related either.

    Definition.  A distributed application is an application
		 carried out by two or more processors.

This leaves the	terms ``application'' and ``processor''	 to  be
defined.   For	example,  a  data-flow machine is a distributed
system on a low-level, although	on the user level it is	neither
an  application	 nor distributed.  Another example is a	distri-
buted application running on a uniprocessor that is  simulating
a  distributed	system.	  A  distributed application running on
this simulator is still	a distributed application, although  in
reality	 there	is  only  one  processor  and  no communication
involved at all.  We believe that everybody has	intuitive ideas
of  what  an  application and what a processor is, and will not
try to obscure these ideas with	a formal definition.

What is	a distributed system?
=============================

We have	defined	a distributed application, but as we have  seen
in  the	 example  of  a	 distributed  application  running on a
uniprocessor, a	distributed application	does not imply	a  dis-
tributed  system.   What is a distributed system, then?	 Again,
we try to define the borders of	the  domain.   We  assume  that
there must be two or more processors.

Example	1.  There are two computers in the same	room which  are
     not  physically  connected	 in  any way.  Whether they are
     both computing parts of the same application or not,  they
     do	not make up a distributed system.

Example	2.  Two	computers are connected	by an  Ethernet.   They
     are  not  communicating  over the network,	and never have;
     still, the	possibility for	communication exists.  They are
     a distributed system.

Example	3.  Two	processing units, each	with  their  own  local
     memory,  have  access  to	a  global bus and common shared
     memory.  They compute independently, but  can  communicate
     through the shared	memory.	 They are a distributed	system.

Example	4.  A computer is made up, among other components, of a
     CPU  and  a  disk drive.  The disk	drive is a slave to the
     CPU, but once it has received a request from the  process-
     ing  unit,	 it  does some processing independent of and in
     parallel with the CPU.  On	the level of a systems program-
     mer,  this	 is  a	distributed  system.   There is	no real
     difference	in driving a disk controller or	a network  dev-
     ice, especially if	the network is reliable.  On the user's
     level, the	system is not distributed.

Example	5.  A processor	is a dedicated file server.   It  is  a
     slave  to the requests of other processors	connected to it
     through a network,	but after receiving a request, it  does
     some  processing  independent  of and in parallel with the
     requesting	processor.  On the level of a systems  program-
     mer,  this	 is a distributed system.  On the user's level,
     it	is not.

	       | distributed |	  shared     |
       example |   system    |	  memory     | communication
       --------|-------------|---------------|--------------
	  1    |     no	     |	    no	     |	    no
	  2    |     yes     |	    no	     |	 possible
	  3    |     yes     |	    yes	     |	    yes
	  4    |     yes     | yes (sort of) |	    yes
	  5    |     yes     |	    no	     |	    yes

The  examples  suggest	the  following.	  The  possibility  for
communication  is  necessary  for  a  distributed  system.  The
method of communication	is irrelevant;  whether	the  processors
communicate  via  a network, shared memory, or device registers
(in the	case of	the disk drive), they still make up  a	distri-
buted  system.	A given	system can be distributed on one level,
and not	distributed on another,	higher,	level.	 Most,	if  not
all  systems  are distributed on some level, hardly ever on the
user's level.

    Definition.  A distributed system consists of two or more
		 processors which have the ability to commun-
		 icate with one another.

What is	a distributed operating	system?
=======================================

The set	of distributed systems includes	 not  only  distributed
operating  systems, but	also distributed database systems, dis-
tributed airline reservation systems, and systems with multiple
operating  systems,  such  as the UNIX BSD4.3 operating	system.
This last system, however, is not a distributed	operating  sys-
tem,   since  it  does	not  support  distributed  applications
directly.  So what features should an operating	system for mul-
tiple  computers  have	before	it deserves the	title ``distri-
buted?''

This is	where we get into the fuzzy areas.  ``When is a	 system
an  operating  system?''  is a similar question.  A system that
simplifies disk	access in the form of  files  is  an  operating
system.	  A  system that supports multi-tasking	is an operating
system.	 A distributed operating system	must include  at  least
these  features	 in combination	with the ability to communicate
between	machines.

But this is not	enough.	 A distributed application  needs  sup-
port  for  starting  processes on different processors,	support
for communication between the processes	 independent  of  where
they  run,  load  balancing and	fault tolerance	mechanisms, and
control	 for  distributed  processes  (signaling,  etc.).    An
operating   system  that  supports  some  of  these  mechanisms
directly can be	called	distributed.   So,  although  the  UNIX
4.3BSD system could be made into a distributed operating system
by adding these	mechanisms to it, the way it currently	exists,
it is not.

			Jennifer Steiner (jennifer@cwi.nl)
			Robbert van Renesse (cogito@cs.vu.nl)
			The Amoeba Project
			Amsterdam