An introduction to distributed algorithms

著者

• Barbosa, Valmir C

書誌事項

An introduction to distributed algorithms

Valmir C. Barbosa

MIT Press, c1996

• : hbk

注記

Includes bibliographical references (p. [323]-347) and index

内容説明・目次

内容説明

"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 work-stations, and multiprocessors. Written from the broad perspective of distributed-memory systems in general it includes topics such as algorithms for maximum flow, programme 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, programme 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 rigour - most are preceded by a general intuitive discussion and followed by formal statements as to correctness complexity or other properties.

目次

• Part 1 Fundamentals: message-passing systems - distributed-memory systems, communication processors, routing and flow control, reactive message-passing programmes, handling infinite-capacity channels, processor allocation, remarks on programme development
• intrinsic constraints - full asynchronism and full synchronism, computations on anonymous systems, the role of knowledge in distributed computations
• models of computation - events, orders and global states, the complexity of distributed computations, full asynchronism and full synchronism, the role of synchronism in distributed computations
• basic algorithms - information propagation, graph connectivity, shortest distances
• basic techniques - leader election, distributed snapshots, network synchronization. Part 2 Advances and applications: stable properties - self-stabilization, termination detection, deadlock detection
• graph algorithms - minimum spanning trees, maximum flows in networks
• resource sharing - algorithms for mutual exclusion, sharing multiple resources, the dining philosophers problem, the drinking philosophers problem
• programme debugging - preliminaries, techniques for programme re-execution, breakpoint detection
• simulation - physical and logical processes, time-stepped simulation, conservative event-driven simulation, optimistic event-driven simulation, hybrid timing and defeasible time-stepping, a general framework.

「Nielsen BookData」 より

詳細情報

• NII書誌ID(NCID): BA28434510
• ISBN:
  • 0262024128
• LCCN: 96013747
• 出版国コード: us
• タイトル言語コード: eng
• 本文言語コード: eng
• 出版地: Cambridge, Mass.
• ページ数/冊数: xiii, 365 p.
• 大きさ: 24 cm
• 分類:
  • LCC : QA76.9.D5
  • DC20 : 005.2
• 件名:
  • LCSH : Electronic data processing -- Distributed processing
  • LCSH : Computer algorithms