Distributed Algorithms 13.1 Message passing systems and algorithms 13.1.1 Modeling message passing systems 13.1.2 Asynchronous systems 13.1.3 Synchronous systems 13.2 Basic algorithms 13.2.1 Broadcast 13.2.2 Construction of a spanning tree 13.3 Ring algorithms 13.3.1 The leader election problem 13.3.2 The leader election algorithm 13.3.3 Analysis of the leader election algorithm 13.4 Fault-tolerant consensus 13.4.1 The consensus problem 13.4.2 Consensus with crash failures 13.4.3 Consensus with Byzantine failures 13.4.4 Lower bound on the ratio of faulty processors 13.4.5 A polynomial algorithm 13.4.6 Impossibility in asynchronous systems 13.5 Logical time, causality, and consistent state 13.5.1 Logical time 13.5.2 Causality 13.5.3 Consistent state 13.6 Communication services 13.6.1 Properties of broadcast services 13.6.2 Ordered broadcast services 13.6.3 Multicast services 13.7 Rumor collection algorithms 13.7.1 Rumor collection problem and requirements 13.7.2 Efficient gossip algorithms 13.8 Mutual exclusion in shared memory 13.8.1 Shared memory systems 13.8.2 The mutual exclusion problem 13.8.3 Mutual exclusion using powerful primitives 13.8.4 Mutual exclusion using read/write registers 13.8.5 Lamport's fast mutual exclusion algorithm 2.
0 kommentar(er)
