Fokkink W. - Distributed Algorithms. An Intuitive Approach [2013, PDF, ENG] torrent

Книги и журналы » Компьютерная литература » Программирование (книги)

Distributed Algorithms. An Intuitive Approach / Распределённые алгоритмы. Интуитивный подход

Год издания: 2013
Автор: Wan Fokkink

Издательство: MIT Press
ISBN: 978-0-262-02677-2
Язык: Английский

Формат: PDF
Качество: Издательский макет или текст (eBook)
Интерактивное оглавление: Да
Количество страниц: 242

Описание: This textbook is meant for a course on distributed algorithms for senior-level under-graduate or graduate students in computer science or software engineering, and as a quick reference for researchers in the field. It focuses on fundamental algorithms and results in distributed computing. The distributed algorithms treated in this book are largely “classics” that were selected mainly because they are instructive with regard to the algorithmic design of distributed systems or shed light on key issues in distributed computing and concurrent programming.

Этот учебник предназначен для курса по распределенным алгоритмам для студентов старших курсов бакалавриата и магистратуры в области компьютерных наук или разработки программного обеспечения, а также в качестве краткого справочника для исследователей в этой области. Он фокусируется на фундаментальных алгоритмах и приводит к распределенным вычислениям. Распределенные алгоритмы, рассматриваемые в этой книге, в значительной степени являются «классическими», выбранными главным образом потому, что они поучительны в отношении алгоритмического проектирования распределенных систем или проливают свет на ключевые вопросы распределенных вычислений и параллельного программирования.
[spoiler="Примеры страниц"]

[/spoiler]
[spoiler="Оглавление"]
1 Introduction

I Message Passing

2 Preliminaries
3 Snapshots
3.1 Chandy-Lamport algorithm
3.2 Lai-Yang algorithm

4 Waves
4.1 Traversal algorithms
4.2 Tree algorithm
4.3 Echo algorithm

5 Deadlock Detection
5.1 Wait-for graphs
5.2 Bracha-Toueg algorithm

6 Termination Detection
6.1 Dijkstra-Scholten algorithm
6.2 Weight-throwing algorithm
6.3 Rana’s algorithm
6.4 Safra’s algorithm

7 Garbage Collection
7.1 Reference counting
7.2 Garbage collection implies termination detection
7.3 Tracing

8 Routing
8.1 Chandy-Misra algorithm
8.2 Merlin-Segall algorithm
8.3 Toueg’s algorithm
8.4 Frederickson’s algorithm
8.5 Packet switching
8.6 Routing on the Internet

9 Election
9.1 Election in rings
9.2 Tree election algorithm
9.3 Echo algorithm with extinction
9.4 Minimum spanning trees

10 Anonymous Networks
10.1 Impossibility of election in anonymous rings
10.2 Probabilistic algorithms
10.3 Itai-Rodeh election algorithm for rings
10.4 Echo algorithm with extinction for anonymous networks
10.5 Computing the size of an anonymous ring is impossible
10.6 Itai-Rodeh ring size algorithm
10.7 Election in IEEE 1394

11 Synchronous Networks
11.1 A simple synchronizer
11.2 Awerbuch’s synchronizer
11.3 Bounded delay networks with local clocks
11.4 Election in anonymous rings with bounded expected delay

12 Crash Failures
12.1 Impossibility of 1-crash consensus
12.2 Bracha-Toueg crash consensus algorithm
12.3 Failure detectors
12.4 Consensus with a weakly accurate failure detector
12.5 Chandra-Toueg algorithm

13 Byzantine Failures
13.1 Bracha-Toueg Byzantine consensus algorithm
13.2 Mahaney-Schneider synchronizer
13.3 Lamport-Shostak-Pease broadcast algorithm
13.4 Lamport-Shostak-Pease authentication algorithm

14 Mutual Exclusion
14.1 Ricart-Agrawala algorithm
14.2 Raymond’s algorithm
14.3 Agrawal-El Abbadi algorithm

II Shared Memory

15 Preliminaries

16 Mutual Exclusion II
16.1 Peterson’s algorithm
16.2 Bakery algorithm
16.3 N registers are required
16.4 Fischer’s algorithm
16.5 Test-and-test-and-set lock
16.6 Queue locks

17 Barriers
17.1 Sense-reversing barrier
17.2 Combining tree barrier
17.3 Tournament barrier
17.4 Dissemination barrier

18 Self-Stabilization
18.1 Dijkstra’s token ring for mutual exclusion
18.2 Arora-Gouda spanning tree algorithm
18.3 Afek-Kutten-Yung spanning tree algorithm

19 Online Scheduling
19.1 Jobs
19.2 Schedulers
19.3 Resource access control
[/spoiler]