Monday, September 19, 2016

The Best Paper of SASO 2016

I have the distinct pleasure to announce that our paper at this year’s IEEE SASO conference, entitled “Self-adaptation to Device Distribution Changes,” has been awarded the Best Paper award for the conference.

In this paper, we tackle one of the quandaries of computer networks that live dispersed through the environment of the real world, like all of our phones, laptops, and other personal devices: how the distribution of those devices in space can affect the systems that we run on them.  When building a distributed system, it is disconcertingly easy to accidentally build in assumptions about the density or position of devices in space, so that a system can have its behavior change radically or even fail entirely, just because a couple of devices moved or because people bunch up in some places and spread out in others.  It has been very hard to predict when these situations may arise, or to find them through empirical testing, since these problems may happen only with large numbers or very specific conditions of positioning.  Worse yet, these issues may not even be apparent in any single component of the system, but only emerge nastily when you put the pieces together.

Our work makes a start on these problems by first making a theoretical analysis of ways in which these problems arise and identifying a new mathematical property called “eventual consistency,” that describes the behavior of systems where things do not break down when devices move or their density increases.  In essence, a networked system is eventually consistent if, the more devices there are, the smoother its behavior is and the less that each individual device matters.

The intuition of eventual consistency: more devices = smoother behavior
In many ways, this notion is an extension of the concept of self-stabilization, which says that a distributed system always converges to a predictable set of values.  Eventual consistency enhances that by saying that the values also shouldn’t depend very much on how many devices there are or where exactly they are positioned in space.  Accordingly, we have taken our previous work establishing a language of efficient self-stabilizing programs and restricted it to get a language of eventually consistent programs, which we demonstrated with some examples in simulation, showing that they became smoother and more similar the more devices we had in the simulation, just like they theory said should happen.

This is cool because it takes us another step toward being able to make a lot of the nasty difficulties of building distributed systems go away.  The recognition is nice too, particularly given this paper’s rather long and bumpy prior path towards publication—we first submitted a version of it more than two years ago, and it spent a long, long time in limbo and rejections before reaching its current happy state.  I also think this work may be important, as we cope with our increasingly computer-saturated environment, and look forward to continuing along these lines.

No comments: