Home > Research > Publications & Outputs > Cliff-edge consensus
View graph of relations

Cliff-edge consensus: agreeing on the precipice

Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSNChapter

Published
Publication date2013
Host publicationParallel computing technologies: 12th International Conference, PaCT 2013, St. Petersburg, Russia, September 30 - October 4, 2013. Proceedings
EditorsVictor Malyshkin
Place of PublicationBerlin
PublisherSpringer-Verlag
Pages51-64
Number of pages14
ISBN (Electronic)9783642399589
ISBN (Print)9783642399572
<mark>Original language</mark>English

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume7979
ISSN (Print)0302-9743

Abstract

This paper presents a new form of consensus that allows nodes to agree locally on the extent of crashed regions in networks of arbitrary size. One key property of our algorithm is that it shows local complexity, i.e. its cost is independent of the size of the complete system, and only depends on the shape and extent of the crashed region to be agreed upon. In this paper, we motivate the need for such an algorithm, formally define this new consensus problem, propose a fault-tolerant solution, and prove its correctness.