License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.06371.3
URN: urn:nbn:de:0030-drops-8501
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2007/850/
Go to the corresponding Portal

Druschel, Peter ; Haeberlen, Andreas ; Kouznetsov, Petr

Abstracting out Byzantine Behavior

pdf-format:
06371.KouznetsovPetr.ExtAbstract.850.pdf (0.2 MB)

Abstract

Many distributed systems are designed to tolerate the presence of emph{Byzantine} failures: an individual process may arbitrarily deviate from the algorithm assigned to it.
Depending on the application requirements, systems enjoy various levels of fault-tolerance. Systems based on state machine replication are able to emph{mask} failures so that their effect is not visible by the application. In contrast, cooperative peer-to-peer systems can tolerate bounded deviant behavior to some extent and therefore do not require masking, as long as each faulty node is emph{exposed}eventually. Finding an abstract way to reason about the levels of fault-tolerance is thus of immanent importance.

We discuss how the information of deviant behavior can be abstracted out in the form of a emph{Byzantine failure detector} (BFD). We formally define a BFD abstraction, and
we discuss two ways of using the abstraction: (1) monitoring systems in order to retroactively detect Byzantine failures and (2) enforcing systems in order to boost their level of fault-tolerance. Interestingly, the BFD formalism allowed us to determine the relative hardness of implementing two popular abstractions in distributed computing: state machine replication and weak interactive consistency.

BibTeX - Entry

@InProceedings{druschel_et_al:DagSemProc.06371.3,
  author =	{Druschel, Peter and Haeberlen, Andreas and Kouznetsov, Petr},
  title =	{{Abstracting out Byzantine Behavior}},
  booktitle =	{From Security to Dependability},
  pages =	{1--12},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6371},
  editor =	{Christian Cachin and Felix C. Freiling and Jaap-Henk Hoepman},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2007/850},
  URN =		{urn:nbn:de:0030-drops-8501},
  doi =		{10.4230/DagSemProc.06371.3},
  annote =	{Keywords: Fault-tolerance, Byzantine failures, masking, detection, total order broadcast, weak interactive consistency}
}

Keywords: Fault-tolerance, Byzantine failures, masking, detection, total order broadcast, weak interactive consistency
Collection: 06371 - From Security to Dependability
Issue Date: 2007
Date of publication: 10.01.2007

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI