Computer Science

Synchronous convex hull consensus in the presence of crash faults

Document Type

Conference Paper

Abstract

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. Copyright 2014 ACM.

Publication Title

Proceedings of the Annual ACM Symposium on Principles of Distributed Computing

Publication Date

2014

First Page

396

Last Page

405

ISBN

9781450329446

DOI

10.1145/2611462.2611470

Keywords

asynchronous system, convex hull consensus, crash faults, vector inputs

APA Citation

Tseng, L., & Vaidya, N. H. (2014, July). Asynchronous convex hull consensus in the presence of crash faults. In Proceedings of the 2014 ACM symposium on Principles of distributed computing (pp. 396-405).

Link to Full Text

Share

COinS