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.5
URN: urn:nbn:de:0030-drops-8488
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2007/848/
Go to the corresponding Portal

Abd-El-Malek, Michael ; Ganger, Gregory R. ; Goodson, Garth R. ; Reiter, Michael K. ; Wylie, Jay J.

Towards bounded wait-free PASIS

pdf-format:
06371.WylieJay.ExtAbstract.848.pdf (0.05 MB)

Abstract

The PASIS read/write protocol implements a Byzantine fault-tolerant erasure-coded atomic register. The prototype PASIS storage system implementation provides excellent best-case performance. Writes require two
round trips and contention- and failure-free reads require one. Unfortunately,
even though writes and reads are wait-free in PASIS, Byzantine components can induce correct clients to perform an unbounded amount of work.

In this extended abstract, we enumerate the avenues by which Byzantine servers and clients can induce correct clients to perform an unbounded amount of work in PASIS. We sketch extensions to the PASIS protocol and Lazy Verification that bound the amount of work Byzantine components can induce correct clients to perform. We believe that the extensions provide bounded wait-free reads and writes. We also believe that an implementation that incorporates these extensions will preserve the excellent best-case performance of the original PASIS prototype.


BibTeX - Entry

@InProceedings{abdelmalek_et_al:DagSemProc.06371.5,
  author =	{Abd-El-Malek, Michael and Ganger, Gregory R. and Goodson, Garth R. and Reiter, Michael K. and Wylie, Jay J.},
  title =	{{Towards bounded wait-free PASIS}},
  booktitle =	{From Security to Dependability},
  pages =	{1--4},
  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/848},
  URN =		{urn:nbn:de:0030-drops-8488},
  doi =		{10.4230/DagSemProc.06371.5},
  annote =	{Keywords: Byzantine fault-tolerant, erasure-coded storage, bounded wait-free, non-skipping timestamps}
}

Keywords: Byzantine fault-tolerant, erasure-coded storage, bounded wait-free, non-skipping timestamps
Collection: 06371 - From Security to Dependability
Issue Date: 2007
Date of publication: 10.01.2007

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