Distributed Algorithms The Morgan Kaufmann Series in Data Management Systems Series Editor, Jim Gray Distributed Algorithms Nancy A. Lynch Object-Relational DBMSs: The Next Great Wave Michael Stonebraker Active Database Systems: Triggers and Rules for Advanced Database Processing Edited by Jennifer Widom and Stefano Ceri Joe Celko's SQL for Smarties: Advanced SQL Programming Joe Celko Migrating Legacy Systems: Gateways, Interfaces, and the Incremental Approach Michael L. Brodie and Michael Stonebraker The Object Database Standard: ODMG-93 (Release 1.2) Edited by R. G. G. Cattell Database: Principles, Programming, and Performance Patrick O'Neil Database Modeling and Design: The Fundamental Principles, Second Edition Toby J. Teorey Readings in Database Systems, Second Edition Edited by Michael Stonebraker Atomic Transactions Nancy Lynch, Michael Merritt, William Weihl, and Alan Fekete Query Processing for Advanced Database Systems Edited by Johann Christoph Freytag, David Maier, and Gottfried Vossen Transaction Processing: Concepts and Techniques Jim Gray and Andreas Reuter Understanding the New SQL: A Complete Guide Jim Melton and Alan R. Simon Building an Object-Oriented Database System: The Story of 02 Edited by Fran(iois Bancilhon, Claude Delobel, and Paris Kanellakis Database Transaction Models for Advanced Applications Edited by Ahmed K. Elmagarmid A Guide to Developing Client/Server SQL Applications Setrag Khoshafian, Arvola Chan, Anna Wong, and Harry K. T. Wong The Benchmark Handbook for Database and Transaction Processing Systems, Second Edition Edited by Jim Gray Camelot and Avalon: A Distributed Transaction Facility Edited by Jeffrey L. Eppinger, Lily B. Mummert~ and Alfred Z. Spector Readings in Object-Oriented Database Systems Edited by Stanley B. Zdonik and David Maier Distributed Algorithms Nancy Lynch A. | Morgan Kaufmann Publishers, Inc. An Imprint of Elsevier San Francisco, California Sponsoring Editors Bruce M. Spatz/Diane D. Cerra Production Manager YonieO verton Production Editor Julie Pabst Cover Design Ross Carron Design Cover Photograph Scott Camazine Copyeditor Sharilyn Hovind Composition Ed Sznyter, Babel Press Proofreaders Ken DellaPenta, Jennifer McClain, and Gary Morris Printer Courier Corporation Morgan Kaufmann Publishers, Inc. Editorial and Sales Office 340 Pine Street, Sixth Floor San Francisco, CA 94104-3205 USA Telephone 415/392-2665 Facsimile 415/982-2665 Internet [email protected] Order toll free 800/745-7323 (cid:14)9 1996by Morgan Kaufmann Publishers, Inc. An Imprint of Elsevier All rights reserved Printed in the United States of America 09 08 07 8 7 No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means--electronic, mechanical, photocopying, recording or other- wise--without the pior written permission of the publisher. Permissions may be sought directly from Elsevier's Science and Technology Rights Department in Oxford, UK. Phone: (44) 1865 843830, Fax: (44) 1865 853333, e-mail: [email protected]. You may also complete your request on-line via the Elsevier homepage: http://www.elsevier.com by selecting "Customer Support" and then "Obtaining Permissions". Library of Congress Cataloging-in-Publication Data Lynch, Nancy A. (Nancy Ann), 1948- Distributed algorithms / Nancy A. Lynch p. cm. Includes bibliographical references and index. ISBN-13:978-1-55860-348-6 ISBN-10:1-55860-348-4 1. Computer algorithms. 2. Electonic data processing--Distributed processing I. Title QA76.9.A43L96 1997 005.2' 76--dc21 97-413 7 5 ISBN- 13: 978-1-55860-348-6 ISBN-10:1-55860-348-4 To Dennis, Patrick, and Mary This Page Intentionally Left Blank Contents Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . six 1 Introduction 1 1.1 The Subject Matter . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Our Viewpoint . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.3 Overview of Chapters 2-25 . . . . . . . . . . . . . . . . . . . . . 6 1.4 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.5 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 Part I Synchronous Network Algorithms 15 2 Modelling I: Synchronous Network Model 17 2.1 Synchronous Network Systems . . . . . . . . . . . . . . . . . . . 17 2.2 Failures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.3 Inputs and Outputs . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.4 Executions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.5 Proof Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.6 Complexity Measures . . . . . . . . . . . . . . . . . . . . . . . . 21 2.7 Randomization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.8 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . 23 3 Leader Election in a Synchronous Ring 25 3.1 The Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.2 Impossibility Result for Identical Processes ............ 27 3.3 A Basic Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.4 An Algorithm with O (nlogn) Communication Complexity . . . 31 3.5 Non-Comparison-Based Algorithms . . . . . . . . . . . . . . . . 35 3.5.1 The TimeSlice Algorithm . . . . . . . . . . . . . . . . . . 35 3.5.2 The VariableSpeeds Algorithm . . . . . . . . . . . . . . . 36 3.6 Lower Bound for Comparison-Based Algorithms ......... 38 viii CONTENTS 3.7 Lower Bound for Non-Comparison-Based Algorithms* ...... 44 3.8 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . 46 3.9 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 4 Algorithms in General Synchronous Networks 51 4.1 Leader Election in a General Network . . . . . . . . . . . . . . . 52 4.1.1 The Problem . . . . . . . . . . . . . . . . . . . . . . . . . 52 4.1.2 A Simple Flooding Algorithm . . . . . . . . . . . . . . . . 52 4.1.3 Reducing the Communication Complexity ......... 54 4.2 Breadth-First Search . . . . . . . . . . . . . . . . . . . . . . . . . 57 4.2.1 The Problem . . . . . . . . . . . . . . . . . . . . . . . . . 57 4.2.2 A Basic Breadth-First Search Algorithm .......... 58 4.2.3 Applications . . . . . . . . . . . . . . . . . . . . . . . . . 60 4.3 Shortest Paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 4.4 Minimum Spanning Tree . . . . . . . . . . . . . . . . . . . . . . 63 4.4.1 The Problem . . . . . . . . . . . . . . . . . . . . . . . . . 63 4.4.2 Basic Theory . . . . . . . . . . . . . . . . . . . . . . . . . 64 4.4.3 The Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 66 4.5 Maximal Independent Set . . . . . . . . . . . . . . . . . . . . . . 71 4.5.1 The Problem . . . . . . . . . . . . . . . . . . . . . . . . . 71 4.5.2 A Randomized Algorithm . . . . . . . . . . . . . . . . . . 71 4.5.3 Analysis* . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 4.6 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . 76 4.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 5 Distributed Consensus with Link Failures 81 5.1 The Coordinated Attack Problem--Deterministic Version .... 82 5.2 The Coordinated Attack Problem--Randomized Version ..... 86 5.2.1 Formal Modelling . . . . . . . . . . . . . . . . . . . . . . 87 5.2.2 An Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 88 5.2.3 A Lower Bound on Disagreement . . . . . . . . . . . . . . 93 5.3 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . 95 5.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 6 Distributed Consensus with Process Failures 99 6.1 The Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 6.2 Algorithms for Stopping Failures . . . . . . . . . . . . . . . . . . 102 6.2.1 A Basic Algorithm . . . . . . . . . . . . . . . . . . . . . . 103 6.2.2 Reducing the Communication . . . . . . . . . . . . . . . . 105 6.2.3 Exponential Information Gathering Algorithms ...... 108 CONTENTS ix 6.2.4 Byzantine Agreement with Authentication ......... 115 6.3 Algorithms for Byzantine Failures . . . . . . . . . . . . . . . . . 116 6.3.1 An Example . . . . . . . . . . . . . . . . . . . . . . . . . 117 6.3.2 EIG Algorithm for Byzantine Agreement ......... 119 6.3.3 General Byzantine Agreement Using Binary Byzantine Agreement . . . . . . . . . . . . . . . . . . . . . . . . . . 123 6.3.4 Reducing the Communication Cost ............. 125 6.4 Number of Processes for Byzantine Agreement .......... 129 6.5 Byzantine Agreement in General Graphs .............. 135 6.6 Weak Byzantine Agreement . . . . . . . . . . . . . . . . . . . . . 139 6.7 Number of Rounds with Stopping Failures ............. 142 6.8 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . 152 6.9 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 7 More Consensus Problems 161 7.1 k-Agreement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161 7.1.1 The Problem . . . . . . . . . . . . . . . . . . . . . . . . . 162 7.1.2 An Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 162 7.1.3 Lower Bound* . . . . . . . . . . . . . . . . . . . . . . . . 164 7.2 Approximate Agreement . . . . . . . . . . . . . . . . . . . . . . . 177 7.3 The Commit Problem . . . . . . . . . . . . . . . . . . . . . . . . 182 7.3.1 The Problem . . . . . . . . . . . . . . . . . . . . . . . . . 182 7.3.2 Two-Phase Commit . . . . . . . . . . . . . . . . . . . . . 184 7.3.3 Three-Phase Commit . . . . . . . . . . . . . . . . . . . . 185 7.3.4 Lower Bound on the Number of Messages ......... 189 7.4 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . 192 7.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192 Part II Asynchronous Algorithms 197 8 Modelling II: Asynchronous System Model 199 8.1 I/O Automata . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200 8.2 Operations on Automata . . . . . . . . . . . . . . . . . . . . . . . 206 8.2.1 Composition . . . . . . . . . . . . . . . . . . . . . . . . . 207 8.2.2 Hiding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212 8.3 Fairness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212 8.4 Inputs and Outputs for Problems . . . . . . . . . . . . . . . . . . 215 8.5 Properties and Proof Methods . . . . . . . . . . . . . . . . . . . 216 8.5.1 Invariant Assertions . . . . . . . . . . . . . . . . . . . . . 216