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.