An Introduction to Distributed Algorithms

This is an average book. But I liked the Distributed Algorithms by Nancy Lynch better. It is a much better presented book that this one though most of the material covered is the same give or take a few. Over all a good book worth the money but there are better books. An Introduction to Distributed Algorithms ......Page 1 Dedication ......Page 2 Table of Contents......Page 3 Preface ......Page 4 Acknowledgments ......Page 5 Part Overview ......Page 7 1.1 Distributed-memory systems ......Page 8 1.2 Communication processors ......Page 11 1.3 Routing and flow control ......Page 12 1.4 Reactive message-passing programs ......Page 15 1.5 Handling infinite-capacity channels ......Page 18 Theorem 1.1 ......Page 19 1.6 Processor allocation ......Page 22 1.6.1 The static approach ......Page 23 1.6.2 Task migration ......Page 25 1.8 Exercises ......Page 27 1.9 Bibliographic notes ......Page 28 2.1 Full asynchronism and full synchronism ......Page 31 Theorem 2.1. ......Page 37 Lemma 2.2. ......Page 38 Theorem 2.3. ......Page 39 2.2 Computations on anonymous systems ......Page 42 Theorem 2.4. ......Page 43 Theorem 2.6. ......Page 45 2.2.2 Boolean-function computations ......Page 47 2.2.3 Another algorithm for local orientation ......Page 51 2.3 The role of knowledge in distributed computations ......Page 56 2.4 Exercises ......Page 59 2.5 Bibliographic notes ......Page 60 3.1 Events, orders, and global states ......Page 61 3.2 The complexity of distributed computations ......Page 69 3.2.1 Communication and time complexities ......Page 70 3.2.2 Local and global measures ......Page 72 3.3 Full asynchronism and full synchronism ......Page 73 3.4 The role of synchronism in distributed computations ......Page 77 Theorem 3.1. ......Page 79 3.5 Exercises ......Page 81 3.6 Bibliographic notes ......Page 82 Overview ......Page 83 4.1.1 Basic algorithms ......Page 84 Theorem 4.1 ......Page 88 4.1.2 Handling multiple concurrent instances ......Page 89 4.2 Graph connectivity ......Page 90 4.3 Shortest distances ......Page 93 Theorem 4.3 ......Page 95 4.4 Exercises ......Page 98 4.5 Bibliographic notes ......Page 99 Overview ......Page 100 5.1 Leader election ......Page 101 Corollary 5.2. ......Page 105 Theorem 5.3. ......Page 110 5.2.1 An algorithm ......Page 111 Theorem 5.5. ......Page 115 5.2.2 Some centralized alternatives ......Page 116 5.3 Network synchronization ......Page 117 5.3.1 General synchronizers ......Page 118 5.3.2 Important special cases ......Page 123 5.4 Exercises ......Page 126 5.5 Bibliographic notes ......Page 127 Part 2: Advances and Applications ......Page 129 Overview ......Page 130 6.1 Self-stabilization ......Page 131 6.2 Termination detection ......Page 135 6.2.1 General computations ......Page 136 6.2.2 Diffusing computations ......Page 141 Theorem 6.1. ......Page 145 6.3.1 The computation ......Page 147 6.3.2 An algorithm ......Page 150 6.4 Exercises ......Page 155 6.5 Bibliographic notes ......Page 156 Overview ......Page 157 7.1.1 The problem ......Page 158 7.1.2 An algorithm ......Page 159 Lemma 7.1. ......Page 160 Theorem 7.2. ......Page 171 7.2 Maximum flows in networks ......Page 172 7.2.1 The problem ......Page 173 7.2.2 Two synchronous algorithms ......Page 175 7.4 Bibliographic notes ......Page 186 8.1 Algorithms for mutual exclusion ......Page 188 Theorem 8.1. ......Page 191 Theorem 8.2. ......Page 197 8.2 Sharing multiple resources ......Page 199 8.3 The dining philosophers problem ......Page 200 8.3.1 An algorithm ......Page 201 Theorem 8.3. ......Page 205 8.3.2 Operation under heavy loads ......Page 206 Theorem 8.4. ......Page 208 Corollary 8.5. ......Page 209 Theorem 8.6. ......Page 210 8.4 The drinking philosophers problem ......Page 211 8.5 Exercises ......Page 216 8.6 Bibliographic notes ......Page 217 9.1 Preliminaries ......Page 218 9.2 Techniques for program re-execution ......Page 219 9.3.1 Fundamentals ......Page 222 9.3.2 A trace-based technique ......Page 225 9.3.3 A trace-independent approach ......Page 230 Lemma 9.2. ......Page 232 Theorem 9.3. ......Page 234 Theorem 9.4. ......Page 237 Theorem 9.5. ......Page 243 Theorem 9.6. ......Page 248 9.5 Bibliographic notes ......Page 249 10.1 Physical and logical processes ......Page 251 10.2 Time-stepped simulation ......Page 255 10.3.1 A first algorithm ......Page 260 10.3.2 Conditional events ......Page 267 10.4 Optimistic event-driven simulation ......Page 269 Corollary 10.3. ......Page 274 10.5 Hybrid timing and defeasible time-stepping ......Page 275 10.6 A general framework ......Page 276 10.7 Exercises ......Page 277 10.8 Bibliographic notes ......Page 278 Bibliography......Page 280 Author Index......Page 305 P ......Page 306 Z ......Page 307 Subject Index......Page 308 D ......Page 309 I ......Page 310 N ......Page 311 S ......Page 312 T ......Page 313 List of Figures ......Page 314 List of Listings ......Page 316 An Introduction to Distributed Algorithms takes up some of the main concepts and algorithms, ranging from basic to advanced techniques and applications, that underlie the programming of distributed-memory systems such as computer networks, networks of workstations, and multiprocessors. Written from the broad perspective of distributed-memory systems in general it includes topics such as algorithms for maximum flow, program debugging, and simulation that do not appear in more orthodox texts on distributed algorithms. Moving from fundamentals to advances and applications, ten chapterswith exercises and bibliographic notescover a variety of topics. These include models of distributed computation, information propagation, leader election, distributed snapshots, network synchronization, self- stability, termination detection, deadlock detection, graph algorithms, mutual exclusion, program debugging, and simulation. All of the algorithms are presented in a clear, template- based format for the description of message-passing computations among the nodes of a connected graph. Such a generic setting allows the treatment of problems originating from many different application areas. The main ideas and algorithms are described in a way that balances intuition and formal rigormost are preceded by a general intuitive discussion and followed by formal statements as to correctness complexity or other properties. Message-passing Systems -- Intrinsic Constraints -- Models Of Computation -- Basic Algorithms -- Graph Algorithms -- Program Debugging -- Simulation. Valmir C. Barbosa. Includes Bibliographical References And Index.