Computer Science – Distributed – Parallel – and Cluster Computing
Scientific paper
2010-02-24
Computer Science
Distributed, Parallel, and Cluster Computing
Scientific paper
We describe an algorithm for Byzantine agreement that is scalable in the sense that each processor sends only $\tilde{O}(\sqrt{n})$ bits, where $n$ is the total number of processors. Our algorithm succeeds with high probability against an \emph{adaptive adversary}, which can take over processors at any time during the protocol, up to the point of taking over arbitrarily close to a 1/3 fraction. We assume synchronous communication but a \emph{rushing} adversary. Moreover, our algorithm works in the presence of flooding: processors controlled by the adversary can send out any number of messages. We assume the existence of private channels between all pairs of processors but make no other cryptographic assumptions. Finally, our algorithm has latency that is polylogarithmic in $n$. To the best of our knowledge, ours is the first algorithm to solve Byzantine agreement against an adaptive adversary, while requiring $o(n^{2})$ total bits of communication.
King Valerie
Saia Jared
No associations
LandOfFree
Breaking the O(n^2) Bit Barrier: Scalable Byzantine agreement with an Adaptive Adversary does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Breaking the O(n^2) Bit Barrier: Scalable Byzantine agreement with an Adaptive Adversary, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Breaking the O(n^2) Bit Barrier: Scalable Byzantine agreement with an Adaptive Adversary will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-260849