Book Review: Complexity

Complexity: A Guided Tour by Melanie Mitchell

[Read in July of 2009 but was delayed in writing the review.]

I came across this book during a bookstore trip and decided to purchase it as it included topics related to a couple of recent posts and previously read book, Linked: The New Science of Networks. I'm glad I did as it made me realize that many of the things that I am interested in fall under the domain of Complex Systems.

The book is structured as five parts and nineteen chapters as summarized below:

PART	CHAPTER	THEME
1		BACKGROUND AND HISTORY
	1	What is Complexity?
	2	Dynamics, Chaos, and Prediction
	3	Information
	4	Computation
	5	Evolution
	6	Genetics, Simplified
	7	Defining and Measuring Complexity
2		LIFE AND EVOLUTION IN COMPUTERS
	8	Self-Reproducing Computer Programs
	9	Genetic Algorithms
3		COMPUTATION WRIT LARGE
	10	Cellular Automata, Life, and the Universe
	11	Computing with Particles
	12	Information Processing in Living Systems
	13	How to Make Analogies (if You Are a Computer)
	14	Prospects of Computer Modeling
4		NETWORK THINKING
	15	The Science of Networks
	16	Applying Network Science to Real-World Networks
	17	The Mystery of Scaling
	18	Evolution, Complexified
5		CONCLUSION
	19	The Past and Future of the Sciences of Complexity

Part 1, nearly a third of the entire book, provides a thorough introduction to Complex Systems which are defined by the author as having the following properties:

1. Complex collective behavior (i.e. the whole is greater than the sum of the parts)
2. Signaling and information processing
3. Adaptation to environmental changes

Example complex systems cited were insect colonies, the brain, the immune system, economies, and the world wide web.

Chapter 2 was an enjoyable introduction to dynamical systems and chaos theory which I had only a cursory awareness of. The simple "rabbit population" example using logistic maps was a great aid in understanding the concepts of fixed/periodic/strange attractors, and a sensitive dependence on initial conditions (aka. the Butterfly Effect). New to me were the concepts of the period doubling route to chaos and Feigenbaum's Constant (which is just plain odd).

Chapters 3 and 4 covered concepts related to information and computation including: entropy, Maxwell's Demon, statistical mechanics, Shannon's information theory, Hilbert's problems, Godel's incompletness theorem, and Turing machines. Overall the treatment was good and a sufficient introduction for readers unfamiliar with these concepts.

Chapters 5 and 6 discussed the topics of evolution and genetics. I found the discussion on evolution interesting as I don't recall learning about the feud between the early Darwinians, who believed in continuous small variations, and Mendelians, who believed in discrete large variations. I also don't recall learning about the Modern Synthesis or the continued challenges in the form of punctuated equilibrium. Interesting stuff.

Chapter 7 discussed various ways of defining and measuring complexity as:

• size
• entropy
• algorithmic information content
• logical depth
• thermodynamic depth
• computatoinal capacity
• statistical complexity
• fractal dimension
• degree of hierarchy

While no single measure was identified as the measure, all were interesting to consider.

Chapters 8 to 10 discussed cellular automata, genetic algorithms, and artificial life. While the treatment was good, it felt light-weight after having just read The Recursive Universe. That said, Chapter 10 did provide a nice overview of Wolfram's work on cellular automata that augmented the prior material I had read on this subject.

Chapter 11 discussed the use of cellular automata for majority classification tasks. The specific task discussed was the determination of the dominant color in a one-dimensional vector of white and black pixels. The authors used genetic algorithms to evolve a set of CA rules that reliably performed this task by creating diagonal vectors that carried local majority-voting decisions which eventually intersected to produce a majority-vote for the entire original vector. The authors seemed unable to at first understand how the evolved CA worked but I thought it obvious as clearly any solution must involve the horizontal communication of local-majority votes in order to reach a global decision. It seems obvious (to me) that such horizontal communication would manifest as diagonal vectors when the CA evolutions are graphed vertically. I thought the use of particle equations to explain the phenomina was overkill but still interesting.

I enjoyed the author's account in Chapter 13 of her work on the CopyCat program which was designed to process analogies. The problem appears hard and the program was quite clever. I must admit I am extermely jealous that she got to work so closely with Douglas Hofstadter.

Chapters 15 to 16 discussed real-world network theory which included topics such as small-world phenomina, scale-free networks, clustering, preferential association, and network resiliance. Overall the treatment was good but mostly a review after having just read (actually listened to) Barabasi's book Linked, which I highly recommend reading.

Chapters 17 and 18 discussed network theory in the contexts of metabolic scaling and evolution which was very interesting. Some of this material was a review of Stuart Kauffman's work documented in his book Origins of Order. I previously read another of Kauffman's books, At Home in the Universe, which touched on some of the same topics but perhaps I'll add Origins to the list of potential future readings.

Chapter 19 concluded the book with an overview of the state of complexity science and the need for a unifying theory. While the field has accomplished many great things, it appears that a lot of difficult work remains which is perhaps why this is such an appealing topic.

In summary, Complexity is a great book that covers a lot of interesting topics. On a personal level, I am thankful to have read this book because, as I mentioned, it helped me realize that complexity science is the meta-topic that unifies many of my long term interests and therefore serves a guide for future research.

The Case of the Bloated Firmware

A few years ago, a co-worker of mine was working on an embedded micro-controller for a proprietary enterprise class motherboard. I don't recall the exact details but my recollection is that the micro-controller was responsible for monitoring a group of sensors and reporting any anomalies.

My friend used a commercial C compiler to develop the code for the micro-controller which compiled fine but resulted in a binary that was too large for the device's EPROM. He tried a number of things to reduce the binary's size but was unable to get the code to fit. During a serendipitous hallway conversation he asked if I could take a look at the problem and we returned to his cube on a mission to shrink the binary.

First, he walked me through the source code to explain the overall purpose and design. At the C level the code looked fine so we next took a look at the disassembled binary and found our first clue - one of the for loops seemed to generate an excessive amount of instructions. Strange.

Again, the exact details escape me but the code in question looked roughly as follows:

 1:  int value1[NUM_SENSORS];
 2:  int value2[NUM_SENSORS];
 3:  int value3[NUM_SENSORS];
 4:  
 5:  for(sensor_num= 0; sensor_num < NUM_SENSORS; sensor_num++) {
 6:  
 7:    value1[sensor_num] = readSensorValue1(sensor_num);
 8:    value2[sensor_num] = readSensorValue2(sensor_num);
 9:    value3[sensor_num] = readSensorValue3(sensor_num);
10:  }

What we observed was that each of the array references resulted in a lot of instructions to compute the specified element's memory address. Since the loop body included three references, it generated a lot of instructions. Matters were made worse by the fact that there were multiple loops of this kind in the code. We found our culprit.

To work around the problem, I suggested that he re-write the code as follows:

 1:  struct {
 2:    int value1;
 3:    int value2;
 4:    int value3;
 5:  } sensors[NUM_SENSORS];
 6:  
 7:  for(sensor_num= 0; sensor_num < NUM_SENSORS; sensor_num++) {
 8:  
 9:    sensors[sensor_num].value1 = readSensorValue1(sensor_num);
10:    sensors[sensor_num].value2 = readSensorValue2(sensor_num);
11:    sensors[sensor_num].value3 = readSensorValue3(sensor_num);
12:  }

We changed the loops, recompiled the code, and presto chango the binary was small enough to fit!

A quick look at the disassembly confirmed my hypothesis that writing the code as proposed would result in only a single array element address calculation in the loop body - the address of each structure member was just an offset from the array element's starting address. The array element address calculations were still inefficient but we had reduced their number enough for the binary to fit within the device's EPROM. Success!

Overall, this wasn't a particularly difficult problem and didn't take that much time to resolve. However, the necessity to imagine how the compiler would respond to restructuring the code made this a fun, and memorable "bug" to work on.

Dan Weinreb Talk at Google

In August, Dan Weinreb gave an interesting talk at Google on ITA Software's high-performance transaction system for airline ticket searching and pricing. ITA's software serves as the foundation for more well known travel pricing services like Orbitz who is an ITA customer. The problem ITA attempts to solve is extremely complex as explained in this slideument by Carl de Marken.

Amongst the Lisp community, ITA is famous for the signficant use of Lisp in their system, hiring well-known Lisp hackers, and using programming puzzles to filter job applicants.

Given my deep interest in all things Lisp (programming, lisp-machines, A.I., etc), Dan's blog is one of my favorite websites and someday I hope to meet him at a Boston Lisp Users meeting (if I can ever make it to one again).

Nice talk and worth watching if you're interested in this kind of thing.

The Case of the Replayed Queue

A number of years ago, I wrote a Linux device driver for a host bus adapter (HBA). The interface to the HBA consisted of two circular buffers, one to send information to the HBA (TxQ) and another to receive information from the HBA (RxQ). In this particular project, the HBAs were being used in a non-standard way to implement a bi-directional communication link between two Linux systems. As a result, the driver sent both commands and responses via the TxQ and received both commands and responses via the RxQ. In both cases, the driver communicated with the HBA using fixed-size data structures called IO control blocks (IOCBs).

Another aspect of this non-traditional use of the HBAs was that a proprietary upper layer protocol was used instead of the standard protocol used with the HBA. In this case, the protocol command packets did not fit within a single IOCB. As a result, two IOCBs were needed to send and receive command packets between the driver and HBA. These IOCB pairs were required to be adjacent in the circular buffers.

As the project reached the beta-testing phase, a perplexing driver bug began manifesting during QA testing. The failure was extremely rare happening only once a day while under heavy load. Unfortunately, the unit-test I had created to test the driver ex-situ continued to run without error so the problem was only occurring in-situ in QA'a full system configuration and under their heavy load. Oh bother.

Faced with a difficult bug and a nearing deadline I got straight to work on figuring out the problem. To start, I reviewed the QA logs to determine a pattern to the failures. The evidence suggested that the driver was re-processing protocol packets that had already been handled. To me this indicated a potential problem with the RxQ circular buffer but a code-review didn't reveal any obvious bugs.

I proceeded on to debugging the driver in-situ. Unfortunately, for reasons that I can't recall, I had little success using a kernel debugger. As a result, I initially tried to use print statements but the verbose system messages generated by the failure caused the information to immediately scroll off the screen. I tried sending debug information out a serial port but this slowed the system down enough to significantly increase the time between failures beyond practicality. Hmph.

After a week of frustration and an increasing pressure from the team to resolve the bug, I decided to take a fresh view of the problem. First, I considered what could cause the driver to replay the RxQ and quickly concluded that erroneously putting the tail-pointer past the head-pointer could cause the problem. A quick review of the head-tail pointer management code didn't reveal any mistakes. Hmph.

Next, I considered how the head-tail pointer code could be tricked into putting the tail pointer beyond the head. I reasoned that one way this could happen was if the driver thought the contents of the circular buffer were longer than its actual size. If this were the case, then when the driver updated the tail pointer it would put it past the head which would erroneously make the circular appear full when the driver re-examined it. But what could make the driver think that the buffer contents were longer than they actually were?

After some deep pondering the problem hit me, it must those multi-IOCB commands! My thought was that if for some reason the second of the two IOCBs wasn't posted to the queue when the driver processed it and if the driver didn't check for this condition, that the driver would adjust the tail pointer as if the second IOCB was present which would put it after the head pointer. The timing window for this seemed to be impossibly small but the failure was taking a day to manifest under heavy load so it had to be a rare sequence of events. If there is one thing that I have learned from my years working on large-scale parallel computer systems it's that highly improbably events occur far more frequently than one suspects.

I checked the code and confirmed that I had failed to account for incomplete multi-IOCBs. I added the necessary guards to the code, gave a new binary to QA, and crossed my fingers. A few days later success was declared and from then on the driver performed without error.

I never figured out why the HBA was delayed in posting the second half of the protocol command IOCBs to the RxQ. But you can be sure that I'll never forget to check for circular buffer fragments again!

The Case of the Errant DMA

The C++ puzzle that I posted about the other day got me thinking of various bugs that I've helped root-cause in the past. I thought it would be fun to post about some of the most memorable ones as a series of posts tagged as BugHunts.

About a year ago, a programmer that I was mentoring ran into a problem with errant DMAs in a ATA device driver that he was writing for a proprietary operating system (mostly as a training exercise). Said programmer did his initial development in a virtualized environment (i.e. virtual machine running on a hypervisor) and the device driver worked just fine. However, when run on a real platform the second and subsequent DMA operations would access "random" memory locations instead of those specified in the supplied scatter-gather lists.

After confirming that the basic scatter-gather code was working properly, the developer asked if I could help identify the problem. I started off by asking him to walk me through how the DMA operations were supposed to occur. Next, we walked through the code to ensure that it matched his description. Not seeing any obvious bugs, we then proceeded on to running the code, breaking into the debugger, and inspecting the scatter-gather lists to make sure that they contained the correct source/destination addresses. We observed the first DMA operation, which always worked, and the subsequent operations, which always failed, but saw no differences between the two. Humph.

At this point, I suggested that we focus on the fact that the first operation always succeeded but the subsequent operations always failed. I asserted that there must be a difference between how the first and subsequent operations were set up. So again we inspected the code and watched the execution in the debugger but didn't see any differences. Double humph.

After some thought, I then hypothesized that perhaps the first DMA operation was unexpectedly altering settings that were setup during the device driver's initialization. Since these setup operations were performed outside of the DMA setup code, we wouldn't observe any execution differences between the first and subsequent operations. So again we walked through the DMA operation but this time considered the additional configuration settings that they depended on. Bingo.

The chipset in question used a memory resident scatter-gather list. Since only a single DMA operation was outstanding at any time (per ATA channel) the developer pre-allocated the memory region during the device driver's initialization and wrote the region's base address to the appropriate chipset register. Since the same memory region was re-used to hold the scatter-gather list for each operation, the developer didn't re-write the base address to the register for each operation.

It turned out that on the virtualized platform the emulated ATA chipset left this register unchanged between operations, hence the device driver worked fine. However, on the real platform the chipset modified the register to point to the active scatter-gather element as the DMA operation was performed. As a result, the first DMA operation completed OK while all subsequent DMA operations walked off the end of the scatter-gather table and misdirected the DMA accesses based on the random data present in memory above the scatter-gather table. Once the developer added the code to re-initialize the scatter-gather base address register for each operation everything worked fine.

After the bug was fixed, the developer stated that he found this behavior surprising. I explained that having worked on designing ASICs in the past, I wasn't at all surprised that the hardware reused the register to hold the address of each scatter-gather element as the operation progressed; all's fair in ASIC design when it means saving some gates!

He then wondered how he could find such bugs in the future without having similar low-level hardware experience. I told him that the important lesson from the exercise was that once the possible errors have been ruled out you need to suspend disbelief and begin considering the impossible errors. Often our understanding of complicated systems is incomplete or flawed, therefore things we assume to be impossible may in fact be possible and therefore must be considered. I explained that this is a skill that must be hard-won over time through solving progressively harder bugs. I encouraged him to seek out hard bugs, spend time trying to resolve them on his own, but if stuck to utilize the already hard-won experiences of his mentors to accelerate his own skill development. This is the advice that has worked for me during my career and I am confident that the developer in question will do just fine.

Anyway, this particular bug was fun because it required thinking about how the system affected the program rather than how the program affected the system. These kinds of puzzles are always fun… after you've figured out the problem that is.

Fun C++ Problem

Today a co-worker of mine ran into an interesting C++ inheritance problem that perplexed the usual lunch crowd. Some might call this a character flaw, but when presented with puzzles like this I feel compelled to figure them out. So, when I got back to my desk I reduced the problem to the following minimal program and got to work on figuring out the root-cause.

 1:  class Superclass
 2:  {
 3:  public:
 4:    void  foo(int aParameter);
 5:    void  foo(int  oneParameter,
 6:              int  twoParameter);
 7:  };
 8:  
 9:  class Subclass : public Superclass
10:  {
11:    void  foo(int aParameter);
12:    // inherits foo(int, int)
13:  };
14:  
15:  void Superclass::foo(int aParameter)
16:  {}
17:  
18:  void Superclass::foo(int  oneParameter,
19:                       int  twoParameter)
20:  {}
21:  
22:  void Subclass::foo(int aParameter)
23:  {
24:    foo(aParameter, 2);
25:  }
26:  
27:  int main(int argc, char * argv[])
28:  {
29:    return (0);
30:  }

In words, there is a super-class, Superclass, with an overloaded method, foo(), that has two variants - foo(int) and foo(int,int). In addition, there is a sub-class, Subclass, derived from Superclass that redefines the foo(int) variant but inherits Superclass's foo(int,int) method.

Straight forward, right? Nope.

$g++ borked.cpp 
borked.cpp: In member function ‘void Subclass::foo(int)’:
borked.cpp:26: error: no matching function for call to ‘Subclass::foo(int&, int)’
borked.cpp:24: note: candidates are: void Subclass::foo(int)

For some reason the compiler isn't able to resolve the call to the inherited foo(int,int) when called from Subclass's foo(int) method. How strange.

Commenting out the offending call on line 24 allows the program to compile and dumping the symbol table yields the expected results:

$nm a.out
0000000100000ea4 s  stub helpers
0000000100001048 D _NXArgc
0000000100001050 D _NXArgv
0000000100000e60 T __ZN10Superclass3fooEi
0000000100000e6e T __ZN10Superclass3fooEii
0000000100000e7e T __ZN8Subclass3fooEi
                 U ___gxx_personality_v0
0000000100001060 D ___progname
0000000100000000 A __mh_execute_header
0000000100001058 D _environ
                 U _exit
0000000100000e8b T _main
0000000100001020 s _pvars
                 U dyld_stub_binder
0000000100000e24 T start

All the methods are present and have unique signatures. Recompiling with the -fdump-class-hierachy option also doesn't produce any suprises - there is no vtable magic going on.

$g++ -fdump-class-hierarchy borked.cpp
$cat borked.cpp.002t.class 
Class Superclass
   size=1 align=1
   base size=0 base align=1
Superclass (0x1407c18c0) 0 empty

Class Subclass
   size=1 align=1
   base size=1 base align=1
Subclass (0x1407c1930) 0 empty
  Superclass (0x1407c19a0) 0 empty

As a final piece of the puzzle, fully qualifying the call to foo(int,int) as follows resolves the problem.

void Subclass::foo(int aParameter)
{
  Superclass::foo(aParameter, 2);
}

Now, I am no C++ guru but I do have a fair amount of experience with it - mostly from writing system level code for a proprietary RTOS that was written in C++. In fact, I wrote a loadable module framework for that RTOS that included a runtime dynamic linker capable of handling C++ intermediate object files. So, I'd like to think I have a decent knowledge of the C++ object model and yet this problem made little sense to me.

As is often the case, I didn't know the anwser to the problem but I did know enough to determine the right keywords to Google for the answer. The solution is to add a using declaration to the Sublcass's definition.

class Subclass : public Superclass
{
  using Superclass::foo;

  void  foo(int aParameter);
  // inherits foo(int, int)
};

As I now understand the situation, when a set of overloaded methods span the base and derived classes, the using declaration is required to introduce the base class's methods into the scope of the derived class. Without the using declaration, the compiler can't resolve the reference to the base class's method without fully qualifying it. Good to know!

I had a lot of fun figuring this out despite the fact that it took 20 minutes of time out of an already busy day. But, sometimes you just have to let the inner-geek exercise itself!

As an aside, I recommend Stanley Lippman's book Inside the C++ Object Model to anyone interested in learning the inner workings of the C++ object model.

Nice Finance Video Collection

While web-surfing I stumbled across a nice collection of YouTube videos by Bionic Turtle on statistics, finance, and quantitative finance.

The videos tend to be short (under ten minutes) which makes them convenient to watch. Also, the author effectively uses Excel to work through examples and highlight the key points.

So far, I've only watched a handful of these videos but I plan to work my way through them gradually with a priority towards the topics relevant for re-balancing and evaluating the performance of my portfolio.

An Algorithmic Trading Primer

While I was getting my MBA I developed a strong interest in quantitative finance. I doubt I'll ever pursue a career in this field but I continue to enjoy reading about it in my spare time as part of a larger, general interest in applied mathematics (more about that in a future post).

Needless to say, I was eager to read the paper Algorithmic Trading: A Primer published in the summer 2009 issue of The Journal of Trading.

Unfortunately, I apparently misinterpreted the title as instead of discussing the algorithms themselves, the article covered the high-level points that clients of algorithmic trading firms should be aware of. To this end the article did cover some important points including:

• The desire (nay need) for algorithms to increase trader productivity
• The importance of Regulation NMS and why it favors electronic trading (which I must admit was new to me).
• The basic framework of algorithmic trading systems such as performance benchmarks, assumptions, etc.
• The rationale for and limitations of using log-normal models for price fluctuations.
• The importance of avoiding trades that signal the market and may therefore invalidate the algorithm's model.
• The importance of using the right algorithms at the right time to achieve the intended goals.

So, although the article didn't cover the topics I had initially hoped for I did find it a useful read anyway.

Book Review: Outliers

Outliers by Malcolm Gladwell

An interesting book asserting that rather than just latent talent, an individual's success is do to:

• timing: some people are born at just the right time to take advantage of historical watershed moments (e.g. the PC revolution) or age-based selections (e.g. birthday cut-offs for joining sports teams, schools, etc).
• practice opportunities: Gladwell asserts that the "universal" requirement for achieving expertise is 10,000 hours of practice. Gladwell further asserts that successful individuals have often been given abnormal opportunities to obtain that amount of practice in a short period of time and at an early age.
• environment: the amount of nurture and support that a person receives from his family and community has a significant effect on their success. This includes parents teaching their children how to be assertive, and actively guide their own lives.
• culture: cultural values and behaviors can have a profound effect on an individual's level of success.

To some degree, Outliers reminded me of other recent readings:

• In the Black Swan, Taleb asserted that individual success in "scalable" fields was due primarily to luck and a rich-get-richer effect. In Outliers I think Gladwell provides a compelling explanation for that phenomenon in his focus on lucky opportunities for obtaining expertise.
• The StudyHacks blog ran a post on how one person successfully entered the music industry by selecting a single nightclub to perform at and then focused all their energy on becoming the best performer at that venue. To me this resonated strongly with Gladwell's assertion that opportunities for obtaining 10,000 hours of practice are one of the keys to success.

So, there appears to be supporting opinions for some of Gladwell's assertions. Personally, I suspect that he is on the right track.

I enjoyed the first half of the book but found the second halves multi-generational discussion weaker as I suspect a "lucky event" can be found in everyone's family history if you go back a few generations.

Being a computer geek, I enjoyed the brief biographies on both Bill Joy and Bill Gates. I had no idea that Gates had so much programming experience before going to college. By all appearances both Bills had rare opportunities to become expert programmers at just the right age to ride the PC technology wave.

Some of the excerpts that I dog-earned were:

• Page 11: … the values of the world we inhabit and the people that we surround ourselves with have a profound effect on who we are.
• Page 42: (regarding the assertion that 10,000 hours of practice are required to become an expert at any particular skill) … ten thousand hours is an enormous amount of time. It's all but impossible to reach that number all by yourself by the time you're a young adult. … In fact most people can only reach that number only if they get into some kind of special program … or if they get some kind of extraordinary opportunity that gives them the chance to put in those hours.
• Page 149: Those three things - autonomy, complexity, and a connection between effort and reward - are, most people agree, the three qualities that work has to have if it is to be satisfying.
• Page 267: … success follows a predictable course. It is not the brightest who succeed. … Nor is success simply the sum of decisions and efforts we make on our own behalf. It is, rather, a gift. Outliers are those who have been given opportunities - and who have had the strength and presence of mind to seize them.

Upon reflection, I reduced (perhaps too far?) the book's message down to the following three points:

1. Pick a meaningful skill and practice it as much as possible.
2. Maximize your exposure to opportunities that require the chosen skill to be successful and provide more practice.
3. Aggressively pursue the opportunities that you come across to extract the most value from them.

Over all a good book, and worth the time to read it.