Filed under: Uncategorized | Tags: Byzantine agreement, resource competitive, security, theory
I recently gave a talk at DISC on our paper Secure and Scalable Computation Among Strangers. Short abstract below:
“The last decade has seen substantial progress on designing Byzantine agreement algorithms that do not require all-to-all communication. However, these protocols do require each node to play a particular role determined by its ID. Motivated by the rise of permissionless systems such as Bitcoin, where nodes can join and leave at will, we extend this research to a more practical model, where initially, each node does not know the identity of its neighbors. In particular, a node can send to new destinations only by sending to random (or arbitrary) nodes, or responding to messages received from those destinations.
We assume a synchronous and fully-connected network, with a full-information, but static Byzantine adversary. A major drawback of existing Byzantine protocols in this setting is that they have at least n^2 message complexity, where n is the total number of nodes. In particular, the communication cost incurred by the honest nodes n^2, even when Byzantine node send no messages. In this paper, we design protocols for fundamental problems which are message-competitive, i.e., the total number of bits sent by honest nodes is not significantly more than the total sent by Byzantine nodes. We describe a message-competitive algorithm to solve Byzantine agreement, leader election, and committee election. Our algorithm sends an expected O((T+n) log n) bits and has latency O(polylog(n))(even in the CONGEST model), where T=O(n^2) is the number of bits sent by Byzantine nodes.”
Filed under: Uncategorized | Tags: Byzantine agreement, spectral analysis, theory
I gave a talk last week at SOFSEM 2015. The talk covers some of our recent work that uses spectral analysis to solve a classic Byzantine agreement problem. Here are the slides.
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.“
Many other articles give details of the theoretical aspects of bitcoin (the second with quotes from distributed computing luminaries like Jim Aspnes and Nancy Lynch). [1]
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.
[1] 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:
Byzantine Agreement in Polynomial Expected Time
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.
Filed under: Uncategorized | Tags: algorithms, Byzantine agreement, theory
The September SIGACT distributed computing column is now available at Technion and at MIT. This month Valerie and I contributed a survey on scalable Byzantine Agreement – Marko Vukolic considers BA for cloud computing providers. Idit’s intro to the column is below.
“After almost 30 years of research on Byzantine Agreement (BA), the problem continues to be relevant and to re-invent itself in new ways. This column discusses two new research directions that further push the scale of BA. It suggests new domains where BA can, and perhaps should, be deployed. First, our main contribution, by Valerie King and Jared Saia, argues for running BA in setting with a large number of nodes (or processors). Valerie and Jared survey new BA protocols whose communication complexity is scalable in the number of participating processors. This, they argue, enables their deployment in larger-scale domains for which BA was considered infeasible before. The second contribution, by Marko Vukolic, considers another emerging domain for BA. It calls for wider-scale deployment of BA protocols, not among many processors, but rather over multiple cloud computing providers.
The column ends with a short announcement about Morgan Claypool’s new monograph series on Distributed Computing Theory, edited by Nancy Lynch.
Many thanks to Valerie, Jared, and Marko for sharing their insights!”
Filed under: Uncategorized | Tags: algorithms, Byzantine agreement, conferences, distributed computing, PODC, theory
The end of the semester here at UNM just about killed me. In addition to the usual academic hubbub, I hosted a visitor, submitted a paper, finished up the camera ready for our PODC paper, and dealt with my toddler who decided it would be a good couple of weeks to wake up every night at 2am (teething?, headache?, likes a dose of cherry-flavored children’s tylenol as a nightcap?)
The camera-ready of our paper, “Breaking the O(n^2) Bit Barrier: Scalable Byzantine agreement with an Adaptive Adversary” (that I blogged about previously) is now available here. This was probably the most time I’ve spent going from an accepted paper to a camera ready – mostly because the algorithm in the paper consisted of several small parts with many connections between the parts. Hopefully, our new version makes everything much easier to understand.
Some great news we received, right after submitting the camera ready, is that our paper was selected to be in the “best paper session” of PODC. The list of all such papers is below – I know that at least some of these papers will be invited to a special issue of the JACM, and all of them look interesting. The best paper session is a new thing for PODC. I definitely like the idea of having multiple best papers, it gives more information about the assessment of the PC than a single best paper. I’ll probably read through most of these before the conference.
Deterministic Distributed Vertex Coloring in Polylogarithmic Time
Barenboim, Elkin
Breaking the O(n^2) Bit Barrier: Scalable Byzantine agreement with an Adaptive Adversary
King, Saia
Optimal Gradient Clock Synchronization in Dynamic Networks
Lenzen, Kuhn, Locher, Oshman
Online set packing and competitive scheduling of multi-part tasks
Emek, Halldorsson, Mansour, Patt-Shamir, Radhakrishnan, Rawitz
How to Meet when you Forget: Log-space Rendezvous in Arbitrary Graphs
Czyzowicz, Kosowski, Pelc
A Modular Approach to Shared-memory Consensus, with Applications to the Probabilistic-write Model
Aspnes
Constant RMR Solutions to Reader Writer Synchronization
Bhatt, Jayanti
Machinations 