E-Book Overview
Replication Techniques in Distributed Systems organizes and surveys the spectrum of replication protocols and systems that achieve high availability by replicating entities in failure-prone distributed computing environments. The entities discussed in this book vary from passive untyped data objects, to typed and complex objects, to processes and messages. Replication Techniques in Distributed Systems contains definitions and introductory material suitable for a beginner, theoretical foundations and algorithms, an annotated bibliography of commercial and experimental prototype systems, as well as short guides to recommended further readings in specialized subtopics. This book can be used as recommended or required reading in graduate courses in academia, as well as a handbook for designers and implementors of systems that must deal with replication issues in distributed systems.
E-Book Content
Replication Techniques in Distributed Systems
The Kluwer International Series on ADVANCES IN DATABASE SYSTEMS Series Editor Ahmed K. Elmagarmid Purdue University West Lafayette, IN 47907 Other books in the Series: DATABASE CONCURRENCY CONTROL: Methods, Performance, and Analysis by Alexander Thomasian, IBM T. J. Watson Research Center TIME-CONSTRAINED TRANSACTION MANAGEMENT Real-Time Constraints in Database Transaction Systems by Nandit R. Soparkar, Henry F. Korth, Abraham Silberschatz SEARCHING MULTIMEDIA DATABASES BY CONTENT by Christos Faloutsos
The Kluwer International Series on Advances in Database Systems addresses the following goals: To publish thorough and cohesive overviews of advanced topics in database systems. To publish works which are larger in scope than survey articles, and which will contain more detailed background information. To provide a single point coverage of advanced and timely topics. To provide a forum for a topic of study by many researchers that may not yet have reached a stage of maturity to warrant a comprehensive textbook.
Replication Techniques in Distributed Systems
Abdelsalam A. Helal Purdue University West Lafayette, Indiana, USA
Abdelsalam A. Heddaya Boston University Boston, Massachusetts, USA
Bharat B. Bhargava Purdue University West Lafayette, Indiana, USA
KLUWER ACADEMIC PUBLISHERS NEW YORK, BOSTON, DORDRECHT, LONDON, MOSCOW
eBook ISBN: Print ISBN:
0-306-47796-3 0-7923-9800-9
©2002 Kluwer Academic Publishers New York, Boston, Dordrecht, London, Moscow Print ©1996 Kluwer Academic Publishers Dordrecht All rights reserved No part of this eBook may be reproduced or transmitted in any form or by any means, electronic, mechanical, recording, or otherwise, without written consent from the Publisher Created in the United States of America Visit Kluwer Online at: and Kluwer's eBookstore at:
http://kluweronline.com http://ebooks.kluweronline.com
To Mindolina and the wonderful Anna Aysha. —A. Helal
To my teachers, colleagues, and students ... for ideas. To Mohga ... for perseverance. To Mostafa and Shehab ... for the future. —A. Heddaya
To my students. —B. Bhargava
This page intentionally left blank
Contents
Foreword Preface 1
2
xiii
Introduction 1.1 1. 2 1. 3 1. 4 1. 5
How systems fail Reliability × Availability = Dependability Replication for failure management Replication for performance Costs and limitations of replication
Replication of Data 2.1
xi
Model of Distributed Database System 2.1.1 Concurrency Control 2.1.2 AtomicityControl 2.1.3 Mutual Consistency in Replicated Databases 2.2 Read One Write All (ROWA) 2.2.1 Simple ROWA Protocol 2.2.2 Read One Write All Available (ROWA-A) 2.2.3 Primary Copy ROWA 2.2.4 True Copy Token ROWA 2.3 Quorum Consensus (QC) or Voting 2.3.1 Uniform Majority QC 2.3.