Vai al contenuto principale della pagina

Introduction to distributed algorithms / Gerard Tel.



(Visualizza formato Marc21)    (visualizza in BIBRAME 2.0)

Creatore: Tel, Gerard, author Visualizza persona
Titolo: Introduction to distributed algorithms / Gerard Tel.
Link to work: Introduction to distributed algorithms Visualizza cluster
Pubblicazione: Cambridge : Cambridge University Press, 2000
Edizione: Second edition.
Estensione: 1 online resource (xii, 596 pages) : digital, PDF file(s).
Tipo formato: computer
Tipo contenuto: text
Tipo supporto: online resource
Disciplina: 005.2/76
Classificazione LOC: QA76.9.D5 T44 2000
Note generali: Title from publisher's bibliographic system (viewed on 05 Oct 2015).
Nota di contenuto: 1 Introduction: Distributed Systems 1 -- 1.2 Architecture and Languages 18 -- 1.3 Distributed Algorithms 26 -- 1.4 Outline of the Book 36 -- Part 1 Protocols 41 -- 2 Model 43 -- 2.1 Transition Systems and Algorithms 44 -- 2.2 Proving Properties of Transition Systems 50 -- 2.3 Causal Order of Events and Logical Clocks 54 -- 2.4 Additional Assumptions, Complexity 64 -- 3 Communication Protocols 74 -- 3.1 Balanced Sliding-window Protocol 76 -- 3.2 A Timer-based Protocol 85 -- 4 Routing Algorithms 103 -- 4.1 Destination-based Routing 105 -- 4.2 All-pairs Shortest-path Problem 110 -- 4.3 Netchange Algorithm 123 -- 4.4 Routing with Compact Routing Tables 132 -- 4.5 Hierarchical Routing 149 -- 5 Deadlock-free Packet Switching 155 -- 5.2 Structured Solutions 158 -- 5.3 Unstructured Solutions 167 -- Part 2 Fundamental Algorithms 179 -- 6 Wave and Traversal Algorithms 181 -- 6.1 Definition and Use of Wave Algorithms 182 -- 6.2 A Collection of Wave Algorithms 190 -- 6.3 Traversal Algorithms 202 -- 6.4 Time Complexity: Depth-first Search 208 -- 7 Election Algorithms 227 -- 7.2 Ring Networks 232 -- 7.3 Arbitrary Networks 245 -- 7.4 Korach-Kutten-Moran Algorithm 260 -- 8 Termination Detection 268 -- 8.2 Computation Trees and Forests 276 -- 8.3 Wave-based Solutions 284 -- 9 Anonymous Networks 307 -- 9.2 Deterministic Algorithms 317 -- 9.3 A Probabilistic Election Algorithm 323 -- 9.4 Computing the Network Size 327 -- 10 Snapshots 335 -- 10.2 Two Snapshot Algorithms 340 -- 10.3 Using Snapshot Algorithms 344 -- 10.4 Application: Deadlock Detection 349 -- 11 Sense of Direction and Orientation 356 -- 11.2 Election in Rings and Chordal Rings 364 -- 11.3 Computing in Hypercubes 374 -- 11.4 Complexity-related Issues 386 -- 12 Synchrony in Networks 396 -- 12.2 Election in Synchronous Networks 404 -- 12.3 Synchronizer Algorithms 408 -- 12.4 Application: Breadth-first Search 414 -- 12.5 Archimedean Assumption 420 -- Part 3 Fault Tolerance 425 -- 13 Fault Tolerance in Distributed Systems 427 -- 13.1 Reasons for Using Fault-tolerant Algorithms 427 -- 13.2 Robust Algorithms 429 -- 13.3 Stabilizing Algorithms 435 -- 14 Fault Tolerance in Asynchronous Systems 437 -- 14.1 Impossibility of Consensus 437 -- 14.2 Initially Dead Processes 442 -- 14.3 Deterministically Achievable Cases 445 -- 14.4 Probabilistic Consensus Algorithms 451 -- 14.5 Weak Termination 462 -- 15 Fault Tolerance in Synchronous Systems 469 -- 15.1 Synchronous Decision Protocols 470 -- 15.2 Authenticating Protocols 481 -- 15.3 Clock Synchronization 493 -- 16 Failure Detection 505 -- 16.2 Solving Consensus with a Weakly Accurate Detector 510 -- 16.3 Eventually Weakly Accurate Detectors 511 -- 16.4 Implementation of Failure Detectors 515 -- 17 Stabilization 520 -- 17.2 Graph Algorithms 526 -- 17.3 Methodology for Stabilization 535 -- A Pseudocode Conventions 551 -- B Graphs and Networks 556.
Sommario/riassunto: Distributed algorithms have been the subject of intense development over the last twenty years. The second edition of this successful textbook provides an up-to-date introduction both to the topic, and to the theory behind the algorithms. The clear presentation makes the book suitable for advanced undergraduate or graduate courses, whilst the coverage is sufficiently deep to make it useful for practising engineers and researchers. The author concentrates on algorithms for the point-to-point message passing model, and includes algorithms for the implementation of computer communication networks. Other key areas discussed are algorithms for the control of distributed applications (wave, broadcast, election, termination detection, randomized algorithms for anonymous networks, snapshots, deadlock detection, synchronous systems), and fault-tolerance achievable by distributed algorithms. The two new chapters on sense of direction and failure detectors are state-of-the-art and will provide an entry to research in these still-developing topics.
ISBN: 9781139168724 (ebook)
9780521794831 (paperback)
Formato: Materiale a stampa
Livello bibliografico Monografia
Lingua di pubblicazione: Inglese
Record Nr.: a12742944
Localizzazioni e accesso elettronico https://stanford.idm.oclc.org/login?url=https://doi.org/10.1017/CBO9781139168724
Lo trovi qui: Stanford University
Item: Permalink to OPAC
Altra ed. diverso supporto: Print version: 9780521794831