Monographs in Theoretical Computer Science. An EATCS Series

Fault-Tolerant Search Algorithms

Reliable Computation with Unreliable Information

Authors: Cicalese, Ferdinando

  • Will be of value to researchers engaged with the theories of search and fault-tolerant computation  
  • Places a special emphasis throughout on algorithmic efficiency 
  • Supported with exercises and pointers to background literature
see more benefits

Buy this book

eBook $84.99
price for USA (gross)
  • ISBN 978-3-642-17327-1
  • Digitally watermarked, DRM-free
  • Included format: EPUB, PDF
  • ebooks can be used on all reading devices
  • Immediate eBook download after purchase
Hardcover $109.00
price for USA
  • ISBN 978-3-642-17326-4
  • Free shipping for individuals worldwide
  • Usually dispatched within 3 to 5 business days.
Softcover $109.00
price for USA
  • ISBN 978-3-662-51871-7
  • Free shipping for individuals worldwide
  • Usually dispatched within 3 to 5 business days.
About this book

Why a book on fault-tolerant search algorithms? Searching is one of the fundamental problems in computer science. Time and again algorithmic and combinatorial issues originally studied in the context of search find application in the most diverse areas of computer science and discrete mathematics. On the other hand, fault-tolerance is a necessary ingredient of computing.  Due to their inherent complexity, information systems are naturally prone to errors, which may appear at any level – as imprecisions in the data, bugs in the software, or transient or permanent hardware failures. This book provides a concise, rigorous and up-to-date account of different approaches to fault-tolerance in the context of algorithmic search theory.

 

Thanks to their basic structure, search problems offer insights into how fault-tolerant techniques may be applied in various scenarios. In the first part of the book, a paradigmatic model for fault-tolerant search is presented, the Ulam—Rényi problem. Following a didactic approach, the author takes the reader on a tour of Ulam—Rényi problem variants of increasing complexity. In the context of this basic model, fundamental combinatorial and algorithmic issues in the design of fault-tolerant search procedures are discussed. The algorithmic efficiency achievable is analyzed with respect to the statistical nature of the error sources, and the amount of information on which the search algorithm bases its decisions. In the second part of the book, more general models of faults and fault-tolerance are considered. Special attention is given to the application of fault-tolerant search procedures to specific problems in distributed computing, bioinformatics and computational learning.

 

This book will be of special value to researchers from the areas of combinatorial search and fault-tolerant computation, but also to researchers in learning and coding theory, databases, and artificial intelligence. Only basic training in discrete mathematics is assumed. Parts of the book can be used as the basis for specialized graduate courses on combinatorial search, or as supporting material for a graduate or undergraduate course on error-correcting codes.

 

About the authors

The author received the award for the Best Italian Ph.D. thesis in Theoretical Computer Science, for work in this field, and he has since been awarded the Sofja Kovalevskaja Award of the Alexander von Humboldt Foundation and the German Federal Ministry of Research.

Reviews

From the book reviews:

“The book is well-written and well-organized, and provides a rigorous and up-to-date account of a wide area of algorithmic fault-tolerant search. Each chapter is supplemented with useful bibliographical notes and exercises. … This book will be useful to students and researchers in many diverse areas, ranging from combinatorial search, to learning and coding theory. It is a most valuable addition to the EATCS Series ‘Monographs in Theoretical Computer Science’.” (Daniele Mundici, zbMATH, Vol. 1295, 2014)

Table of contents (9 chapters)

  • Prologue: What This Book Is About

    Cicalese, Ferdinando

    Pages 1-6

  • Fault-Tolerant Search à la Ulam-Rényi

    Cicalese, Ferdinando

    Pages 9-29

  • Adaptive vs. Non-adaptive Search

    Cicalese, Ferdinando

    Pages 31-64

  • Weighted Errors over a General Channel

    Cicalese, Ferdinando

    Pages 65-76

  • Variations on a Theme of Ulam and Rényi: More Types of Questions and Lies

    Cicalese, Ferdinando

    Pages 77-98

Buy this book

eBook $84.99
price for USA (gross)
  • ISBN 978-3-642-17327-1
  • Digitally watermarked, DRM-free
  • Included format: EPUB, PDF
  • ebooks can be used on all reading devices
  • Immediate eBook download after purchase
Hardcover $109.00
price for USA
  • ISBN 978-3-642-17326-4
  • Free shipping for individuals worldwide
  • Usually dispatched within 3 to 5 business days.
Softcover $109.00
price for USA
  • ISBN 978-3-662-51871-7
  • Free shipping for individuals worldwide
  • Usually dispatched within 3 to 5 business days.
Loading...

Recommended for you

Loading...

Bibliographic Information

Bibliographic Information
Book Title
Fault-Tolerant Search Algorithms
Book Subtitle
Reliable Computation with Unreliable Information
Authors
Series Title
Monographs in Theoretical Computer Science. An EATCS Series
Copyright
2013
Publisher
Springer-Verlag Berlin Heidelberg
Copyright Holder
Springer-Verlag Berlin Heidelberg
eBook ISBN
978-3-642-17327-1
DOI
10.1007/978-3-642-17327-1
Hardcover ISBN
978-3-642-17326-4
Softcover ISBN
978-3-662-51871-7
Series ISSN
1431-2654
Edition Number
1
Number of Pages
XV, 207
Number of Illustrations and Tables
14 b/w illustrations
Topics