I’m no great fan of the ubiquity of the CAP theorem – it’s a solid impossibility result which appeals to the theorist in me, but it doesn’t capture every fundamental tension in a distributed system. For example: we make our systems distributed across more than one machine usually for reasons of performance and to eliminate a single point of failure. Neither of these motivations are captured verbatim by the CAP theorem. There’s more to designing distributed systems!

In this, I agree with Stonebraker; it’s the erroneous representation of ‘partition tolerance’ that I found very strange. I’ve been a good deal more forceful in private about this than I have in public

Summer of Code is a great program – providing stipends to students and more importantly connecting them with mentors in open source projects. ZooKeeper has a number of interesting projects to get started on.

ZooKeeper is a distributed coordination platform on which you can build the distributed equivalents of many traditional concurrent primitives like locks, queues and barriers. It’s heavily used in the real world – Yahoo! use it extensively, and many other major companies rely on it. The other committers and I are actively looking to increase participation in the project – there is loads of really interesting work left to do. If consensus protocols, distributed systems, scalability, fault-tolerance and performance are your thing, this is certainly the project for you.

If you have any questions at all, drop me a line at henry at apache dot org.

Real post with actual content coming in the next week or so!

The long reason was that I have now moved across the ocean, from Cambridge to San Francisco, where I am living in order that the commute to Cloudera be a little shorter than 24 hours. My possessions finally arrived on Thursday – over three months since we shipped them – and we are finally getting everything in order, including getting this blog back online. I’m now hosted at Bluehost, and have transferred all the old posts over to the new WordPress installation. I don’t yet have access to the images, so unfortunately those wil have to wait, but most other things are in order. Please excuse the dust as I find out which links are broken.

The old address – http://hnr.dnsalias.net/wordpress – will still work, but the correct link is now our very own domain: http://the-paper-trail.org/. Hopefully we will start showing up in Google again when the crawlers do their thing. Please update your rss readers – those of you who are still following and haven’t deleted my feed in disgust. Does anyone even still use rss readers anymore?

I am in the process of deciding what to write about for the next few posts. I still have the remainder of the theory of computation posts to write, which would be fun to do but is a bit of a departure from the systems focus. I never really fully explained Byzantine Fault Tolerance – at least, I never got as far as describing Zyzzyva and other modern systems. At the same time, some interesting stuff in systems research has happened since the blog went quiet – Google released the Go programming language which is intriguing for writing user-space systems software. SOSP 2009 happened, with some very cool papers which I really want to write about. And I’ve been busy myself – I was recently made a committer on the Apache ZooKeeper project, which is a distributed coordination system written by some engineers and researchers at Yahoo!, and is very cool. My largest contribution was a patch for ‘observers’ – which are listeners, in Paxos terminology – which help maintain the read performance of the cluster as the number of clients scales.

So, lots going on, plenty to write about, and some exciting possibilities coming down the queue. Good to be back.

What’s interesting is that the general sentiment seems to be that the concessions that GFS made for performance and simplicity (single master, loose consistency model) have turned out to probably be net bad decisions, although they probably weren’t at the time.

There are scaling issues with GFS – the well known many-small-files problem that also plagues HDFS, and a similar huge-files problem. Both increase the amount of metadata that a master has to maintain, and both therefore degrade performance due to some linear costs on metadata operations.

A replacement for GFS is in the works – a complete re-do, not just incremental updates to the design. This will involve, at least, a rethink of metadata storage and clearly a more fault-tolerant and scalable design. Multiple appenders, also a bugbear of HDFS, may be serialised through a single writer process, which would help the consistency issues.

“Our user base has definitely migrated from being a MapReduce-based world to more of an interactive world that relies on things such as BigTable. Gmail is an obvious example of that. Videos aren’t quite as bad where GFS is concerned because you get to stream data, meaning you can buffer. Still, trying to build an interactive database on top of a file system that was designed from the start to support more batch-oriented operations has certainly proved to be a pain point.”

One of those great articles where every paragraph is rich with insight. Worth reading, probably twice.

The best looking sessions to me are ‘scalability’ and ‘clusters’, but there’s at least one great looking title in every session. I’ll start posting some reviews once I find some bandwidth (and have finished the computation theory series – next one on its way).

Congratulations to all accepted authors!

One of the courses I do some teaching for is the dryly named ‘Theory of Computation’. Although such a course name is unlikely to pique a lot of interest, in actual fact it is probably the most fundamental and important course that you could take about computer science. Computation theory allows us to ask, and answer, questions about the limits of computers and the programs they execute. Is every problem solvable by a computer program? What do we even mean by a ‘problem’?

It turns out that there are profound and beautiful truths to be discovered when considering these questions. In a short series of articles, I’m going to give a brief introduction to the theory of computability, aimed at those who have never studied Turing machines, Cantor diagonalisation or Godel incompleteness. An appreciation for some of these ideas and results should give a perspective on what computers are, and are not, capable of.

This first article presents a bit of background material on the nature of infinity, which is right at the heart of computation theory. In the next article I’ll tie this in with the idea of computability and show how these ideas elegantly allow us to establish limits on what we can do with computers – even in theory, let alone practice.

Different Types of Infinity

A very important and fundamental question to computation theory is this: “how many unique computer programs are there?”

Although we’re not in a position to be precise about the details of such a question, we can at least give some thought to the kind of answers it might have. Are there just a finite number of computations – different executions with different results that a theoretical computer could perform?

It’s clear that this is unlikely. For example, we can conceive of a program that prints out a unique integer, and we can think of infinitely many programs that each print out a different integer. So it seems that there should be infinitely many programs, or computations. But let’s not be too hasty throwing that word ‘infinite’ around. What do we understand by infinity?

Let’s get one thing straight right away. We can’t say that ‘infinity’ is a quantity, or a number. We can’t add one to infinity. Infinity minus infinity is meaningless, not zero. Rather, infinity is a predicate on sets of things. If I describe to you a set, if we say that it does not contain a finite number of things then we say that the set has the property of being infinite. An infinite set is one that doesn’t have a number that we can call its size.

Bear with me a moment while I get pedantic. What does ‘size’ mean? What’s the size of a set? Obviously, the size of a set is the number of items in it. But how do we arrive at that number? We count the items, one by one. So what we do is give every item in the set a label in order ’1′, ’2′, ’3′… and so on until all the elements in the set have a label. The value of the last label that we assigned is what we call the size, or cardinality of a set. It’s the number of labels we need to uniquely label every element in the set. If a set is infinite, there is no finite number of labels that we can use to uniquely label every element. No matter what number of labels we use, there will always be elements (in fact, infinitely many of them) left over at the end that didn’t get a label. This is what infinite means. If we take a finite number of things out of an infinite set the set will never be empty, no matter how many we take out.

An example of an infinite set is the set of all words that are some number of As followed by the same number of Bs. For example, AB, AABB, AAABBB are all in the set. There are infinitely many words like this. How do we prove that a set is infinite? One way to do it is to take a set that we already know is infinite and show that for every element in our known set there is exactly one element in our candidate infinite set. This is similar to our labelling technique for finite sets – we take an infinite set and show that we can use it to label our candidate set. Since there are infinitely many labels from our infinite set, and we have shown that we need all of them to label our candidate set, we can conclude that our candidate set must itself be infinite, otherwise we would only need a finite number of labels to label it. By coming up with a labelling that uses every element of the infinite set, no matter what it is, we show that no finite labelling can exist.

So how do we apply this technique to our A…B… set? Well, we take a known infinite set, in our case the natural numbers and find a labelling. Here the labelling is easy to find. Let’s write every element of as where means ‘repeat times’. Then there is exactly one word in for every positive integer (negative values of don’t make a lot of sense). This makes it very easy to come up with a labelling from to . A word in has a label in . For every natural number, there is exactly one word. Therefore must be infinite!

This technique is the most useful when it comes to reasoning about the cardinality of various sets, and is hugely important when talking about computability. Computer scientists will call the act of finding a labelling establishing a bijection between and . A bijection is simply a precise word for a relationship that pairs elements of two sets together such that every element of each set has a unique partner in the other.

Now, we have taken as given that the set of integers is infinite, and no-one would argue with us. Is that the end of the story? Do all infinite sets have a bijection with the integers?

It turns out that the answer is no, not all infinite sets can be placed in correspondence with the integers. This result is extremely famous, and due to Georg Cantor, a man who spent much of his mathematical career looking into infinity and drove himself mad as a consequence.

‘Smaller’, But Still The Same Size

Let’s consider two different sets and challenge our intuitions about their size as compared to the integers. Firstly, consider the even integers. Is the set of even integers infinite? We would think so, because no matter what finite collection of them we can put together, we can always think of one that we’ve left out. This is a giveaway property of an infinite set. But at the same time, it seems like there should be fewer even integers than all the integers combined – intuitively we would expect there to be twice as many odd and even integers as just the even ones. But ‘twice as many’ is a murky concept when dealing with infinity, which as we discussed earlier doesn’t yield to normal arithmetic.

Indeed, an attempt to find a bijection between even integers and the whole set of integers turns up a correspondence pretty quickly. Recall that we can write every even integer in the form for all . This trivially gives us our bijection – label every even integer with the integer you get by dividing it by two. Conversely, every integer has a corresponding even integer that is the result of multiplying the integer by two. So 1 maps to 2, 7 maps to 14 and 316 maps to 632.

So it turns out that, completely counter-intuitively, there are as many integers as there are both even and odd integers! Infinity does not always behave as we expect. In particular it’s not sufficient to show that one set is a proper subset of another in order to demonstrate their different sizes when both sets are infinite.

Bigger Than Infinite?

I said earlier that there are infinite sets that are not of the same size as the integers. We’ve tried to find a set that was smaller, but had no luck. Let’s consider an apparently larger set and see where we get.

The real numbers are a good candidate. The real numbers are fairly complex to formally define, but we know that they include all the integers, as well as all the numbers with decimal expansions between the integers. Indeed, some real numbers have expansions that are infinitely long – a fact that will prove very important when we talk about the limits of Turing machines.

Is there a bijection between real numbers and integers? This is a tricky question, and required a genuine bit of ingenuity to resolve. The problem is that when a bijection is not obviously forthcoming (it’s hard to write each real number in terms of a single integer) we have to look in the other direction and prove that there is no such bijection. This is a good deal harder – a positive proof just requires us to come up with a single exemplar, whereas a negative proof has to be valid for every single possible bijection!

Cantor’s attack on the negative proof went as follows. Imagine there is such a bijection. Then we could conceive of a list with all the real numbers in order, as labelled by their integer counterparts. So at the top would be real number 1, followed by real number 2 and so on. Obviously, the list would be infinite so we couldn’t write it down. That’s no problem, we just have to imagine it.

Note at this point how the list doesn’t depend at all on the nature of the bijection itself – no matter what the bijection is, we can construct this list. This generality is crucial for easily dismissing the entire set of bijections at once.

The next step is the neat one. If this list was a bijection, it would contain every single real number. So if we could come up with some real number that wasn’t in the list, we would show that it was not a bijection. Cantor’s great insight was to see that there is a way to construct such a real number by showing that it could not be equal to any real number in the list.

Cantor imagined the list of real numbers as a table, with the rows being real numbers, and the columns being the individual digits of each real number. So the 3rd column would contain the 3rd digits of every real number. Therefore we can identify the digit from the real number by talking about the digit .

To keep the presentation straightforward, we’re going to consider only the real numbers between 0 and 1 – if there are more of even these kinds of number than real numbers, we’ll still have established the result.

		Digit 1	Digit 2	Digit 3	Digit 4	…
	0.	7	3	9	4	…
	0.	9	3	2	8	…
	0.	4	2	9	8	…
…

This table is the first few rows of an example bijection.

Now the key observation here is that, for a real number to be different from it is enough for to differ from at just one digit. That is, as long as there exists a for which then .

So to find a real number that is not in the list, we just have to find a way to construct one that is different from every real number in the list at at least one digit.

Obviously it’s no good just changing a single digit – say we set the 3rd digit of our real number to 7 – because it’s guaranteed that there are some real numbers whose 3rd digit is 7 and we don’t know whether or not the rest of our real number matches them.

However, just as there are an infinite number of real numbers in our list, there are infinitely many columns in our table – so infinitely many digits to play with. So if we just make sure that each digit is different from its counterpart in one real number each, that will be sufficient because there are enough digits to go around. We will construct a real number so that each digit of is different from digit of the real number in the list, and that is different for all .

There are two challenges here. The first is to come up with a method that lets us always pick a digit that is different. The second is to come up with a mapping – in fact, another bijection – between the columns and the rows so that every digit in our constructed real number is responsible for being different from exactly one real number in the table.

Both challenges are easily resolved. If the digit we wish to be different from is , then it’s simple to construct by adding one to (and if is 9, wrapping around to 0).

We can also neatly deal with the second challenge. In our constructed real number , we’ll give digit the responsibility of being different from the 1st real number in the list, at digit . Similarly for . And so on. Every digit of causes it to be different from a unique real number in the list. By combining all these digits together, we get a new, infinitely long real number that is different from every single listed real number.

		Digit 1	Digit 2	Digit 3	Digit 4	…
	0.	7	3	9	4	…
	0.	9	3	2	8	…
	0.	4	2	9	8	…
…

In the case of our example bijection, we would have the beginnings of as 0.840… – different from 0.7394… at digit 1, different from 0.9328… at digit 2 and different from 0.4298… at digit 3. Different from every real number in the table!

This concludes the proof. What we have shown is that there is no bijection between the real numbers and the integers. No matter what the bijection, we can come up with some real number that’s not been included. Therefore we can conclude that there are more real numbers than integers.

The shape that the ‘differing digits’ make in the table of real numbers moves along the diagonal. This is why this is called ‘Cantor’s diagonal proof’. In actual fact, the diagonal pattern is just one of infinitely many bijections we could have come up with. It is the simplest, and the easiest to understand.

Two Kinds of Infinity

So this leads us to the strange idea that there are two different kinds of infinity. The first kind of infinite sets, like the integers, are called countably infinite to emphasise the idea that they can be placed in one-to-one correspondence with the integers, an action that we cal ‘counting’. The second kind of infinite sets that we have discovered, like the real numbers, are called uncountably infinite by way of contrast. Uncountably infinite sets are unimaginably more vast than countable ones. Between any two real numbers, there are uncountably infinite intermediate real numbers – more than there are integers. There are more real numbers between 0 and 1 than there are integers.

This contrast will play a significant role in the development of a theory of computation. We will be able to identify the number of possible computations with a countably infinite set, and therefore describe, using our established language of infinity, computations that our best efforts cannot perform, not even with all the resources in the world.

A small conciliatory nugget that regular readers of this blog might find interesting: a trademark Robinson monster post on Cloudera’s blog describing how to build a simple distributed queue with Apache ZooKeeper.

More on ZooKeeper and our usual distributed systems programming to follow.

Hadoop is Cloudera’s business. Hadoop is an open-source implementation of Google’s MapReduce Cloudera provides support for Hadoop, and their own fully supported distribution of the Hadoop toolset. Hadoop allows very large scale distributed and parallel processing of huge data sets in a fault-tolerant and efficient manner. Data sets are getting bigger all the time, and there’s a mismatch now between the desire and the ability of companies to handle and process all those data. Cloud computing, at least in the form of dynamic provision of computing resources, and distributed processing technologies such as Hadoop are helping to make this problem tractable. Cloudera provides the expertise and the experience to help businesses make best use of this seriously powerful tech.

I’m joining, as you might expect, as a distributed systems engineer. There are plenty of interesting problems to attack, both in Hadoop and the ecosystem of technologies that support and extend it, such as HDFS, Hbase, Pig, Hive and ZooKeeper. Cloudera already has a killer team (see some of the press from the New York Times), and I’m really looking forward to being a part of it.

Professor Liskov seems to be particularly well known for the Liskov substitution principle which says that some property of a supertype ought to hold of its subtypes. I’m not in any position to speak as to the importance of this contribution. However, her more recent work has been regarding the tolerance of Byzantine failures in distributed systems, which is much more close to my heart.

The only work of Liskov’s that I am really familiar with is the late 90s work on Practical Byzantine Fault Tolerance with Miguel Castro and is first published in this OSDI ’99 paper. I’m not going to do a full review, but the topic sits so nicely with my recent focus on consensus protocols that it makes sense to briefly discuss its importance.

Towards Byzantium

Remember that in the articles on Paxos, we were able to deal with two kinds of failure: fail-stop and fail-recover. Although these two failure modes capture a lot of the possible failures in a distributed system there is a yet more general failure mode which captures all possible kinds of errors. Byzantine failures occur when a participant in a protocol deviates arbitrarily from the specified protocol, and thus cannot be relied upon to do anything useful. Worse than that, Byzantine nodes may often look like they are non-faulty up until a crucial point where they might, for example, lie about the result of a transaction, or send two different responses to identical requests, or simply fail to respond. Although Byzantine failures are often equated with malicious attacks, where an attacker has gained control of a node and is controlling its behaviour, in fact many Byzantine failures occur due to programming errors in the implementation of a protocol (Amazon were susceptible to a Byzantine failure recently when a bit-flip caused a gossipped message to be incorrectly propogated, taking down S3 for hours).

As we’ve talked about elsewhere on this blog, consensus is a hugely important primitive for distributed algorithms. When Byzantine failures come into the picture consensus takes even more of the centre stage. Every action that a replica is instructed to perform has to be validated by every fault-free replica because there’s a strong possibility that the coordinator is itself faulty and has told different nodes to do different things. So nodes must run a consensus protocol to agree on what they were asked to do, let alone the result of doing it.

Of course, standard consensus algorithms won’t do as they themselves are not Byzantine fault tolerant. So building Byzantine fault tolerant systems is often reduced to building a Byzantine fault tolerant consensus primitive, and using that to build replicated state machines in the usual style.

When we talk about BFT consensus we often distinguish a co-ordinator node responsible for initiating the consensus protocol and proposing the initial value, which is usually received from an external client. The other nodes are replicas, as normal. There’s nothing particularly special about the co-ordinator, as it still functions like a replica for the rest of the protocol. However, we can show that if the co-ordinator is definitely not faulty then we can execute a more relaxed protocol; more on this later.

BFT consensus has similar requirements to standard consensus: validity, which is that only a proposed value can be decided upon, termination and agreement. Agreement says that all correct nodes must agree upon the same value – this is the same as for standard consensus, but the definition of faulty here is widened to include Byzantine faults. Validity also requires a small relaxation – if the co-ordinator is faulty then we allow correct nodes to agree upon some default ‘no-op’ value. This is because if the co-ordinator is faulty it’s impossible to tell what the original request from the client was, and so the safe action is to do nothing. If the co-ordinator is non-faulty, then validity is required as normal. This of course implies that correct replicas must be able to detect a faulty co-ordinator.

How might faults appear in an instance of Byzantine consensus? There are the standard failure modes that we know about – messages might take a long time to be processed, due to a fail-recover fault, or replicas might crash. More perniciously, replicas might falsify messages to other replicas. The co-ordinator might tell half the replicas that value A has been proposed, and half the replicas that value B was. Faulty replicas in either half might then lie to other replicas about the value that it received from the co-ordinator. The task of a Byzantine fault-tolerant consensus algorithm is to figure out if the co-ordinator is non-faulty, and if so what values it sent to the good replicas. This is a difficult problem – how, with no a priori notion of trust, do you tell who is lying?

Leslie Lamport, along with Shostak and Pease, wrote the seminal paper on the subject of BFT. Indeed, they introduced the metaphor of the ‘Byzantine Generals’, deciding whether to attack or retreat from their distributed camp sites in the presence of potential traitors, and therefore misinformation.

Their paper set out two important results. The first is the most well known: that to tolerate completely arbitrary Byzantine failures in a network where Byzantine replicas may lie not only about their own state, but what they have heard from other replicas, at least nodes total are required to tolerate faults.

This is an extremely famous result, and one that is quoted time and time again in the literature – often without a full understanding of why it holds and in what conditions. The proof itself will be the subject of a later post, but the intuition comes from considering the case when . In order to reach agreement with three nodes, it can be seen very easily that every replica must send every other replica a message containing the proposal it got from the co-ordinator. If only the co-ordinator could be faulty then the replicas can figure this out very quickly as, when they compare notes, they will see that both received different proposals. However, if one of the replicas could be faulty then the good replica will still see the same message from the faulty replica: both values that they claim to have received from the co-ordinator are different. Since the good replica can’t distinguish this situation from when the co-ordinator is faulty, it can’t decide who to believe and therefore can’t decide consistently. The paper then goes on to show that any purported solution which uses fewer than replicas could be used to solve the three-replica, one fault case. Therefore, any correct solution must involve replicas or more. The paper gives one such solution.

The second result is that, if nodes may sign their messages to other nodes in a non-forgeable way so that Byzantine nodes cannot lie about what they have heard, there is an algorithm for Byzantine consensus in a synchronous network that tolerates failures. This is dramatically better than the bound, but comes at the cost of an expensive protocol in terms of the number of rounds needed to execute.

It’s difficult to overestimate how influential this paper has been. All subsequent BFT papers that I’ve read (quite a few!) have characterised their solutions similarly, in terms of the fraction of faulty replicas that their algorithm will tolerate. The idea of having replicas sign their messages, so that other replicas could not lie about what they had heard is highly practical given the advent of public-key cryptography, and clearly greatly strengthens the system.

But Lamport’s paper only dealt with synchronous signed-message networks. What about asynchronous ones? Treatment of these had to wait until a few years later for a paper by Bracha and Toueg. They showed that, even if replicas could not forge responses from other replicas, there was still a fundamental lower bound on the number of replicas. The proof was by construction of an arrangement of replicas such that correct replicas couldn’t decide between good and bad responses under two different, but identical from the perspective of correct replicas, executions.

The intuition behind this result is that each correct replica must hear from other replicas in the worst case, so that the faulty replicas that may be lying about the proposed value that they heard can be outvoted. So the number of replicas must be at least .

At the same time, a replica can only wait to hear from at most replicas (where is the total number of replicas). Why? Because in an asynchronous system it’s possible either that a) replicas are faulty and have failed to reply or b) replicas are not faulty, but haven’t replied yet. A correct replica can’t distinguish between these cases, and so can’t wait for an unbounded amount of time to get all replies, which might never be forthcoming. If the network were synchronous, a good replica could detect that the replicas that had failed to reply must be faulty, which means that the replies it had already received were all from the other correct replicas. In an asynchronous network, this is not possible.

Therefore we have that , or that .

Practical Byzantine Fault Tolerance

Miguel Castro and Professor Liskov had a 1999 OSDI paper called Practical Byzantine Fault Tolerance. Their contribution was to develop a Byzantine fault tolerant consensus protocol that was both efficient and applicable to realistic scenarios.

Liskov and Castro were the first to propose a correct algorithm that worked efficiently in asynchronous networks, and that realised the lower bound. FLP impossibility tells us that consensus is in general impossible to solve in asynchronous networks with even just fail-stop failures, rather than the more general Byzantine failures, so Liskov and Castro’s PBFT took a similar approach to Paxos and guaranteed liveness only when the network was synchronous. During periods of asynchrony PBFT may not terminate, but will never violate its safety properties (which are, as ever, validity and agreement).

PBFT’s other advantages were its high performance – owing in part to the use of the more efficient Message Authentication Codes rather than public-key cryptography for fast message signing – and its ability to tolerate an unbounded number of faults over the lifetime of execution, as long as no more than were concurrent. PBFT provides the familiar state-machine abstract interface, with a primary through which requests go that proposes a sequence number for every operation. The correct replicas agree (via Byzantine consensus) on the sequence number, and then commit the requests in sequence order.

The protocol itself is reasonably simple, but I’m not going to describe it in detail here as that would require a lot of groundwork to prove some basic results and show why it’s correct: this will be the subject of a future series of posts, as there’s a lot of interesting work in BFT still being done. The basic idea of PBFT is to have the primary broadcast a request to all replicas, which then retransmit what they have heard to every other replica. If all replicas agree on the same operation, then the primary is currently correct, and the replicas broadcast a commit message to each other, much like a standard three-phase commit protocol. In fact, replicas will proceed once they have got identical replies in the first phase, which is a Byzantine quorum, any two of which will be guaranteed to contain at least one correct replica in common. The idea is to ensure that the primary can’t have two conflicting sequence numbers for a single request accepted (since this would require a correct replica to accept both, which it will not do).

If, however, the primary turns out to be faulty, then a view-change protocol has to be executed, which causes all replicas to stop taking requests from the primary, and elect a new one in its stead. Getting this protocol right involves taking checkpoints of mutually agreed upon histories, since a view-change might occur during a request, then agreeing on the new leader and restarting any pending requests. All the while making sure that faulty replicas can’t hijack the process.

If you’re interested, the best paper is not the OSDI one, but the one in Transactions on Computer Systems, which is a longer paper and an easier read.

PBFT has since been update by a variety of different work, but the main structure of the protocol has yet to be fundamentally improved upon. There is still some distance to go before Byzantine fault tolerance techniques habitually make their way into production systems – there’s still increased complexity, cost and performance issues to worry about – but when they do, PBFT will doubtless have been a tremendously important step in the right direction.