Filed under: Uncategorized | Tags: Byzantine agreement, spectral analysis, theory
Last month, Marc Andreessen wrote a thought-provoking article on bitcoin for the New York Times. Interestingly, early in the article he mentions Byzantine agreement (albeit by the more colorful name of the Byzantine Generals Problem):
“Bitcoin is the first practical solution to a longstanding problem in computer science called the Byzantine Generals Problem. To quote from the original paper defining the B.G.P.: “[Imagine] a group of generals of the Byzantine army camped with their troops around an enemy city. Communicating only by messenger, the generals must agree upon a common battle plan. However, one or more of them may be traitors who will try to confuse the others. The problem is to find an algorithm to ensure that the loyal generals will reach agreement.“
When Marc Andreessen mentions Byzantine agreement in the New York Times, it gets my attention. I’m far from an expert on bitcoin, but from what I can tell, the system is faced with a Byzantine agreement (BA) problem when maintaining logs of currency transactions. This BA problem occurs over a huge network, so a solution that uses all-to-all communication is infeasible. To circumvent this, bitcoin uses an algorithm that trades off computation for communication.
In particular, bitcoin’s algorithm for BA uses proof-of-work. Instead of each node sending out a vote, only those nodes that are able to solve a computational puzzle send out their votes. If the puzzle is hard enough, only a small number of nodes send out votes and communication is low. Of course, each vote contains a small proof that the node solved an instance of the puzzle. This approach works provided that the computational effort exerted by the “good” nodes is twice the computational effort exerted by the bad nodes.
However, there are two issues with using proof-of-work. One is ensuring there is an incentive for the good nodes to work to solve a large fraction of the puzzles. Bitcoin uses a clever approach: reward users that solve puzzles with their own bitcoins. However, this is very application-specific, and it’s unclear if bitcoin’s BA algorithm would work for other systems where there is no obvious way to incentivize computational work.
Second, proof-of-work wastes computational resources. Arguably, many BA algorithms waste communication resources, so maybe this is a fair tradeoff. However, one has to wonder if there is a more efficient way to tolerate bad nodes. In particular, it’d be nice to have a scheme where the computation done by the good nodes is some function of the computation done by the bad nodes. One could hopefully show this via something like resource competitive analysis. Resolving whether or not this is possible is I think one of the more interesting research problems related to bitcoin’s approach to Byzantine agreement.
 See also this rebuttal to Andresseen’s article
Filed under: Uncategorized | Tags: Byzantine agreement, spectral, theory
Accepted papers for SODA 2014 are now published. Valerie King and I have a paper there on Faster Agreement via a Spectral Method for Detecting Malicious Behavior. This is one of the first papers that I know of that uses a spectral approach to solve a problem in reliable distributed computing. Slides from an early talk on the research in this paper are available on my web page.
Just getting back from a great visit to Ann Arbor to work with Maxwell Young, Seth Pettie and Valerie King. Perhaps the most important discovery at Ann Arbor for several of us was the existence of sour beer.
I also gave a talk on our polynomial time Byzantine agreement result. The talk went well with many questions and ideas. Unfortunately, though it seems like an hour is the bare minimum to convey the problem and ideas of our algorithm – kind of worried about what to do in 20 minutes at STOC.
Talk slides are now up on my web page. Comments welcome!
Filed under: Uncategorized | Tags: Byzantine agreement, distributed computing, theory
I just put up a paper from Val and I that will appear in this upcoming STOC. The paper is:
It gives the first expected polynomial time algorithm for Byzantine agreement as it was originally posed: adaptive adversary, full-information model, with asynchronous communication. It’s something that we’ve both been working on for many years.
Congratulations to my student Olumuyiwa (“M”) Oluwasanmi who successfully defended his dissertation on “Practical, Scalable Algorithms for Byzantine agreement” last week!
Usually on this blog, I allow only a 1 slide dissertation summary, but today I’m making an exception for 2 slides (at least they have the same x-axis :). The slides below summarize the performance of 4 Byzantine agreement algorithms. The CKS algorithm is from the paper “Random oracles in Constantinople: Practical asynchronous Byzantine agreement using cryptography“. The remaining 3 algorithms are from M’s dissertation, and the algorithms with the RB prefix assume the existence of a random beacon.
Filed under: Uncategorized | Tags: Byzantine agreement, distributed computing, grants, theory
The process of grant writing was completely opaque to me when I was a grad student. As a faculty member, I now take the position that grant writing is intrinsically important, and that all grad students should learn something about it in order to get insight into the long-term planning process for doing research. For this reason, it’d be nice to see more examples of funded grants publicly available.
Last January, I posted a one page project summary for one of my funded NSF proposals. This year again I was lucky enough to have a proposal funded and I’m posting the one page summary below. I hope that some readers find it useful.