Load Balanced Scalable Byzantine Agreement through Quorum Building, with Full Information

Valerie King, Steven Lonargan, Jared Saia, Amitabh Trehan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

22 Citations (Scopus)

Abstract

We address the problem of designing distributed algorithms for large scale networks that are robust to Byzantine faults. We consider a message passing, full information model: the adversary is malicious, controls a constant fraction of processors, and can view all messages in a round before sending out its own messages for that round. Furthermore, each bad processor may send an unlimited number of messages. The only constraint on the adversary is that it must choose its corrupt processors at the start, without knowledge of the processors’ private random bits.

A good quorum is a set of O(logn) processors, which contains a majority of good processors. In this paper, we give a synchronous algorithm which uses polylogarithmic time and Õ(vn) bits of communication per processor to bring all processors to agreement on a collection of n good quorums, solving Byzantine agreement as well. The collection is balanced in that no processor is in more than O(logn) quorums. This yields the first solution to Byzantine agreement which is both scalable and load-balanced in the full information model.

The technique which involves going from situation where slightly more than 1/2 fraction of processors are good and and agree on a short string with a constant fraction of random bits to a situation where all good processors agree on n good quorums can be done in a fully asynchronous model as well, providing an approach for extending the Byzantine agreement result to this model.

Original languageEnglish
Title of host publicationDistributed Computing and Networking
Subtitle of host publication12th International Conference, ICDCN 2011, Bangalore, India, January 2-5, 2011. Proceedings
PublisherSpringer
Pages203-214
Number of pages12
ISBN (Electronic)978-3-642-17679-1
ISBN (Print)978-3-642-17678-4
DOIs
Publication statusPublished - 2011
Event12th International Conference on Distributed Computing and Networking, ICDCN 2011 - Bangalore, India
Duration: 02 Jan 201105 Jan 2011

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Berlin Heidelberg
Volume6522
ISSN (Print)0302-9743

Conference

Conference12th International Conference on Distributed Computing and Networking, ICDCN 2011
CountryIndia
CityBangalore
Period02/01/201105/01/2011

Fingerprint

Message passing
Parallel algorithms
Communication

Cite this

King, V., Lonargan, S., Saia, J., & Trehan, A. (2011). Load Balanced Scalable Byzantine Agreement through Quorum Building, with Full Information. In Distributed Computing and Networking: 12th International Conference, ICDCN 2011, Bangalore, India, January 2-5, 2011. Proceedings (pp. 203-214). (Lecture Notes in Computer Science; Vol. 6522). Springer. https://doi.org/10.1007/978-3-642-17679-1_18
King, Valerie ; Lonargan, Steven ; Saia, Jared ; Trehan, Amitabh. / Load Balanced Scalable Byzantine Agreement through Quorum Building, with Full Information. Distributed Computing and Networking: 12th International Conference, ICDCN 2011, Bangalore, India, January 2-5, 2011. Proceedings. Springer, 2011. pp. 203-214 (Lecture Notes in Computer Science).
@inproceedings{571237052fef4de784dbf66006a43ff9,
title = "Load Balanced Scalable Byzantine Agreement through Quorum Building, with Full Information",
abstract = "We address the problem of designing distributed algorithms for large scale networks that are robust to Byzantine faults. We consider a message passing, full information model: the adversary is malicious, controls a constant fraction of processors, and can view all messages in a round before sending out its own messages for that round. Furthermore, each bad processor may send an unlimited number of messages. The only constraint on the adversary is that it must choose its corrupt processors at the start, without knowledge of the processors’ private random bits. A good quorum is a set of O(logn) processors, which contains a majority of good processors. In this paper, we give a synchronous algorithm which uses polylogarithmic time and {\~O}(vn) bits of communication per processor to bring all processors to agreement on a collection of n good quorums, solving Byzantine agreement as well. The collection is balanced in that no processor is in more than O(logn) quorums. This yields the first solution to Byzantine agreement which is both scalable and load-balanced in the full information model. The technique which involves going from situation where slightly more than 1/2 fraction of processors are good and and agree on a short string with a constant fraction of random bits to a situation where all good processors agree on n good quorums can be done in a fully asynchronous model as well, providing an approach for extending the Byzantine agreement result to this model.",
author = "Valerie King and Steven Lonargan and Jared Saia and Amitabh Trehan",
year = "2011",
doi = "10.1007/978-3-642-17679-1_18",
language = "English",
isbn = "978-3-642-17678-4",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "203--214",
booktitle = "Distributed Computing and Networking",

}

King, V, Lonargan, S, Saia, J & Trehan, A 2011, Load Balanced Scalable Byzantine Agreement through Quorum Building, with Full Information. in Distributed Computing and Networking: 12th International Conference, ICDCN 2011, Bangalore, India, January 2-5, 2011. Proceedings. Lecture Notes in Computer Science, vol. 6522, Springer, pp. 203-214, 12th International Conference on Distributed Computing and Networking, ICDCN 2011, Bangalore, India, 02/01/2011. https://doi.org/10.1007/978-3-642-17679-1_18

Load Balanced Scalable Byzantine Agreement through Quorum Building, with Full Information. / King, Valerie; Lonargan, Steven; Saia, Jared; Trehan, Amitabh.

Distributed Computing and Networking: 12th International Conference, ICDCN 2011, Bangalore, India, January 2-5, 2011. Proceedings. Springer, 2011. p. 203-214 (Lecture Notes in Computer Science; Vol. 6522).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Load Balanced Scalable Byzantine Agreement through Quorum Building, with Full Information

AU - King, Valerie

AU - Lonargan, Steven

AU - Saia, Jared

AU - Trehan, Amitabh

PY - 2011

Y1 - 2011

N2 - We address the problem of designing distributed algorithms for large scale networks that are robust to Byzantine faults. We consider a message passing, full information model: the adversary is malicious, controls a constant fraction of processors, and can view all messages in a round before sending out its own messages for that round. Furthermore, each bad processor may send an unlimited number of messages. The only constraint on the adversary is that it must choose its corrupt processors at the start, without knowledge of the processors’ private random bits. A good quorum is a set of O(logn) processors, which contains a majority of good processors. In this paper, we give a synchronous algorithm which uses polylogarithmic time and Õ(vn) bits of communication per processor to bring all processors to agreement on a collection of n good quorums, solving Byzantine agreement as well. The collection is balanced in that no processor is in more than O(logn) quorums. This yields the first solution to Byzantine agreement which is both scalable and load-balanced in the full information model. The technique which involves going from situation where slightly more than 1/2 fraction of processors are good and and agree on a short string with a constant fraction of random bits to a situation where all good processors agree on n good quorums can be done in a fully asynchronous model as well, providing an approach for extending the Byzantine agreement result to this model.

AB - We address the problem of designing distributed algorithms for large scale networks that are robust to Byzantine faults. We consider a message passing, full information model: the adversary is malicious, controls a constant fraction of processors, and can view all messages in a round before sending out its own messages for that round. Furthermore, each bad processor may send an unlimited number of messages. The only constraint on the adversary is that it must choose its corrupt processors at the start, without knowledge of the processors’ private random bits. A good quorum is a set of O(logn) processors, which contains a majority of good processors. In this paper, we give a synchronous algorithm which uses polylogarithmic time and Õ(vn) bits of communication per processor to bring all processors to agreement on a collection of n good quorums, solving Byzantine agreement as well. The collection is balanced in that no processor is in more than O(logn) quorums. This yields the first solution to Byzantine agreement which is both scalable and load-balanced in the full information model. The technique which involves going from situation where slightly more than 1/2 fraction of processors are good and and agree on a short string with a constant fraction of random bits to a situation where all good processors agree on n good quorums can be done in a fully asynchronous model as well, providing an approach for extending the Byzantine agreement result to this model.

U2 - 10.1007/978-3-642-17679-1_18

DO - 10.1007/978-3-642-17679-1_18

M3 - Conference contribution

SN - 978-3-642-17678-4

T3 - Lecture Notes in Computer Science

SP - 203

EP - 214

BT - Distributed Computing and Networking

PB - Springer

ER -

King V, Lonargan S, Saia J, Trehan A. Load Balanced Scalable Byzantine Agreement through Quorum Building, with Full Information. In Distributed Computing and Networking: 12th International Conference, ICDCN 2011, Bangalore, India, January 2-5, 2011. Proceedings. Springer. 2011. p. 203-214. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-642-17679-1_18