At the most recent Embedded Systems Conference in Boston, emergentcomplexity was discussed in a class presented by Brian Cruickshank,titled “Keeping Agile ” a test-centric approach tosoftware development (ESC-242).”

Until just a few years ago most embedded systems were closed, staticand non-connected, with many applications ranging from a few hundred toa few hundred thousand lines of code, written for a single processor orcontroller in a design. As embedded designs become increasinglycomplex, based on multi-cores, multiprocessors, wired and wirelesslydistributed sensors and controllers, emergent complexity is indeed atopic that deserves closer examination.

Emergent complexity deals with the nature of open, dynamic complexsystems – how order emerges spontaneously out of chaos, how larger andmore complex patterns are replaced by smaller and less complex ones,how one pattern emerges locally and when and how it spreads throughouta system to replace another more dominant one.

Since it became an area of intense study, the analysis of thebehavior of open, dynamic, and adaptive complex systems has been usedto bring clarity to the behavior of a wide array of phenomena:biological, environmental, ecological, physiological, physics, social,networks, the Internet and the World Wide Web.

One of the most comprehensive books I have read on the topic is Swarm Intelligenceby James Kennedy and Russell C. Eberharten, with Yuhui Shi. Anothermore recent book isEric Beinhocker's The Origin of Wealth. While thelatter book focuses on using emergent complexity to explain theevolution and operation of economies and markets, it also summarizeshow useful the study of complex systems is in a wide range ofdisciplines. Parenthetically, both books provide insights into howtechnology innovation occurs and evolves.

But it is an earlier book by a seminal researcher in this field, Stuart Kauffman – “The Origins Of Order” – that has had the most impact on my own thinking, especially in itsdescription of the spontaneous emergence of new patterns in simpleBoolean networks. What amazes me is the small number of Boolean nodesthere needs to be in a system before it exhibits the phenomena ofemergent complexity – not billions or even millions, but mere thousandsor less.

After thirty years of studying complex systems in general andBoolean networks in particular, it has been determined that thebehavior of such dynamic, connected and adaptive systems depends on atleast three variables: (1) the number of nodes; (2) how much everythingis connected to everything else and (3) the bias in the rules – themicro-rules – guiding the behavior of the nodes. Often, new patterns donot emerge in the center of the system, but at the edges, and near thediscontinuities. Under the right conditions, order emerges out of chaosand new patterns emerge and do battle with the old ones.

What this tells me is that developers of today's embedded systemshave more to worry about than defining their system properly, correctlywriting the code and building the hardware and then exhaustivelydebugging and testing the code. For an embedded developer whose job itis to establish a pattern and use it to direct the way in which asystem behaves, it would seem that the ability of complex systems toexhibit spontaneous re-organization would be troubling and something towatch.

In the context of a top-down organized system such as an embeddedapplication, wouldn't the ability of complex systems to organize andreorganize themselves be viewed as a problem as serious as a systemwith code to be debugged or a badly defined system description?

Under the right conditions, couldn't an embedded system – if it isopen and connected and sufficiently dynamic and adaptive -spontaneously generate alternative patterns that would bring it down,or at least, make it operate according to rules other than the ones theprogrammer thought he or she built in?

If this is the case, it also seems to me that in defense,programming practice has got to change. Among other things, it has gotto become more structured, less ad hoc, guided by common rules andbuilt using high level design tools that generate code that is “correctby construction.”

Emergent complexity is our friend
What struck me in Cruickshank's class on agile programming at ESC is thathe does not look on the emergent complexity of today's connected andadaptive embedded designs as just a problem to be solved. Rather, hebelieves the rules of emergent complexity can be used as a tool tobuild better, more reliable and fault resilient systems.

His solution: throw out the top-down centralized way of developing acode base that, as it becomes more complex, becomes harder to manage.Replace it with a decentralized codebase with micro-rules that allowthe emergence of a system which dynamically reconfigures itself tominimize information loss.

“As a large software codebase evolves over time it typically becomesincreasingly difficult to modify the software without unintended sideeffects,” he said. “Information about the software codebase is somehowlost, causing the codebase to become too complex to understand fully.And once complexity gets out of control, it takes control. We end upwith code that no one understands well enough to change withconfidence.”

Rather than combat this loss of information is by centralizingcontrolof the software codebase, he suggests using a more de-centralizedapproach using a concept borrowed from the study of the complex socialsystems of insects, called “stigmergy.”

Coined in the 1950's by Pierre-Paul Grasse to describethe mechanism of decentralized indirect information flow in socialinsects, stigmergy is the simple set of local 'micro-rules' that promptthe insects to respond to their environment in particular ways. In asituation in which many individuals contribute to a collective effort,he said, stimuli provided by the emerging structure itself can providea rich source of information for the workers. Previous work on thestructure directs and triggers new building actions.

“Software codebases can also be thought of as an emergentstructure,” said Cruickshank. “If developers were to leave enoughinformation behind in the codebase to guide other developers in thecreation of new content and modification of existing content, thenperhaps the codebase itself could become 'stigmergic'.”

To do this, Cruickshank thinks the codebase (including the code andassociated tests and documents), would need to provide feedback tocurrent and future developers to enable them to understand what thecode is doing, and why it is doing it.

“The information would need to be reliable and always in sync withthe current state of the code,” he said. “The structure of the codewould be of the same level of importance as the code itself. And a setof simple guidelines would be needed that, if followed by developers,would result in a coherent, understandable code base that is capable ofevolving over many releases of software.”

Whether we look upon the phenomena of emergent complexity as afriend or as an enemy, embedded systems are becoming more complex, moreopen, more dynamic and more adaptive. The nature of today'sincreasingly complex embedded systems needs to be understood morecompletely if we don't want to be constantly surprised.

What do you think? Leave a comment at the end of this article, callme at 602-288-7257, or email me at bccole@acm.org.

Embedded.com site editor BernardCole, who writes a regular column, The Netcentric View, is also a partner in the Techrite Associates LLC editorial consulting firm, which serveshigh technology firms.