TY - GEN
T1 - Fast Byzantine leader election in dynamic networks
AU - Augustine, John
AU - Pandurangan, Gopal
AU - Robinson, Peter
N1 - Funding Information:
Peter Robinson was partly supported by the European Community’s Seventh Framework Programme (FP7/2007-2013) under the ASAP project, grant agreement no. 619706.
Funding Information:
Gopal Pandurangan was supported in part by NSF grant CCF-1527867.
Funding Information:
John Augustine was supported by IIT Madras New Faculty Seed Grant, IIT Madras Exploratory Research Project, and Indo-German Max Planck Center for Computer Science (IMPECS).
Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2015.
PY - 2015
Y1 - 2015
N2 - We study the fundamental Byzantine leader election problem in dynamic networks where the topology can change from round to round and nodes can also experience heavy churn (i.e., nodes can join and leave the network continuously over time). We assume the full information model where the Byzantine nodes have complete knowledge about the entire state of the network at every round (including random choices made by all the nodes), have unbounded computational power and can deviate arbitrarily from the protocol. The churn is controlled by an adversary that has complete knowledge and control over which nodes join and leave and at what times and also may rewire the topology in every round and has unlimited computational power, but is oblivious to the random choices made by the algorithm. Our main contribution is an O(log3 n) round algorithm that achieves Byzantine leader election under the presence of up to O(n1/2-ε) Byzantine nodes (for a small constant ε > 0) and a churn of up to O(√n/ polylog(n)) nodes per round (where n is the stable network size). The algorithm elects a leader with probability at least 1 - n-Ω(1) and guarantees that it is an honest node with probability at least 1-n-Ω(1); assuming the algorithm succeeds, the leader’s identity will be known to a 1-o(1) fraction of the honest nodes. Our algorithm is fully-distributed, lightweight, and is simple to implement. It is also scalable, as it runs in polylogarithmic (in n) time and requires nodes to send and receive messages of only polylogarithmic size per round. To the best of our knowledge, our algorithm is the first scalable solution for Byzantine leader election in a dynamic network with a high rate of churn; our protocol can also be used to solve Byzantine agreement in a straightforward way. We also show how to implement an (almost-everywhere) public coin with constant bias in a dynamic network with Byzantine nodes and provide a mechanism for enabling honest nodes to store information reliably in the network, which might be of independent interest.
AB - We study the fundamental Byzantine leader election problem in dynamic networks where the topology can change from round to round and nodes can also experience heavy churn (i.e., nodes can join and leave the network continuously over time). We assume the full information model where the Byzantine nodes have complete knowledge about the entire state of the network at every round (including random choices made by all the nodes), have unbounded computational power and can deviate arbitrarily from the protocol. The churn is controlled by an adversary that has complete knowledge and control over which nodes join and leave and at what times and also may rewire the topology in every round and has unlimited computational power, but is oblivious to the random choices made by the algorithm. Our main contribution is an O(log3 n) round algorithm that achieves Byzantine leader election under the presence of up to O(n1/2-ε) Byzantine nodes (for a small constant ε > 0) and a churn of up to O(√n/ polylog(n)) nodes per round (where n is the stable network size). The algorithm elects a leader with probability at least 1 - n-Ω(1) and guarantees that it is an honest node with probability at least 1-n-Ω(1); assuming the algorithm succeeds, the leader’s identity will be known to a 1-o(1) fraction of the honest nodes. Our algorithm is fully-distributed, lightweight, and is simple to implement. It is also scalable, as it runs in polylogarithmic (in n) time and requires nodes to send and receive messages of only polylogarithmic size per round. To the best of our knowledge, our algorithm is the first scalable solution for Byzantine leader election in a dynamic network with a high rate of churn; our protocol can also be used to solve Byzantine agreement in a straightforward way. We also show how to implement an (almost-everywhere) public coin with constant bias in a dynamic network with Byzantine nodes and provide a mechanism for enabling honest nodes to store information reliably in the network, which might be of independent interest.
UR - http://www.scopus.com/inward/record.url?scp=84946039925&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84946039925&partnerID=8YFLogxK
U2 - 10.1007/978-3-662-48653-5_19
DO - 10.1007/978-3-662-48653-5_19
M3 - Conference contribution
AN - SCOPUS:84946039925
SN - 9783662486528
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 276
EP - 291
BT - Distributed Computing - 29th International Symposium, DISC 2015, Proceedings
A2 - Moses, Yoram
PB - Springer Verlag
T2 - 29th International Symposium on Distributed Computing, DISC 2015
Y2 - 7 October 2015 through 9 October 2015
ER -