2013/07/04 by Lewis Tseng, Tseng, Lewis, Nitin Vaidya +1
Computer Science · #Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC) #cs.DC
paper · pdf · doi:10.48550/arxiv.1307.1332
arXiv admin note: substantial text overlap with arXiv:1307.1051
arxiv created 2013/07/09 · arxiv updated 2013/07/10
Much of the past work on asynchronous approximate Byzantine consensus has assumed scalar inputs at the nodes [4, 8]. Recent work has yielded approximate Byzantine consensus algorithms for the case when the input at each node is a d-dimensional vector, and the nodes must reach consensus on a vector in the convex hull of the input vectors at the fault-free nodes [9, 13]. The d-dimensional vectors can be equivalently viewed as points in the d-dimensional Euclidean space. Thus, the algorithms in [9, 13] require the fault-free nodes to decide on a point in the d-dimensional space. In our recent work [arXiv:/1307.1051], we proposed a generalization of the consensus problem, namely Byzantine convex consensus (BCC), which allows the decision to be a convex polytope in the d-dimensional space, such that the decided polytope is within the convex hull of the input vectors at the fault-free nodes. We also presented an asynchronous approximate BCC algorithm. In this paper, we propose a new BCC algorithm with optimal fault-tolerance that also agrees on a convex polytope that is as large as possible under adversarial conditions. Our prior work [arXiv:/1307.1051] does not guarantee the optimality of the output polytope.