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:

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