第1页 / 共899页
第2页 / 共899页
第3页 / 共899页
第4页 / 共899页
第5页 / 共899页
第6页 / 共899页
第7页 / 共899页
第8页 / 共899页
[分布式算法] Distributed Algorithms Nancy Lynch 最新版 打印版.pdf
Front Cover
Distributed Algorithms
Copyright Page
Contents
Preface
Chapter 1. Introduction
1.1 The Subject Matter
1.2 Our Viewpoint
1.3 Overview of Chapters 2-25
1.4 Bibliographic Notes
1.5 Notation
Part I: Synchronous Network Algorithms
Chapter 2. Modelling I: Synchronous Network Model
2.1 Synchronous Network Systems
2.2 Failures
2.3 Inputs and Outputs
2.4 Executions
2.5 Proof Methods
2.6 Complexity Measures
2.7 Randomization
2.8 Bibliographic Notes
Chapter 3. Leader Election in a Synchronous Ring
3.1 The Problem
3.2 Impossibility Result for Identical Processes
3.3 A Basic Algorithm
3.4 An Algorithm with O (n log n) Communication Complexity
3.5 Non-Comparison-Based Algorithms
3.6 Lower Bound for Comparison-Based Algorithms
3.7 Lower Bound for Non-Comparison-Based Algorithms
3.8 Bibliographic Notes
3.9 Exercises
Chapter 4. Algorithms in General Synchronous Networks
4.1 Leader Election in a General Network
4.2 Breadth-First Search
4.3 Shortest Paths
4.4 Minimum Spanning Tree
4.5 Maximal Independent Set
4.6 Bibliographic Notes
4.7 Exercises
Chapter 5. Distributed Consensus with Link Failures
5.1 The Coordinated Attack Problem—Deterministic Version
5.2 The Coordinated Attack Problem—Randomized Version
5.3 Bibliographic Notes
5.4 Exercises
Chapter 6. Distributed Consensus with Process Failures
6.1 The Problem
6.2 Algorithms for Stopping Failures
6.3 Algorithms for Byzantine Failures
6.4 Number of Processes for Byzantine Agreement
6.5 Byzantine Agreement in General Graphs
6.6 Weak Byzantine Agreement
6.7 Number of Rounds with Stopping Failures
6.8 Bibliographic Notes
6.9 Exercises
Chapter 7. More Consensus Problems
7.1 k-Agreement
7.2 Approximate Agreement
7.3 The Commit Problem
7.4 Bibliographic Notes
7.5 Exercises
Part II: Asynchronous Algorithms
Chapter 8. Modelling II: Asynchronous System Model
8.1 I/O Automata
8.2 Operations on Automata
8.3 Fairness
8.4 Inputs and Outputs for Problems
8.5 Properties and Proof Methods
8.6 Complexity Measures
8.7 Indistinguishable Executions
8.8 Randomization
8.9 Bibliographic Notes
8.10 Exercises
Part IIA: Asynchronous Shared Memory Algorithms
Chapter 9. Modelling III: Asynchronous Shared Memory Model
9.1 Shared Memory Systems
9.2 Environment Model
9.3 Indistinguishable States
9.4 Shared Variable Types
9.5 Complexity Measures
9.6 Failures
9.7 Randomization
9.8 Bibliographic Notes
9.9 Exercises
Chapter 10. Mutual Exclusion
10.1 Asynchronous Shared Memory Model
10.2 The Problem
10.3 Dijkstra's Mutual Exclusion Algorithm
10.4 Stronger Conditions for Mutual Exclusion Algorithms
10.5 Lockout-Free Mutual Exclusion Algorithms
10.6 An Algorithm Using Single-Writer Shared Registers
10.7 The Bakery Algorithm
10.8 Lower Bound on the Number of Registers
10.9 Mutual Exclusion Using Read-Modify-Write Shared Variables
10.10 Bibliographic Notes
10.11 Exercises
Chapter 11. Resource Allocation
11.1 The Problem
11.2 Nonexistence of Symmetric Dining Philosophers Algorithms
11.3 Right-Left Dining Philosophers Algorithm
11.4 Randomized Dining Philosophers Algorithm
11.5 Bibliographic Notes
11.6 Exercises
Chapter 12. Consensus
12.1 The Problem
12.2 Agreement Using Read/Write Shared Memory
12.3 Agreement Using Read-Modify-Write Shared Memory
12.4 Other Types of Shared Memory
12.5 Computability in Asynchronous Shared Memory Systems
12.6 Bibliographic Notes
12.7 Exercises
Chapter 13. Atomic Objects
13.1 Definitions and Basic Results
13.2 Implementing Read-Modify-Write Atomic Objects in Terms of Read/Write Variables
13.3 Atomic Snapshots of Shared Memory
13.4 Read/Write Atomic Objects
13.5 Bibliographic Notes
13.6 Exercises
Part IIB: Asynchronous Network Algorithms
Chapter 14. Modelling IV: Asynchronous Network Model
14.1 Send/Receive Systems
14.2 Broadcast Systems
14.3 Multicast Systems
14.4 Bibliographic Notes
14.5 Exercises
Chapter 15. Basic Asynchronous Network Algorithms
15.1 Leader Election in a Ring
15.2 Leader Election in an Arbitrary Network
15.3 Spanning Tree Construction, Broadcast and Convergecast
15.4 Breadth-First Search and Shortest Paths
15.5 Minimum Spanning Tree
15.6 Bibliographic Notes
15.7 Exercises
Chapter 16. Synchronizers
16.1 The Problem
16.2 The Local Synchronizer
16.3 The Safe Synchronizer
16.4 Safe Synchronizer Implementations
16.5 Applications
16.6 Lower Bound on Time
16.7 Bibliographic Notes
16.8 Exercises
Chapter 17. Shared Memory versus Networks
17.1 Transformations from the Shared Memory Model to the Network Model
17.2 Transformations from the Network Model to the Shared Memory Model
17.3 Bibliographic Notes
17.4 Exercises
Chapter 18. Logical Time
18.1 Logical Time for Asynchronous Networks
18.2 Adding Logical Time to Asynchronous Algorithms
18.3 Applications
18.4 Transforming Real-Time Algorithms to Logical-Time Algorithms
18.5 Bibliographic Notes
18.6 Exercises
Chapter 19. Consistent Global Snapshots and Stable Property Detection
19.1 Termination-Detection for Diffusing Algorithms
19.2 Consistent Global Snapshots
19.3 Bibliographic Notes
19.4 Exercises
Chapter 20. Network Resource Allocation
20.1 Mutual Exclusion
20.2 General Resource Allocation
20.3 Bibliographic Notes
20.4 Exercises
Chapter 21. Asynchronous Network Computing with Process Failures
21.1 The Network Model
21.2 Impossibility of Agreement in the Presence of Faults
21.3 A Randomized Algorithm
21.4 Failure Detectors
21.5 k-Agreement
21.6 Approximate Agreement
21.7 Computability in Asynchronous Networks
21.8 Bibliographic Notes
21.9 Exercises
Chapter 22. Data Link Protocols
22.1 The Problem
22.2 Stenning's Protocol
22.3 Alternating Bit Protocol
22.4 Bounded Tag Protocols Tolerating Reordering
22.5 Tolerating Crashes
22.6 Bibliographic Notes
22.7 Exercises
Part III: Partially Synchronous Algorithms
Chapter 23. Modelling V: Partially Synchronous System Models
23.1 MMT Timed Automata
23.2 General Timed Automata
23.3 Properties and Proof Methods
23.4 Modelling Shared Memory and Network Systems
23.5 Bibliographic Notes
23.6 Exercises
Chapter 24. Mutual Exclusion with Partial Synchrony
24.1 The Problem
24.2 A Single-Register Algorithm
24.3 Resilience to Timing Failures
24.4 Impossibility Results
24.5 Bibliographic Notes
24.6 Exercises
Chapter 25. Consensus with Partial Synchrony
25.1 The Problem
25.2 A Failure Detector
25.3 Basic Results
25.4 An Efficient Algorithm
25.5 A Lower Bound Involving the Timing Uncertainty
25.6 Other Results
25.7 Postscript
25.8 Bibliographic Notes
25.9 Exercises
Bibliography
Index
Related Titles from Morgan Kaufmann
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 A. Lynch
|
Morgan Kaufmann Publishers, Inc.
An Imprint of Elsevier
San Francisco, California
Julie Pabst
Sponsoring Editors Bruce M. Spatz/Diane D. Cerra
Production Manager Yonie Overton
Production Editor
Cover Design Ross Carron Design
Cover Photograph
Scott Camazine
Copyeditor
Composition
Proofreaders Ken DellaPenta, Jennifer McClain, and Gary Morris
Printer Courier Corporation
Ed Sznyter, Babel Press
Sharilyn Hovind
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 mkp@mkp.com
Order toll free 800/745-7323
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: permissions@elsevier.co.uk.
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
I. Title
processing--Distributed processing
QA76.9.A43L96
005.2' 76--dc21
ISBN- 13: 978-1-55860-348-6
ISBN-10:1-55860-348-4
1997
97-413 7 5
To Dennis, Patrick, and Mary
This Page Intentionally Left Blank
Contents
P r e f a c e
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
s i x
1
I n t r o d u c t i o n
1.1
1.2
1.3
1.4
1.5 N o t a t i o n
T h e S u b j e c t M a t t e r
.
O u r V i e w p o i n t
.
O v e r v i e w of C h a p t e r s 2 - 2 5
B i b l i o g r a p h i c N o t e s
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
P a r t
I
Synchronous N e t w o r k Algorithms
2 Modelling I: Synchronous Network Model
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
1
1
4
6
13
14
1 5
17
17
19
20
20
21
21
22
23
2 5
25
27
27
31
35
35
36
38
2.1
2.2
2.3
2.4
2.5
2.6
2.7
2.8
.
.
.
.
.
.
.
.
.
S y n c h r o n o u s N e t w o r k S y s t e m s
F a i l u r e s
.
I n p u t s a n d O u t p u t s
.
.
E x e c u t i o n s
.
P r o o f M e t h o d s
.
.
C o m p l e x i t y M e a s u r e s
.
R a n d o m i z a t i o n
.
B i b l i o g r a p h i c N o t e s
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3 Leader Election i n a S y n c h r o n o u s
.
.
.
.
.
.
.
R i n g
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
T h e P r o b l e m
.
I m p o s s i b i l i t y R e s u l t for Identical P r o c e s s e s
.
3.1
3.2
3.3 A Basic A l g o r i t h m
3.4 A n A l g o r i t h m with O ( n l o g n ) C o m m u n i c a t i o n C o m p l e x i t y
.
3.5
.
.
.
.
. . . . . . . . . . . .
.
.
T h e TimeSlice A l g o r i t h m
.
.
T h e VariableSpeeds A l g o r i t h m
.
N o n - C o m p a r i s o n - B a s e d A l g o r i t h m s
.
3.5.1
.
3.5.2
.
Lower B o u n d for C o m p a r i s o n - B a s e d A l g o r i t h m s
.
.
.
3.6
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
. . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
. . .
.
.
.
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
