TY - GEN
T1 - Capacity of byzantine agreement with finite link capacity
AU - Liang, Guanfeng
AU - Vaidya, Nitin
PY - 2011
Y1 - 2011
N2 - We consider the problem of maximizing the throughput of Byzantine agreement, when communication links have finite capacity. Byzantine agreement is a classical problem in distributed computing. In existing literature, the communication links are implicitly assumed to have infinite capacity. The problem changes significantly when the capacity of links is finite. We define the throughput and capacity of agreement, and identify necessary conditions of achievable agreement throughputs. We propose an algorithm structure for achieving agreement capacity in general networks. We also introduce capacity achieving algorithms for two classes of networks: (i) arbitrary four-node networks with at most 1 failure; and (ii) symmetric networks of arbitrary size.
AB - We consider the problem of maximizing the throughput of Byzantine agreement, when communication links have finite capacity. Byzantine agreement is a classical problem in distributed computing. In existing literature, the communication links are implicitly assumed to have infinite capacity. The problem changes significantly when the capacity of links is finite. We define the throughput and capacity of agreement, and identify necessary conditions of achievable agreement throughputs. We propose an algorithm structure for achieving agreement capacity in general networks. We also introduce capacity achieving algorithms for two classes of networks: (i) arbitrary four-node networks with at most 1 failure; and (ii) symmetric networks of arbitrary size.
UR - http://www.scopus.com/inward/record.url?scp=79960871630&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=79960871630&partnerID=8YFLogxK
U2 - 10.1109/INFCOM.2011.5935257
DO - 10.1109/INFCOM.2011.5935257
M3 - Conference contribution
AN - SCOPUS:79960871630
SN - 9781424499212
T3 - Proceedings - IEEE INFOCOM
SP - 739
EP - 747
BT - 2011 Proceedings IEEE INFOCOM
T2 - IEEE INFOCOM 2011
Y2 - 10 April 2011 through 15 April 2011
ER -