TY - GEN

T1 - Synchronous convex hull consensus in the presence of crash faults

AU - Tseng, Lewis

AU - Vaidya, Nitin H.

PY - 2014/1/1

Y1 - 2014/1/1

N2 - This paper defines a new consensus problem, convex hull consensus. The input at each process is a d-dimensional vector of reals (or, equivalently, a point in the d-dimensional Euclidean space), and the output at each process is a convex polytope contained within the convex hull of the inputs at the fault-free processes. We explore the convex hull consensus problem under crash faults with incorrect inputs, and present an asynchronous approximate convex hull consensus algorithm with optimal fault tolerance that reaches consensus on an optimal output poly tope. Convex hull consensus can be used to solve other related problems. For instance, a solution for convex hull consensus trivially yields a solution for vector (multidimensional) consensus. More importantly, convex hull consensus can potentially be used to solve other more interesting problems, such as function optimization.

AB - This paper defines a new consensus problem, convex hull consensus. The input at each process is a d-dimensional vector of reals (or, equivalently, a point in the d-dimensional Euclidean space), and the output at each process is a convex polytope contained within the convex hull of the inputs at the fault-free processes. We explore the convex hull consensus problem under crash faults with incorrect inputs, and present an asynchronous approximate convex hull consensus algorithm with optimal fault tolerance that reaches consensus on an optimal output poly tope. Convex hull consensus can be used to solve other related problems. For instance, a solution for convex hull consensus trivially yields a solution for vector (multidimensional) consensus. More importantly, convex hull consensus can potentially be used to solve other more interesting problems, such as function optimization.

KW - Asynchronous system

KW - Convex hull consensus

KW - Crash faults

KW - Vector inputs

UR - http://www.scopus.com/inward/record.url?scp=84905482259&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84905482259&partnerID=8YFLogxK

U2 - 10.1145/2611462.2611470

DO - 10.1145/2611462.2611470

M3 - Conference contribution

AN - SCOPUS:84905482259

SN - 9781450329446

T3 - Proceedings of the Annual ACM Symposium on Principles of Distributed Computing

SP - 396

EP - 405

BT - PODC 2014 - Proceedings of the 2014 ACM Symposium on Principles of Distributed Computing

PB - Association for Computing Machinery

T2 - 2014 ACM Symposium on Principles of Distributed Computing, PODC 2014

Y2 - 15 July 2014 through 18 July 2014

ER -