Distributed systems have two distinguishing features:

  • Asynchrony, or “absence of synchrony”: messages from one process to another do not arrive immediately. In a fully asynchronous system, messages may be delayed for unbounded periods of time. In contrast, synchronous networks always provide bounded message delays.
  • Partial failure: some processes in the system may fail while other processes continue executing.

It’s the combination of these two features that make distributed systems really hard; the crux of many impossibility proofs is that nodes in a fully asynchronous system can’t distinguish message delays from failures.

In practice, networks are somewhere between fully asynchronous and synchronous. That is, most (but not all!) of the time, networks give us sufficiently predictable message delays to allow nodes to coordinate successfully in the face of failures.

When designing a distributed algorithm however, common wisdom says that you should try to make as few assumptions about the network as possible. The motivation for this principle is that minimizing your algorithm’s assumptions about message delays maximizes the likelihood that it will work when placed in a real network (which may, in practice, fail to meet bounds on message delays).

On the other hand, if your network does in fact provide bounds on message delays, you can often design simpler and more performant algorithms on top of it. An example of this observation that I find particularly compelling is Speculative Paxos, which co-designs a consensus algorithm and the underlying network to improve overall performance.

At the risk of making unsubstantiated generalizations, I get the sense that theorists (who have dominated the field of distributed computing until somewhat recently) tend to worry a lot about corner cases that jeopardize correctness properties. That is, it’s the theorist who’s telling us to minimize our assumptions. In contrast, practitioners are often willing to sacrifice correctness in favor of simplicity and performance, as long as the corner cases that cause the system to violate correctness are sufficiently rare.

To resolve the tension between the theorists’ and the practitioners’ principles, my half-baked idea is that we should attempt to answer the following question: “How asynchronous are our networks in practice”?

Before outlining how one might answer this question, I need to provide a bit of background.

Failure Detectors

In reaction to the overly pessimistic asynchrony assumptions made by impossibility proofs, theorists spent about a decade [1] developing distributed algorithms for “partially synchronous” network models. The key property of the partially synchronous model is that at some point in the execution of the distributed system, the network will start to provide bounds on message delays, but the algorithm won’t know when that point occurs.

The problem with the partial asynchrony model is that algorithms built on top of it (and their corresponding correctness proofs) are messy: the timing assumptions of the algorithm are strewn throughout the code, and proving the algorithm correct requires you to pull those timing assumptions through the entire proof until you can finally check at the end whether they match up with the network model.

To make reasoning about asynchrony easier, a theorist named Sam Toueg along with a few others at Cornell proposed the concept of failure detectors. Failure detectors allow algorithms to encapsulate timing assumptions: instead of manually setting timers to detect failures, we design our algorithms to ask an oracle about the presence of failures [2]. To implement the oracle, we still use timers, but now we have all of our timing assumptions collected cleanly in one place.

Failure detectors form a hierarchy. The strongest failure detector has perfect accuracy (it never falsely accuses nodes of failing) and perfect completeness (it always informs all nodes of all failures). Weaker failure detectors might make mistakes, either by falsely accusing nodes of having crashed, or by neglecting to detect some failures. The different failure detectors correspond to different points on the asynchrony spectrum: perfect failure detectors can only be implemented in a fully synchronous network [3], whereas imperfect failure detectors correspond to partial synchrony.

Measuring Asynchrony

One way to get a handle on our question is to measure the behavior of failure detectors in practice. That is, one could implement imperfect failure detectors, place them in networks of different kinds, and measure how often they falsely accuse nodes of failing. If we have ground truth on when nodes actually fail in a controlled experiment, we can quantify how often those corner cases theorists are worried about come up.

Anyone interested in getting their hands dirty?


[1] Starting in 1988 and dwindling after 1996.

[2] Side note: failures detectors aren’t widely used in practice. Instead, most distributed systems use ad-hoc network timeouts strewn throughout the code. At best, distributed systems use adaptive timers, again strewn throughout the code. A library or language that encourages programmers to encapsulate timing assumptions and explicitly handle failure detection information could go a long way towards improving the simplicity, amenability to automated tools, and robustness of distributed systems.

[3] Which is equivalent to saying that they can’t be implemented. Unless you can ensure that the network itself never suffers from any failures or congestion, you can’t guarantee perfect synchrony. Nonetheless, some of the most recent network designs get us pretty close.

A typical web page is composed of multiple objects: HTML files, Javascript files, CSS files, images, etc..

When your browser loads a web page, it executes a list of tasks: first it needs to fetch the main HTML, then it can parse each of the HTML tags to know what other objects to fetch, then it can process each of the fetched objects and their effect on the DOM, and finally it can render pixels to your screen.

To load your web page as fast as possible, the browser tries to execute as many of these tasks as it can in parallel. The less time the browser spends sitting idle waiting for tasks to finish, the faster the web page will load.

It is not always possible to execute tasks in parallel. This is because some tasks have dependencies on others. The most obvious example is that the browser needs to fetch the main HTML before it can know what other objects to fetch [1].

In general, the more dependencies a web page has, the longer it will take to load. Prudent web developers structure their web pages in a way that minimizes browsers’ task dependencies.

A particularly nasty dependency is Javascript execution. Whenever the browser encounters a Javascript tag, it stops all other parsing and rendering tasks, waits to fetch the Javascript, executes it until completion, and finally restarts the previously blocked tasks. Browsers enforce this dependency because Javascript can modify the DOM; by modifying the DOM, Javascript might affect the execution of all other parsing and rendering tasks.

Placing Javascript tags in the beginning of an HTML page can have a huge performance hit, since each script adds 1 RTT plus computation time to the overall page load time.

Fortunately, the HTML standard provides a mechanism that allows developers to mitigate this cost: the defer attribute. The defer attribute tells the browser that it’s OK to fetch and execute a Javascript tag asynchronously.

Unfortunately, using the defer tag is not straightforward. The issue is that it’s hard for the web developer to know whether it’s safe to allow the browser to execute Javascript asynchronously. For instance, the Javascript may actually need to modify the DOM to ensure the correct execution of the page, or it may depend on other resources (e.g. other Javascript tags).

Forcing web developers to reason about these complicated (and often hidden!) dependencies is, at best, a lot to ask for, and at worst, highly error-prone. For this reason few web developers today make use of defer tags.

So here’s my half-baked idea: wouldn’t it be great if we had a compiler that could automatically mark defer attributes? Specifically, let’s apply static or dynamic analysis to infer when it’s safe for Javascript tags to execute asynchronously. Such a tool could go a long way towards improving the performance and correctness of the web.


[1] See the WProf paper for a nice overview of browser activity dependencies.

gdb, although an incredibly powerful tool for debugging single programs, doesn’t work so well for distributed systems.

The crucial difference between a single program and a distributed system is that distributed computation revolves around network messages. Distributed systems spend much of their time doing nothing more than waiting for network messages. When they receive a message, they perform computation, perhaps send out a few network messages of their own, and then return to their default state of waiting for more network messages.

Because there’s a network separating the nodes of the distributed system, you can’t (easily) pause all processes and attach gdb. And, in the words of Armon Dadgar, “even if you could, the network is part of your system. Definitely not going to be able to gdb attach to that.”

Suppose that you decide to attach gdb to a single process in the distributed system. Even then, you’ll probably end up frustrated. You’re going to spend most of your time waiting on a select or receive breakpoint. And when your breakpoint is triggered, you’ll find that most of the messages won’t be relevant for triggering your bug. You need to wait for a specific message, or even a specific sequence of messages, before you’ll be able to trace through the code path that leads to your bug.

Crucially, gdb doesn’t give you the ability to control network messages, yet network message are what drive the distributed system’s execution. In other words, gdb operates at a level of abstraction that is lower than what you want.

Distributed systems need a different kind of debugger. What we need is a debugger that will allow us to step through the distributed system’s execution at the level of network messages. That is, you should be able to generate messages, control the order in which they arrive, and observe how the distributed system reacts.

Shameless self-promotion: STS supports an “Interactive Mode” that takes over control of the (software) network separating the nodes of a distributed system. This allows you to interactively reorder or drop messages, inject failures, or check invariants. We need something like this for testing and debugging general distributed systems.

As a graduate student, I find that the rate of progress I’m able to make on my current research project is significantly lower than the rate at which I encounter ideas for new research projects. Over time, this means that the number of half-baked ideas jotted down in my notebook grows without bound.

In Academia, we sometimes feel dissuaded from sharing our half-baked ideas. Our fear is that we may get ‘scooped’; that is, we worry that if we share an idea before we have a time to flesh it out, someone else may take that idea and turn it into a fully-fledged publication, thereby stealing our opportunity to publish.

Until now, I haven’t publicly shared any of my half-baked ideas. I would like to change that [1].

So, in the hope of generating discussion, I’ll be posting a series of half-baked ideas. Please feel welcome to steal them, criticize them, or add to them!

[1] In part, this is because I have come to believe that academic caginess is petty. More importantly though, I have come to the terms with the reality that I will not have time to pursue most of these ideas.

At Berkeley I have the opportunity to work with some of the smartest undergrads around. One of the undergrads I work with, Andrew Or, did some neat work on modeling the performance of network control plane systems (e.g. SDN controllers). He decided to take a once-in-a-lifetime opportunity to join Databricks before we got the chance to publish his work, so in his stead I thought I’d share his work here.

An interactive version of his performance model can be found at this website. Description from the website:

A key latency metric for network control plane systems is convergence time: the duration between when a change occurs in a network and when the network has converged to an updated configuration that accommodates that change. The faster the convergence time, the better.

Convergence time depends on many variables: latencies between network devices, the number of network devices, the complexity of the replication mechanism used (if any) between controllers, storage latencies, etc. With so many variables it can be difficult to build an intuition for how the variables interact to determine overall convergence time.

The purpose of this tool is to help build that intuition. Based on analytic models of communication complexity for various replication and network update schemes, the tool quantifies convergence times for a given topology and workload. With it, you can answer questions such as “How far will my current approach scale while staying within my SLA?”, and “What is the convergence time of my network under a worst-case workload?”.

The tool is insightful (e.g. note the striking difference between SDN controllers and traditional routing protocols) and a lot of fun to play around with; I encourage you to check it out. In case you are curious about the details of the model or would like to suggest improvements, the code is available here. We also have a 6-page write up of the work, available upon request.

I often overhear a recurring debate amongst researchers: is Academia a good place to build real software systems? By “real”, we typically mean “used”, particularly by people outside of academic circles.

There have certainly been some success stories. BSD, LLVM, Xen, and Spark come to mind.

Nonetheless, some argue that these success stories came about at a time when the surrounding software ecosystem was nascent enough for a small group of researchers to be able to make a substantial contribution, and that the ecosystem is normally at a point where researchers cannot easily contribute. Consider for example that BSD was initially released in 1977, when very few open source operating systems existed. Now we have Linux, which has almost 1400 active developers.

Is this line of reasoning correct? Is the heyday of Academic systems software over? Will it ever come again?

Without a doubt, building real software systems requires substantial (wo)manpower; no matter how great the idea is, implementing it will require raw effort.

This fact suggests an indirect way to evaluate our question. Let’s assume that (i) any given software developer can only produce a fixed (constant) amount of coding progress in a fixed timeframe and (ii) the maturity of the surrounding software ecosystem is proportional to collective effort put into it. We can then approximate an answer to our question by looking at the number of software developers in industry vs. the number of researchers over time.

It turns out that the Bureau of Labor Statistics publishes exactly the data we need for the United States. Here’s what I found:

OES data

Hm. The first thing we notice is that it’s hard to even see the line for academic and industrial researchers. To give you a sense of where it’s at, the y-coordinate at May, 2013 for computer science teachers and professors is 35,770, two orders of magnitude smaller than the 3,339,440 total employees in the software industry at that time.

What we really care about though is the ratio of employees in industry to number of researchers:

OES ratio data

In the last few years, both the software industry and Academia are growing at roughly the same rate, whereas researchers in industrial labs appear to be dropping off relative to the software industry. We can see this relative growth rate better by normalizing the datasets (dividing each datapoint by the maximum datapoint in its series — might be better to take the derivative, but I’m too lazy to figure out how to do that at the moment):

OES normalized data

The data for the previous graphs only goes back to 1995. The Bureau of Labor Statistics also publishes coarser granularity going all the way to 1950 and beyond:

NES data

(See the hump around 2001?)

Not sure if this data actually answers our initial question, but I certainly found it insightful! If you’d like more details on how I did this analysis, or would like to play around with the data for yourself, see my code.

I recently came across a statement in Aphyr’s excellent Jepsen blog series that caught my eye:

“In a very real sense, [network] partitions are just really big windows of concurrency.”

This statement seems to imply that distributed systems are “equivalent” to parallel (single-machine) computing systems, for the following reason: partitions, which occur in a network but don’t really occur on a single chip [0], appear to be the key distinguishing property of distributed systems. But if partitions are just a special case of concurrency, then there shouldn’t be any fundamental reasons why algorithms for multicore computational models (such as PRAM) wouldn’t be perfectly suitable for solving all the problems we might encounter in a distributed setting. We know this to be false, so I’ve been trying to puzzle out precisely what properties of distributed computing distinguish it from parallel computing [1].

I’ve been taught that distributed systems have two crucial features:

  • Asynchrony, or “absence of synchrony”: messages from one process to another do not arrive immediately. In a fully asynchronous system, messages may be delayed for unbounded periods of time.
  • Partial failure: some processes in the system may fail while other processes continue executing.

Let’s discuss these two properties separately.


Parallel systems also exhibit asynchrony, as long it’s possible for there to be a delay between one process sending a message [2] and the other processes having the opportunity to read that message. Even on a single machine, this delay might be induced by locks within the operating system kernel, or by the cache coherence protocol implemented in hardware on a multicore chip.

With this in mind, let’s return to Aphyr’s statement. What exactly did he mean by “big windows of concurrency”? His article focuses on what happens when multiple clients write to the same database key, so by “concurrency” I think he is referring to situations where multiple processes might simultaneously issue writes to the same piece of state. But if you think about it, the entire execution is a “big window of concurrency” in this sense, regardless of whether the database replicas are partitioned. By “big windows of concurrency” I think Aphyr was really talking about asynchrony (or more precisely, periods of high message delivery delays), since network partitions are hard to deal with precisely because the messages between replicas aren’t deliverable until after the partition is recovered: when replicas can’t coordinate, it’s challenging (or impossible, if the system chooses to enforce linearizability) for them to correctly process those concurrent writes. Amending Aphyr’s statement then:

“Network partitions are just really big windows of asynchrony.”

Does this amendment resolve our quandary? Someone could rightly point out that because partitions don’t really occur within a single chip [0], parallel systems can effectively provide guarantees on how long message delays can last [3], whereas partitions in distributed systems may last arbitrarily long. Some algorithms designed for parallel computers might therefore break in a distributed setting, but I don’t think this is really the distinction we’re looking for.

Partial Failure

Designers of distributed algorithms codify their assumptions about the possible ways nodes can fail by specifying a ‘failure model’. Failure models might describe how many nodes can fail—for example, quorum-based algorithms assume that no more than N/2 nodes ever fail, otherwise they cannot make progress—or they might spell out how individual crashed nodes behave. The latter constraint forms a hierarchy, where weaker failure models (e.g. ‘fail-stop’, where crashed nodes are guaranteed to never send messages again) can be reduced to special cases of stronger models (e.g. ‘Byzantine’, where faulty nodes can behave arbitrarily, even possibly mimicking the behavior of correct nodes) [4].

Throughout the Jepsen series, Aphyr tests distributed systems by (i) telling clients to issue concurrent writes, (ii) inducing a network partition between database replicas, and (iii) recovering the partition. Observe that Jepsen never actually kills replicas! This failure model is actually weaker than fail-stop, since nodes are guaranteed to eventually resume sending messages [5]. Aphyr’s statement is beginning to make sense:

“Network partitions that are followed by network recovery are just really big windows of asynchrony.”

This statement is true; from the perspective of a node in the system, a network partition followed by a network recovery is indistinguishable from a random spike in message delays, or peer nodes that are just very slow to respond. In other words, a distributed system that guarantees that messages will eventually be deliverable to all nodes is equivalent to an asynchronous parallel system. But if any nodes in the distributed system actually fail, we’re no longer equivalent to a parallel system.

Who cares?

This discussion might sound like academic hairsplitting, but I claim that these distinctions have practical implications.

As an example, let’s imagine that you need to make a choice between shared memory versus message passing as the communication model for the shiny new distributed system you’re designing. If you come from a parallel computing background you would know that message passing is actually equivalent to shared memory, in the sense that you can use a message passing abstraction to implement shared memory, and vice versa. You might therefore conclude that you are free to choose whichever abstraction is more convenient or performant for your distributed system. If you jumped to this conclusion you might end up making your system more fragile without realizing it. Message passing is not equivalent to shared memory in distributed systems [6], precisely because distributed systems exhibit partial failures; in order to correctly implement shared memory in a distributed system it must always be possible to coordinate with a quorum, or otherwise be able to accurately detect which nodes have failed. Message passing does not have this limitation.

Another takeaway from this discussion is that Jepsen is actually testing a fairly weak failure mode. Despite Jepsen’s simplicity though, Aphyr has managed to uncover problems in an impressive number of distributed databases. If we want to uncover yet more implicit assumptions about how our systems behave, stronger failure modes seem like an excellent place to look.

[0] After I posted this blog post, Aphyr and others informed me that some of the latest multicore chips are in fact facing partial failures between cores due to voltage issues. This is quite interesting, because as multicore chips grow in transistor density, the distinction between parallel computing and distributed computing is becoming more and more blurred: modern multicore chips face both unbounded asynchrony (from the growing gap between levels of the memory hierarchy) and partial failure (from voltage issues).

[1] Thanks to Ali Ghodsi for helping me tease out the differences between these properties.

[2] or writing to shared memory, which is essentially the same as sending a message.

[3] See, for example, PRAM or BSP, which assume that every node can communicate with every other node within each “round”. It’s trivial to solve hard problems like consensus in this world, because you can always just take a majority vote and decide within two rounds.

[4] See Ali Ghodsi’s excellent slides for a taxonomy of these failure models.

[5] Note that this is not equivalent to ‘crash-recovery’. Crash-recovery is actually stronger than fail-stop, because nodes may recover or they may not.

[6] Nancy Lynch, “Distributed Algorithms”, Morgan Kaufmann, 1996.

According to a study by Turner et al. [1], wide area network links have an average of 1.2 to 2.7 days of downtime per year. This translates to roughly two and a half 9’s of reliability [2].

I was curious how this compared to datacenter links, so I took a look at Gill et. al’s paper [3] on datacenter network failures at Microsoft. Unfortunately some of the data has been redacted, but I was able to reverse engineer the mean link downtime per year with the help of Aurojit Panda’s svg-to-points converter. The results are interesting: out of all links types, the average downtime was 0.3 days. This translates to roughly three and a half 9’s of reliability, an order of magnitude greater than WAN links.

Intuitively this makes sense. WAN links are much more prone to drunken hunters, bulldozers, wild dogs, ships dropping anchor and the like than links within a secure datacenter.


[1] Daniel Turner, Kirill Levchenko, Alex C. Snoeren, and Stefan Savage. California Fault Lines: Understanding the Causes and Impact of Network Failures, Table 4. SIGCOMM ‘10.

[2] Note that this statistic is specifically about hardware failure, not overall network availability.

[3] Phillipa Gill, Navendu Jain, Nachiappan Nagappan. Understanding Network Failures in Data Centers: Measurement, Analysis, and Implications, Figures 8c & 9c. SIGCOMM ‘11

In 2010, Jeff Dean gave a talk that laid out a list of numbers every programmer should know. His list has since become relatively well known among the systems community.

The other day, a friend mentioned a latency number to me, and I realized that it was an order of magnitude smaller than what I had memorized from Jeff’s talk. The problem, of course, is that hardware performance increases exponentially! After some digging, I actually found that the numbers Jeff quotes are over a decade old [1].

Partly inspired by my officemate Aurojit Panda, who is collecting awesome data on hardware performance, I decided to write a little tool [2] to visualize Jeff’s numbers as a function of time [3].

Without further ado, here it is.


[1] Jeff’s numbers are from 2001, and were first publicized by Peter Norvig in this article.

[2] Layout stolen directly from ayshen on GitHub.

[3] The hardware trends I’ve gathered are rough estimates. If you want to tweak the parameters yourself, I’ve made it really easy to do so — please send me updates! Better yet, issue a pull request.

tl;dr: handling event ordering correctly in distributed systems is tricky. In this post I cover 7 approaches to coping with concurrency.

Robust distributed systems are notoriously difficult to build. The difficulty arises from two properties in particular:

  • Limited knowledge: each node knows its own state, and it knows what state the other nodes were in recently, but it can’t know their current state.

  • (Partial) failures: individual nodes can fail at any time, and the network can delay or drop messages arbitrarily.

Why are these properties difficult to grapple with? Suppose you’re writing code for a single node. You’re deep in a nested conditional statement, and you need to deal with a message arrival. How do you react? What if the message you’re seeing was actually delayed by the network and is no longer relevant? What if some of the nodes you need to coordinate with have failed, but you aren’t aware of it yet? The set of possible event sequences you need to reason about is huge, and it’s all too easy to forget about the one nasty corner case that will eventually bring your system to a screeching halt.

To make the discussion more concrete, let’s look at an example.

Floodlight bug

The figure above depicts a race condition [1] in Floodlight, a distributed controller for software-defined networks. With Floodlight, switches maintain one hot connection to a master controller and one or more cold connections to replica controllers. The master holds the authority to modify the configuration of the switches, while the other controllers are in slave mode and do not perform any changes to the switch configurations unless they detect that the master has crashed [2].

The race condition is triggered when a link fails (E1), and the switch attempts to notify the controllers (E2,E4) shortly after the master has died (E3), but before a new master has been selected (E6). In this case, all live controllers are in the slave role and will not take responsibility for updating the switch flow table (E5). At some point, heartbeat messages time out and one of the slaves elevates itself to the master role (E6). The new master will proceed to manage the switch, but without ever clearing the routing entries for the failed link (resulting in a persistent blackhole) [3].

If we take a step back, we see that there are two problems involved: leader election (“Who is the master at any point in time?”), and replication (“How should the backups behave?”). Let’s assume that leader election is handled by a separate consensus algorithm (e.g. Paxos), and focus our attention on replication.

Now that we have a concrete example to think about, let’s go over a few solutions this problem. The first four share the same philosophy: “get the ordering right”.

Take it case-by-case

The straightforward fix here is to add a conditional statement for this event ordering: if you’re a slave, and the next message is a link failure notification, store the notification in memory in case you become master later.

This fix seems easy in retrospect. But recall how the bug came about in the first place: the programmer had some set of event orderings in mind when writing the code, but didn’t implement one corner case. How do we know there isn’t another race condition lurking somewhere else in the code? [4]

The number of event orderings you need to consider in a distributed system is truly huge; it scales combinatorially with the number of nodes you’re communicating with. For the rest of this post, let’s see if we can avoid the need to reason on a case-by-case basis altogether.

Replicate the computation

Consider a system consisting of only one node. In this world, there is a single, global order (with no race conditions)!

How can we obtain a global event order, yet still achieve fault tolerance? One way [5] is to have the backup nodes mimic every step of the master node: forward all inputs to the master, have the master choose a serial order for those events, issue the appriopriate commands to the switches, and replicate the decision to the backups [6]. The key here is that each backup should execute the computation in the exact same order as the master.

For the Floodlight bug, the backup would still need to hold the link failure message in memory until it detects that the master has crashed. But we’ve gained a powerful guarantee over the previous approach: when the backup takes over for the master, it will be in a up-to-date state, and know exactly what commands it needs to send to the switches to get them into a correct configuration.

Make your event handlers transactional

Transactions allow us to make a group of operations appear either as if they happened simultaneously, or not at all. This is a powerful idea!

How could transactions help us here? Suppose we did the following: whenever a message arrives, find the event handler for that message, wrap it in a transaction, run the event handler, and hand the result of the transaction to the master controller. The master decides on a global order, checks whether any concurrent transactions conflict with each other (and aborts one of them if they do), updates the switches, sends the serialized transactions to the backups, and waits for ACKs before logging a commit message.

This is very similar to the previous solution, but it gives us two benefits over the previous approach:

  • We can potentially handle more events in parallel; most of the transactions will not conflict with each other, and we can simply abort and retry the ones that do.
  • We can now roll back operations. Suppose a network operator issues a policy change to the controller, but realizes that she made a mistake. No problem — she can simply roll back the previous transaction and start again where she began.

Compared to the first approach, this is a significant improvement! Each event is handled in isolation from the other events, so there’s need to reason about event interleavings; if a conflicting transaction was committed before we get to commit, just abort and retry!

Reorder events when no one will notice

It turns out that we can achieve even better throughput if we use a replication model called virtual synchrony. In short, virtual synchrony provides a library with three operations:

  • join() a process group
  • register() an event handler
  • send() an atomic multicast message to the rest of your process group.

These primitives provide two crucial guarentees:

  • Atomic multicast means that if any correct node gets the message, every live node will eventually get the message. That implies that if any live node ever gets the link failure notification, you can rest assure that one of your future masters will get it.
  • The join() protocol ensures that every node always know who’s a member of its group, and that everyone has the same view of who is alive and who is not. Failures results in a group change, but everyone will agree on the order in which the failure occured.

With virtual synchrony, we no longer need a single master; atomic multicast means that there is a single order of events observed by all members of the group, regardless of who initiated the message. And with multiple masters, we aren’t constrained by the speed of a single node.

The virtual part of virtual synchrony is that when the library detects that two operations are not causally related to each other, it can reorder them in whatever way it believes most efficient. Since those operations aren’t causally related, we’re guaranteed that the final output won’t be noticeably different.

OK, let’s move on to the final three approaches, which take a different tack than the first four: “avoid having to reason about event ordering altogether”

Make yourself stateless

In a database, the “ground truth” is stored on disk. In a network, the “ground truth” is stored in the routing tables of the switches themselves. This implies that the controllers’ view of the network is just soft state; we can always recover it simply by querying the switches for their current configuration!

How does this observation relate to the Floodlight bug? Suppose we didn’t even attempt to keep the backup controllers in sync with the master. Instead, just have them recompute the entire network configuration whenever they realize they need to take over for the master. Their only job in the meantime is to monitor the liveness of the master!

Of course, the tradeoff here is that it may take significantly longer for the newly elected master to get up to speed.

We can apply the same trick to avoid race conditions between concurrent events at the master: instead of maintaining locks between threads, just restart computation of the entire network configuration whenever a new event comes in. Race conditions don’t happen if there is no shared state!

Incidentally, Google’s wide-area network controller is almost entirely stateless, presumably for many of the same reasons.

Force yourself to be stateless

In the spirit stateless computation, why not write your code in a language that doesn’t allow you to keep state at all? Programs written in declarative languages such as Overlog have no explicit ordering whatsoever. Programmers simply declare rules such as “If the switch has a link failure, then flush the routing entries that go over that link”, and the language runtime handles the order in which the computation is carried out.

With a declarative language, as the long as the same set of events is fed to the controller (regardless of their order), the same result will come out. This makes replication really easy: send inputs to all controllers, have each node compute the resulting configuration, and only allow the master node to send out commands to the switches once the computation has completed. The tradeoff is that without an explicit ordering. the performance of declarative languages is difficult to reason about.

Guarantee self-stabilization

The previous solutions were designed to always guarantee correct behavior despite failures of the other nodes. This final solution, my personal favorite, is much more optimistic.

The idea behind self-stabilizing algorithms is to have a provable guarantee that no matter what configuration the system starts in, and no matter what failures occur, all nodes will eventually stabilize to a configuration where safety properties are met. This eliminates the need to worry about correct initialization, or detect whether the algorithm has terminated. As a nice side benefit, self-stabilizing algorithms are usually considerably simpler than their order-aware counterparts.

What do self-stabilizing algorithms look like? Self-stabilizing algorithms are actually everywhere in networking — routing algorithms are the most canonical example.

How would a self-stabilizing algorithm help with the Floodlight bug? The answer really depends on what network invariants the control application needs to maintain. If it’s just to provide connectivity [7], we could simply run a traditional link-state algorithm: have each switch periodically send port status messages to the controllers, have the controllers compute shortest paths using Dijkstra’s, and have the master push the appropriate updates to the switches. Even if there are transient failures, we’re guaranteed that the network will eventually converge to a configuration with no loops and deadends.

Ultimately, the best replication choice depends on your workload and network policies. In any case, I hope this post has convinced you that there’s more than one way to skin a cat!


[1] Note that this issue was originally discovered by the developers of Floodlight. (We don’t mean to pick on BigSwitch here; we chose this bug because it’s a great example of the difficulties that come up in distributed systems). For more information, see line 605 of Controller.java.

[2] This invariant is crucial to maintain. Think of the switches’ routing tables as shared variables between threads (controllers). We need to ensure mutual exclusion over those shared variables, otherwise we could end up with internally inconsistent routing tables.

[3] The Floodlight bug noted in [1] actually involves neglecting to clear the routing tables of newly connected switches, but the same flavor of race condition could occur for link failures. We chose to focus on link failures because they’re likely to occur much more often than switch connects.

[4] It’s possible in some cases to use a model checker to automatically find race conditions, but the runtime complexity is often intractable and very few systems do this in practice.

[5] There are actually a handful of ways to implement state machine replication. Ours depend on a concensus algorithm to choose the master, but you could also run the concensus algorithm itself to achieve replication. There are also cheaper algorithms such as reliable broadcast. You can also get significantly better read throughput with chain replication, which doesn’t require quorum for reads, but writes become more complicated.

[6] We still need to maintain the invariant that only the master modifies the the switch configurations. Nonetheless, with state machine replication the backup will always know what commands need to be sent to switches if and when it takes over for the master.

[7] Although if your goal is only to provide connectivity, it’s not clear why you’re using SDN in the first place.