Multicellular Computing:
Discussion and Comments
Discussion
and comments on multicellular computing topics from various blogs,
other Web sites and relevant papers
Although
the multicellular computing site is not intended to be a blog, I'll
occasionally post discussion
from various bloggers, emails, and/or relevant papers below.
Amorphous computing - - Hal Abelson, Jacob Beal, and Gerald Jay Sussman, an MIT effort primarily aimed at Swarm-style groups
of computers. Roughly at the biofilm level. See
MIT Tech Report (2007). Their work is based on the following premise:
"A colony of cells cooperates to
form a multicellular organism under the direction of a genetic program
shared by the members of the colony. A swarm of bees cooperates to
construct a hive. Humans group together to build towns, cities, and
nations. These examples raise fundamental questions for the
organization of computing systems:
- How do we obtain coherent behavior from the cooperation of
large numbers of unreliable parts that are interconnected in unknown,
irregular, and time-varying ways?
- What are the methods for instructing myriads of
programmable entities to cooperate to achieve particular goals?
These questions have been
recognized as fundamental for generations. Now is an opportune time to
tackle the engineering of emergent order
to identify the engineering principles and languages that can be used
to observe, control, organize, and exploit the behavior of programmable
multitudes." (From their 2000 CACM paper).
Comment - This interesting work
explores what can be done with large numbers of identical elements
operating at a rather simple level of organization similar to
biofilms. They explicitly look to biological metaphors for
inspiration. They explore the limits of a model that lacks
specialization (hence the term amorphous), stigmergy (although
mechanisms for stigmergy could be programmed to emerge by cooperative
behavior) and apoptosis.
Steve
Johnson blogs
on 'Software Physics 101," July 1, 2006
Steve Johnson
argues in his blog for an
analogy between biology and modern software/computing very
similar to what I
propose.
"It has taken the IT
community nearly 60 years to develop a distributed objects architecture
based upon multicellular organization. This was achieved through a slow
evolutionary process via innovation and natural selection performed by
millions of independently acting programmers. Granted, this occurred
much faster than the three billion years nature took to come up with
the same architecture, but we could have done this back in the 1960s if
we had known better - after all, the object-oriented language Simula
was developed in 1965. Softwarephysics proposes that we use concepts
from biology to skip to solutions directly.
"
He then discusses his work in the '80s, in a mainframe
environment: "...
in 1985 I began developing an early mainframe
IDE (Integrated
Development Environment) called BSDE (Bionic Systems Development
Environment) that developed software based upon concepts from molecular
biology."
Comment: It's a very interesting
take on the history of computing and its parallels to other sciences.
However, it requires some mainframe background to fully appreciate the story.
His
more recent blog, includes additional history and background.
Ben Hyde blogs on his "Ascription is an Anathema to
any Enthusiasm" site May 30, 2006:
"Traditional Apache HTTPD has a very very primitive example of
apoptosis. There you have a swarm of child processes that handle the
incoming HTTP
requests. You can configure these children to commit suicide after N
requests.
I have built systems where processes commit suicide for
assorted reasons. Lack of customer is one. Memory bloat is a common
one. It is often a lot
easier to have them die than fix all the legacy problems that cause
them to leak
this or that resource. And then I have built systems where suicide and
murder
are used when various handshaking patterns fail. These are useful when
you can’t
control some of the components."
Response: "...suicide and
murder are used when various handshaking patterns fail. These are
useful when you can’t control some of the components." This is
precisely the situation that
motivates the
apoptosis
idea when dealing with the
"out of control"
complexity in large multicellular systems.
There is an interesting distinction between sepuku and "fall on your
sword" Falling on your sword usually has the connotation of
sacrificing yourself for a superior or perhaps scapegoating yourself --
a very "Western" notion. Sepuku usually has the connotation of
removing yourself due to something like "shame" at your failure to live
up to the expectations of your role in society. That is, sepuku
benefits a whole social system whereas "falling on your sword" benefits
superiors in your particular hierarchy. Apoptosis is like the
former, benefiting the whole organism, not like the latter.
Sam
Ruby, in his blog
May 25, 2006, wrote (in part) Steve Burbeck [on the
Intertwined Principles
page]: says:
In biology, the four principles stand together. So should they in
multicellular computing
I found the last paragraph jarring. Why are “architecture” and
“design” in quotes?
Upon further reflection, I think that Steve (perhaps without realizing
it) is starting to explore an entirely new perspective.
Take the four principles as a given. Intertwined-ness then
becomes a meta-principle. One of the contributors to the success
of wikis is the syntax people use. Similarly, HTTP without HTML
(or vice versa) wouldn’t have taken hold.
Abstractions
leak, deal with it.
Response: On your main point, yes
intertwined-ness
is a meta
principle. It happens most often when architectural principles
evolve together -- hence inevitably co-evolve. And, yes, it has
something to do with Joel's abstraction leakage principle (although I
hadn't seen Joel's piece on that idea -- very nice stuff!). As
Joel points out, some leakage is inevitable because elements (web
pages, wiki pages, cells, ants, ...) participate in more than one at a
time. So the leaks tend to travel through elements that happen to
be at a nexus of several principles hence their behavior affects them
all. (I hope that makes some sense...)
The quotes around "architecture" reflect the fact that we don't usually
think of an architecture of messages themselves, i.e., that they should
be multi part to deal with multiple architectural features of the
system at once. Such multi-purpose messages, in effect, provide
the underlying mechanism of the abstraction leakage! Kinda
subtle. Perhaps I should remove the quotes and say that
explicitly.
The quotes around "design" were intended to put a little doubt into the
notion that we can "design" something so complicated. We try, but
then we watch helplessly as unexpected emergent properties pop up.
Lillen
& Bhargava, in "A scheme for
privacy-preserving data dissemination" Systems, Man and
Cybernetics, Part A, IEEE Transactions, May 2006, vol 36 no.3
They bring up apoptosis in their abstract:
" The proposed
scheme for privacy-preserving data dissemination enables control of
data by their owner (such as a weaker partner). It relies on the ideas
of bundling sensitive data with metadata, an apoptosis of endangered
bundles, and an adaptive evaporation of bundles in suspect
environments. Possible applications include interactions among patients
and healthcare providers, customers and businesses, researchers, and
suppliers of their raw data. They will contribute to providing privacy
guarantees, which are indispensable for the realization of the promise
of pervasive computing."
Comment:
I haven't read the paper (it requires a subscription) but from the
abstract it sure looks like an application not only of apoptosis, but
also of a
multicellular
messaging architecture.
Phil
Jones' Wiki
April 22, 2006 summarizes briefly some of my
stigmergy notions
in biology and
in computing.
He then asks: "
But then, what communication
isn't stigmergic? Writing must
be - ie. we leave writing around the environment. It seems like speech
shouldn't be. Is there a
MediaAndMaterials
question lurking here? Eg. that some sorts of communication are "more
stigmergic than others" and this can bias the overall system behavior
in certain ways?"
Response:
His question gets at the distinction between signals and cues
(discussed on my
Stigmergy
page). Signals are sent and received in real-time whereas cues
are deposited in the environment to be "read" later. So, yes,
writing is stigmergic whereas speech is not -- or was not prior to
audio recording, film, iPods and podcasts. The other distinction
has at least something to do with a notion of "place", i.e., the
"place" where cues reside. For cues to facilitate positive
feedback, i.e., self-organizing behavior, the behavior they "cause" in
subsequent activity needs to affect the same structure. That
notion isn't absolute. Cues, e.g., pheromones (scents) can be
blown on the wind, which is why predators hunt from down wind.
But place matters even then because the predators follow those scents
upwind to the
location of the
prey..
Peter
Small points out: that for stigmergy to be effective, "The
environment must be able to be changed locally by agents; and such
changes must persist long enough to affect the choice, parameters, or
consequences of [other] agents' behaviour. (This effectively rules out
stigmergy in empty or highly dynamic environments, such as space, air,
and water.)"
The notion of "place" in the digital world is a big nebulous, but not
meaningless. A wiki is a stigmergy structure that "lives" at a
given URL. Same with folksonomies. So one can think of URLs
as "places". But the web as a whole can also be thought of as a
stigmergy structure. The notion of "place" in that case might be
Google's URL since Google and other search engines "organize" the
Web. But, clearly, place becomes a more slippery concept in
cyberspace than in the physical world.
Matt
McAlister's blog
April 19, 2006, discusses multicellular stigmergy issues in the context
of search
and
tagging. Emergent bodies of tags, for example in Flickr, are
known as a "
folksonomy"
-- a term which denotes a cooperatively created taxonomy for
categorizing information.
A folksonomy is clearly a stigmergy structure. It is a
persistent set of metadata that helps to guide search in an
unstructured collection of information. People tag information in
a free form way. Others search tags in a free form way. Out
of this interchange, serendipity generates logical groups of similarly
tagged information which encourages others to add or modify the tags
they put on their information. This positive feedback slowly
provides organization above and beyond the organization naturally
provided by common agreements on the meaning of words. (
Arne Handt
discusses in his
blog the
idea that tags are analogous to pheromones, i.e., communication and
organization cues in a stigmergy structure.)"
Comment:
Matt makes a couple of good points: "If you think of each
type of human
data contributed to the information
pool on the Internet as elements and molecules (clicks, views, saved
things, sent things, tags, comments, ratings, individual blog posts,
wikipedia entries, etc.), then you can imagine bodies made up of those
pieces with unique purposes, behaviors, functions and roles." .A
very nice way to put it.
He also brings up the point of how folksonomies might
interrelate. Although the Internet can be thought of as one big
information pool, actually it is a heavily balkanized collection of
pools. I don't just mean by language (or state-sponsored
firewalls like those in China) but also by information type and
use. As Matt puts it: "...there's an abstraction layer out there
somewhere in the future that
will make it easier for me to jump from data pool to data pool more
fluidly to find what I need...and to interact with it." Yes,
indeed. I would state that as jumping from stigmergy structure to
stigmergy structure since these data pools are not disorganized
puddles, but loosely structured data organized by cues such as tags,
ratings, Google rankings, etc.
Johan Sundström blogs
April 15, 2006, about the stigmergy pattern in the context of user
scripts
(e.g., greasemonkey).
He
argues that: "The web page, in a user script setting, is
a stigmergic structure,
where an ecology of user scripts can work together to build new and
interesting applications, without the blessings of or participation
from the website page host."
He adds: "Next I would want to stigmergize-enable
GM_xmlhttpRequest
calls too, to provide the same ecology of specialized helpers to
process page-external resources to the scripts I write that pull
together data from many locations into tools like
Book
Burro. But let's play this one step at a time." This seems to
resonate a bit with Matt McAlister's desire to jump from pool to pool.
Comment:
Good stuff! It is worth reading this blog carefully.
Patrick
Logan's weblog
discusses apoptosis in the context of
Erlang,
"Apoptosis is an increasingly recognized pattern, e.g. from the Erlang
community the idea that small components should give up quickly and
allow a higher-order component handle the fault."
Comment:
Erlang is a language (and runtime) specialized for distributed,
reliable soft real-time systems, e.g., telecommunication systems.
Today that sort of application may seem light years away from the wild
and woolly Internet. But tomorrow, or the day after, the majority
of the Internet population will be cell phones, not PCs. So
Erlang-style systems may well merge into the Internet with interesting
cross pollination!
Alexander
Stojanovic's blog
April 14, 2006, discusses the basic issues of what I call multicellular
computing and
he apparently calls "amorphous computing" (after Michael Resnick's book
Turtles, Termites and Traffic Jams (StarLogo). It's clear from
his comment that we are talking about the same thing. Here's a
bit of it:
"How do we obtain coherent
behavior from the cooperation of large
numbers of unreliable parts that are interconnected in unknown,
irregular, and time-varying ways? What are the methods for instructing
myriads of programmable entities to cooperate to achieve particular
goals? These questions have been recognized as fundamental for
generations. Now is an opportune time to tackle the engineering of
emergent order: to identify the engineering principles and languages
that can be used to observe, control, organize, and exploit the
behavior of programmable multitudes. We call this effort the study of
amorphous computing."
Comment:
The principles I propose --
specialization,
polymorphic
messaging,
stigmergy,
and
apoptosis --
are an attempt to provide an architectural
framework for dealing with such questions.
Stephanie
Forrest's group out of Univ. New Mexico published a
paper
that addresses the computing monoculture and viral code issues in a
novel and interesting way. Their ideas are summarized
here.
In brief, the idea is that each computer "encrypts" its hardware
instruction set. All code on the machine "knows" the encryption
key whereas any code injected into the system, e.g., by a virus, does
not. So the viral code is, effectively,random junk. They
have some nice discussion about the probabilities of random code doing
anything useful (to anyone) before crashing and that probability is
very near zero.
Comment:
This idea provides at least the start of a way to think about how code
could be allowed to to be transferred between machines with some
safety. In my view, moving code should simply be
taboo. But in the mean time, approaches such as this could change
the playing field in interesting ways.
Kenneth N. Lodding (Nasa)
published a very nice article,
"Hitchhiker's
Guide to Biomorphic Software" (
ACM Queue vol.
2, no. 4 - June 2004) which describes an explicitly biologically
inspired multicellular programming metaphor. (See
also) The article includes
a review of previous biologically inspired software approaches
including neural nets, stigmergy inspired problem solving, swarm
software, and the like. He defines Biomorphic Software thus:
"
In a nutshell, biomorphic software is simply algorithmic design
concepts distilled
from biological systems, or processes. It is biologically inspired
computing.
The common thread that runs through all current biomorphic
architectures is
that they describe dynamic, self-organizing systems. In biomorphic
architectures,
problem solutions emerge as the result of the interaction of numerous,
individual
elements within the system, rather than from the application of some
external
mechanism or algorithm. Biomorphic programs are not coordinated from
start to
finish by a controlling, global plan. Instead, control arises from the
interaction
of the individual elements, each viewing its local part of the world at
any
given moment. Control within biomorphic programs is decentralized.
Program execution
is distributed and parallel."
Comment: The focus of
his paper is on
designing
biomorphic/multicellular systems. That is, defining the
characteristics of
every part (cell) of the system, including the messages that flow
between them. That is a good
first step for exploring what can be done by a particular biomorphic
approach in a particular external environment. I have two
quibbles (and they are just quibbles, not disagreements) with that
approach. First, to design such a system and to understand the
full range of behavior that can emerge from a given set of elements and
interactions requires some understanding of the fundamental
architectural principles
that have evolved in biological systems. And second,
multicellularity is already
rampant in
the Internet and in institutional intranets, so we may learn
more about the possibilities of biomorphic software by studying the
phenomenon in the wild than by trying to build carefully designed
isolated systems.
Roy Sterritt & Mike Hinchey,
published an interesting article,
Apoptosis
and Self-Destruct: A Contribution to Autonomic Agents?, in
Formal Approaches to Agent-Based Systems, Springer Berlin/Heidelberg,
2004
ABSTRACT:
Autonomic Computing (AC), a self-managing systems initiative based on
the biological metaphor of the autonomic nervous system, is
increasingly gaining momentum as the way forward in designing reliable
systems. Agent technologies have been identified as a key enabler for
engineering autonomicity in systems, both in terms of retrofitting
autonomicity into legacy systems and designing new systems. The AC
initiative provides an opportunity to consider other biological systems
and principles in seeking new design strategies. This paper reports on
one such investigation; utilizing the apoptosis metaphor of biological
systems to provide a dynamic health indicator signal between autonomic
agents.
Comment: To read
the whole paper requires a SpringerLink account that I don't
have. The abstract is certainly enticing, though.
Steve
Oberlin has an interesting abstract on “Architecture
Recapitulates Phylogeny: How Scalability Requires Specialization”
in the Preliminary IEEE Cluster 2001
Conference Schedule
“There is an old saying in biology
asserting that ontogeny recapitulates phylogeny, expressing the belief
that the stages of development of an embryo, from one fertilized cell
to a complete human form, mimics the steps taken by our genetic
ancestors as homo sapiens evolved. There's an analogy that can be drawn
between this biological assertion and the evolution of parallel
processing.
SMPs and clusters alike have generally been configured with nearly
homogeneous functionality among processors. This has limited their
scalability for many large applications.
Recently, more specialization of purpose has crept into the roles
individual nodes play in cluster configurations. As clusters are scaled
further to take their place as the heirs to the roles formerly played
by custom-designed large-scale supercomputers, even more specialization
is needed to achieve the efficiency and manageability required to
perform satisfactorily on tough capability workloads in demanding
production environments, in the same way cells must differentiate and
specialize in larger complex organisms.”
Comment: Although he
speaks of parallel processing in the context of tightly coupled
clusters intended for supercomputing, his points apply more
widely. The notion that specialization is a prerequisite for
massive scalability is insightful. I would be interested to get
his take on 1) the need for polymorphic messaging so that each machine
needs know nothing about the internal specializations of the others, 2)
the value of stigmergy structures in which the specialized nodes can
deposit cues for other nodes (somewhat like a blackboard
architecture), and 3) the value of apoptosis for managing errant
or failed nodes. In my view, all four are prerequisites for massive
scalability.
Contact: sburbeck at mindspring.com
Last revised 8/13/2009