Synchronous convex hull consensus in the presence of crash faults

Lewis Tseng, Nitin H. Vaidya

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish (US)
Title of host publicationPODC 2014 - Proceedings of the 2014 ACM Symposium on Principles of Distributed Computing
PublisherAssociation for Computing Machinery
Pages396-405
Number of pages10
ISBN (Print)9781450329446
DOIs
StatePublished - Jan 1 2014
Event2014 ACM Symposium on Principles of Distributed Computing, PODC 2014 - Paris, France
Duration: Jul 15 2014Jul 18 2014

Publication series

NameProceedings of the Annual ACM Symposium on Principles of Distributed Computing

Other

Other2014 ACM Symposium on Principles of Distributed Computing, PODC 2014
CountryFrance
CityParis
Period7/15/147/18/14

Keywords

  • Asynchronous system
  • Convex hull consensus
  • Crash faults
  • Vector inputs

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'Synchronous convex hull consensus in the presence of crash faults'. Together they form a unique fingerprint.

Cite this