Monthly Archives: July 2014


SyncMore travel for me and another great book.  This one is Sync: How Order Emerges from Chaos in The Universe, Nature, and Daily Live by Steven Strogatz.

The simplest example,  echoed on the book cover, is how do millions of fireflies synchronize their blinking.  There is no global “blink now” clock.  There is no master firefly orchestrating the performance.  So how do the fireflies end up synchronized?  It’s a simple idea that requires a lot of thought to truly understand.  The problem seems so simple when you first hear it.  I would have probably waved my hands at it, mumbled that the solution probably looked like XYZ, and then moved on. Only when you really try to solve it, do you begin to see the depth and subtly of this particular rat hole.

Strogatz also discusses many other sync problems:  pairs of electrons in superconductors, pacemaker cells in the heart, hints at neurons in the brain, and many others.  I was particularly intrigued by his discussion of the propagation of chemical activation waves in 2 and 3 dimensions.

There are no equations in the book, but Strogatz’s prose is sufficient to give a good taste of the novel mathematics he and others have used to address these problems.  It was a quick read.

As with most books I read, I begin to ponder how I might apply some of its ideas to multiagent systems.  For one, there are multiple ties to social networking (the A is-connected-to B kind; not the Twitter kind).  I also try to re-imagine his waves of chemical activations around a Petri dish transformed into waves of protocol interactions around a social network.

Most of Strogatz’s problems appear to require continuous-space and continuous-time.  Most of my multiagent system problems are simpler, requiring only discrete-space and discrete-time. I’ve developed some “half-vast” (say it out loud) ideas about using a model checker to approach protocol problems with sync-like elements.  I’d introduce some social operators into the model and an expanded CTL-like expression language.  Models would only need to be expanded enough to check the specific properties under consideration.  I’d also need to introduce agent variables that range over a group of agents to express the kinds of properties I have in mind.  The classic CTL temporal operators are strictly time-like, whereas the social operators would be strictly space-like.  Unfortunately, my current ideas could easily cause a massive state space explosion, so I still have work to do.

I so love reading books like Sync:  books that open intellectual doors and expand conceptual horizons.  I expect I’ll be thinking about these ideas for quite some time.

Using Commitments: When Things Go Wrong

SONY DSCThis is the last in my series on commitments, where we look at what happens when debtors don’t satisfy their commitments.

A debtor agent makes a commitment before satisfying the commitment.  In fact, that’s the whole point of using commitments.  It is a way for a debtor to tell others what it will do in the future.  Since debtors are assessed penalties when they fail to satisfy a commitment, they are certainly encouraged to do satisfy. However, bad things can happen between making and satisfying a commitment.

To paraphrase Spock in The Wrath of Khan, “There are two possibilities. They are unable to respond. They are unwilling to respond”First, a debtor may be unable to satisfy all of its commitments.  Toyota had a lot of commitments to deliver automobiles, but when the tsunami hit it, Toyota was no longer able to keep all of those commitments.

Second, event considering the cost of penalties, a debtor may be unwilling to satisfy all of its commitments.  Airlines knowingly overbook flights, creating more commitments than they can possibly keep.  They willing pay the penalties for their broken commitments.  This covers the case where debtors originally intended in good faith to satisfy their commitments but it is no longer profitable to do so, and where debtors made a commitment never intending to satisfy them.  We don’t distinguish between good and bad intentions in our commitment formalism, because it makes little difference and it is often impossible to distinguish anyway.

To model real world situations, we have to allow these messy cases.  We can not require debtors to always satisfy their commitments. The only thing we do require is that debtors must not leave their commitments hanging forever.  If they can’t satisfy a commitment, then then must eventually cancel it.   Commitment cancellation could be triggered by a timeout mechanism.