| An Introduction to Distributed Algorithms (1996) |
| Front Cover | Book Details | |||||||||||||
|
|
| Plot |
| From the Publisher "Barbosa makes the otherwise difficult subject of distributed algorithms very enjoyable and attractive to both students and researchers. The leading intuitive discussion of each algorithm is so very well organized and clearly written that a reader can, without the slightest effort, have a clear picture of it. An ideal textbook for an one-semester distributed algorithms course." -- Mamoru Maekawa, Professor, Graduate School of Information Systems, University of Electro-Communications, Tokyo "The strength of this book is its focus on practical problems in distributed computing. The book is very accessible---I would use it teaching a senior level course on distributed algorithms." -- David Nicol, Department of Computer Science, Dartmouth College 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 chapters -- with exercises and bibliographic notes -- cover 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 rigor -- most are preceded by a general intuitive discussion and followed by formal statements as to correctness complexity or other properties Table of Contents Preface Part 1. Fundamentals 1. Message-Passing Systems 1.1 Distributed-memory systems 1.2 Communication processors 1.3 Routing and flow control 1.4 Reactive Message-passing programs 1.5 Handling infinite-capacity channels 1.6 Processor allocation 1.7 Ramarks on program development 1.8 Exercises 1.9 Bibliographic notes 2. Intrinsic Constraints 2.1 Full asynchronism and full synchronism 2.2 Computations on anonymous systems 2.3 The role of knowlegde in distributed computatons 2.4 Exercises 2.5 Bibliographic notes 3. Models of Computation 3.1 Events, orders, and global states 3.2 The complexity of distributed computations 3.3 Full asynchronism and full synchronism 3.4 The role of synchronism in distributed computation 3.5 Exercises 3.6 Bibliographic notes 4. Basic Algorithms 4.1 Information propagation 4.2 Graph connectivity 4.3 Shortest distances 4.4 Exercises 4.5 Bibliographic notes 5. Basic Techniques 5.1 Leader election 5.2 Distributed snapshots 5.3 Network synchronization 5.4 Exercises 5.5 Bibliographic notes Part 2. Advances and Applications 6. Stable Properties 6.1 Self-stabilization 6.2 Termination detection 6.3 Deadlock detection 6.4 Exercises 6.5 Bibliographic notes 7. Graph Algorithms 7.1 Minimum spanning trees 7.2 Maximum flows in networks 7.3 Exercises 7.4 Bibliographic notes 8. Resource Sharing 8.1 Algorithms for mutual exclusion 8.2 Sharing multiple resources 8.3 The dining philosophers problem 8.4 The drinking philosophers problem 8.5 Exercises 8.6 Bibliographic notes 9. Program Debugging 9.1 Preliminaries 9.2 Techniques for program re-execution 9.3 Breakpoint detection 9.4 Exercises 9.5 Bibliographic notes 10. Simulation 10.1 Physical and logical processes 10.2 Time-stepped simulation 10.3 Conservative event-driven simulation 10.4 Optimistic event-driven simulation 10.5 Hybrid timing and defeasible time-stepping 10.6 A general framework 10.7 Exercises 10.8 Bibliographic notes Bibliography Author Index Subject Index About the Author Valmir C. Barbosa is Associate Professor of Computer Science, Federal University of Rio de Janeiro. |
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Notes |
| Includes bibliographical references (p. [323]-347) and index. |