DesignandAnalysisofDistributedAlgorithms资源-CSDN文库

algorithm

distributed

5星 · 超过95%的资源需积分: 9 6 浏览量 2008-02-19 16:13:52 上传评论收藏 3.57MB PDF 举报

资源推荐

资源详情

资源评论

DESIGN AND ANALYSIS

OF DISTRIBUTED

ALGORITHMS

Nicola Santoro

Carleton University, Ottawa, Canada

WILEY-INTERSCIENCE

A JOHN WILEY & SONS, INC., PUBLICATION

Published by John Wiley & Sons, Inc., Hoboken, New Jersey

Published simultaneously in Canada

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, scanning, or otherwise, except as

permitted under Section 107 or 108 of the 1976 United States Copyright Act, without either the prior

written permission of the Publisher, or authorization through payment of the appropriate per-copy fee to

the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, (978) 750-8400, fax

(978) 750-4470, or on the web at www.copyright.com. Requests to the Publisher for permission should

be addressed to the Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ

07030, (201) 748-6011, fax (201) 748-6008, or online at http://www.wiley.com/go/permission.

Limit of Liability/Disclaimer of Warranty: While the publisher and author have used their best efforts in

preparing this book, they make no representations or warranties with respect to the accuracy or

completeness of the contents of this book and speciﬁcally disclaim any implied warranties of

merchantability or ﬁtness for a particular purpose. No warranty may be created or extended by sales

representatives or written sales materials. The advice and strategies contained herein may not be suitable

for your situation. You should consult with a professional where appropriate. Neither the publisher nor

author shall be liable for any loss of proﬁt or any other commercial damages, including but not limited to

special, incidental, consequential, or other damages.

For general information on our other products and services or for technical support, please contact our

Customer Care Department within the United States at (800) 762-2974, outside the United States at (317)

572-3993 or fax (317) 572-4002.

Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may

not be available in electronic formats. For more information about Wiley products, visit our web site at

www.wiley.com.

Library of Congress Cataloging-in-Publication Data:

Santoro, N. (Nicola), 1951-

Design and analysis of distributed algorithms / by Nicola Santoro.

p. cm. – (Wiley series on parallel and distributed computing)

Includes index.

ISBN-13: 978-0-471-71997-7 (cloth)

ISBN-10: 0-471-71997-8 (cloth)

1. Electronic data processing–Distributed processing. 2. Computer algorithms. I. Title. II. Series.

QA76.9.D5.S26 2007

005.1–dc22

2006011214

Printed in the United States of America

10987654321

CONTENTS

Preface .............................................................. xiv

1. Distributed Computing Environments............................... 1

1.1 Entities......................................................... 1

1.2 Communication ................................................. 4

1.3 Axioms and Restrictions ......................................... 4

1.3.1 Axioms ................................................... 5

1.3.2 Restrictions ............................................... 6

1.4 Cost and Complexity ............................................ 9

1.4.1 Amount of Communication Activities ........................ 9

1.4.2 Time .................................................... 10

1.5 An Example: Broadcasting ...................................... 10

1.6 States and Events............................................... 14

1.6.1 Time and Events .......................................... 14

1.6.2 States and Conﬁgurations .................................. 16

1.7 Problems and Solutions () ...................................... 17

1.8 Knowledge .................................................... 19

1.8.1 Levels of Knowledge...................................... 19

1.8.2 Types of Knowledge ...................................... 21

1.9 Technical Considerations........................................ 22

1.9.1 Messages ................................................ 22

1.9.2 Protocol ................................................. 23

1.9.3 Communication Mechanism ............................... 24

1.10 Summary of Deﬁnitions......................................... 25

1.11 Bibliographical Notes........................................... 25

1.12 Exercises, Problems, and Answers ............................... 26

1.12.1 Exercises and Problems .................................. 26

1.12.2 Answers to Exercises..................................... 27

2. Basic Problems And Protocols ..................................... 29

2.1 Broadcast ..................................................... 29

2.1.1 The Problem ............................................. 29

2.1.2 Cost of Broadcasting ...................................... 30

2.1.3 Broadcasting in Special Networks .......................... 32

vii

viii CONTENTS

2.2 Wake-Up ...................................................... 36

2.2.1 Generic Wake-Up......................................... 36

2.2.2 Wake-Up in Special Networks.............................. 37

2.3 Traversal ...................................................... 41

2.3.1 Depth-First Traversal...................................... 42

2.3.2 Hacking () .............................................. 44

2.3.3 Traversal in Special Networks .............................. 49

2.3.4 Considerations on Traversal................................ 50

2.4 Practical Implications: Use a Subnet.............................. 51

2.5 Constructing a Spanning Tree.................................... 52

2.5.1 SPT Construction with a Single Initiator: Shout .............. 53

2.5.2 Other SPT Constructions with Single Initiator................ 58

2.5.3 Considerations on the Constructed Tree ..................... 60

2.5.4 Application: Better Traversal............................... 62

2.5.5 Spanning-Tree Construction with

Multiple Initiators......................................... 62

2.5.6 Impossibility Result ....................................... 63

2.5.7 SPT with Initial Distinct Values ............................ 65

2.6 Computations in Trees .......................................... 70

2.6.1 Saturation: A Basic Technique ............................. 71

2.6.2 Minimum Finding ........................................ 74

2.6.3 Distributed Function Evaluation ............................ 76

2.6.4 Finding Eccentricities ..................................... 78

2.6.5 Center Finding ........................................... 81

2.6.6 Other Computations....................................... 84

2.6.7 Computing in Rooted Trees ................................ 85

2.7 Summary...................................................... 89

2.7.1 Summary of Problems..................................... 89

2.7.2 Summary of Techniques ................................... 90

2.8 Bibliographical Notes........................................... 90

2.9 Exercises, Problems, and Answers ............................... 91

2.9.1 Exercises ................................................ 91

2.9.2 Problems................................................. 95

2.9.3 Answers to Exercises...................................... 95

3. Election .......................................................... 99

3.1 Introduction ................................................... 99

3.1.1 Impossibility Result ....................................... 99

3.1.2 Additional Restrictions ................................... 100

3.1.3 Solution Strategies ....................................... 101

3.2 Election in Trees .............................................. 102

3.3 Election in Rings.............................................. 104

3.3.1 All the Way ............................................. 105

剩余602页未读，继续阅读

评论收藏

内容反馈

guoxze

2014-05-19

非常好的讲述分布式算法的书，值得一读

drmingdrmer

粉丝: 1
资源: 1

Design and Analysis of Distributed Algorithms

最新资源

Design and Analysis of Distributed Algorithms

Design and Analysis of Algorithms

Algorithms Design and Analysis

The Design and Analysis of Algorithms

Chapter 4 Solutions.doc

Chapter 2 Solutions.doc

Chapter 3 Solutions.doc

分布式研究的经典教材2部

Algorithms: Design and Analysis

Design-and-Analysis-of-Algorithms

Analysis and Design of Algorithms

Algorithms Design Techniques and Analysis

Introduction to the Design and Analysis of Algorithms

Principles of Distributed Database Systems

Parallel Algorithms

Efficient Broadcasting Using Network Coding

Fuzzy Sets in Human-Centric Systems

Introduction to The Design & Analysis of Algorithms

Introduction to Design Analysis of Algorithms

Design-and-Analysis-of-Algorithms_Algoritms_

Data Analytics with Hadoop(O'Reilly,2016)

Data Algorithms(O'Reilly,2016)

Hands-On Data Science and Python Machine Learning

Data Analytics with Hadoop: An Introduction for Data Scientists

09年新书，感知无线电 网络中的频谱接入和管理Dynamic Spectrum Access and Management in Cognitive Radio Networks

最新资源

09年新书，感知无线电网络中的频谱接入和管理Dynamic Spectrum Access and Management in Cognitive Radio Networks