分布式算法精髓

譯者序
前言
第1章　頂點著色1
　1.1　問題和模型1
　1.2　著色樹3
　1.3　本章注釋8
　1.4　參考文獻(xiàn)9
第2章　樹算法13
　2.1　廣播13
　2.2　融合廣播15
　2.3　廣度優(yōu)先搜索樹的構(gòu)建15
　2.4　最小生成樹的構(gòu)建17
　2.5　本章注釋20
　2.6　參考文獻(xiàn)20
第3章　領(lǐng)導(dǎo)人選舉23
　3.1　匿名領(lǐng)導(dǎo)人選舉23
　3.2　異步環(huán)24
　3.3　下界27
　3.4　同步環(huán)29
　3.5　本章注釋30
　3.6　參考文獻(xiàn)31
第4章　分布式排序33
　4.1　數(shù)組和網(wǎng)格33
　4.2　排序網(wǎng)絡(luò)36
　4.3　計數(shù)網(wǎng)絡(luò)40
　4.4　本章注釋44
　4.5　參考文獻(xiàn)45
第5章　共享內(nèi)存47
　5.1　模型47
　5.2　互斥48
　5.3　存儲和收集51
　5.4　分離器53
　5.5　二叉分離樹54
　5.6　分離器矩陣56
　5.7　本章注釋57
　5.8　參考文獻(xiàn)57
第6章　共享對象59
　6.1　集中式解決方案59
　6.2　Arrow算法60
　6.3　Ivy算法65
　6.4　本章注釋69
　6.5　參考文獻(xiàn)69
第7章　極大獨立集73
　7.1　MIS73
　7.2　原始的快速M(fèi)IS75
　7.3　快速M(fèi)IS v278
　7.4　應(yīng)用83
　7.5　本章注釋84
　7.6　參考文獻(xiàn)85
第8章　本地下界87
　8.1　模型87
　8.2　本地性87
　8.3　鄰域圖90
　8.4　本章注釋94
　8.5　參考文獻(xiàn)95
第9章　全局問題97
　9.1　直徑和APSP97
　9.2　下界圖100
　9.3　通信復(fù)雜度102
　9.4　分布式復(fù)雜度理論108
　9.5　本章注釋109
　9.6　參考文獻(xiàn)110
第10章　同步113
　10.1　基礎(chǔ)知識113
　10.2　本地同步器α114
　10.3　全局同步器β115
　10.4　混合同步器γ116
　10.5　網(wǎng)絡(luò)分區(qū)118
　10.6　時鐘同步120
　10.7　本章注釋123
　10.8　參考文獻(xiàn)124
第11章　穩(wěn)定性127
　11.1　自穩(wěn)定性127
　11.2　高級穩(wěn)定化132
　11.3　本章注釋135
　11.4　參考文獻(xiàn)136
第12章　社交網(wǎng)絡(luò)137
　12.1　小世界網(wǎng)絡(luò)137
　12.2　傳播研究145
　12.3　本章注釋146
　12.4　參考文獻(xiàn)146
第13章　無線協(xié)議149
　13.1　基礎(chǔ)知識149
　13.2　非統(tǒng)一的初始化150
　13.3　使用碰撞檢測的統(tǒng)一初始化151
　13.4　無碰撞檢測的統(tǒng)一初始化153
　13.5　領(lǐng)導(dǎo)人選舉154
　13.6　使用碰撞檢測的快速領(lǐng)導(dǎo)人選舉155
　13.7　下界159
　13.8　統(tǒng)一異步喚醒160
　13.9　有用的公式161
　13.10　本章注釋162
　13.11　參考文獻(xiàn)162
第14章　標(biāo)記方案165
　14.1　鄰接關(guān)系165
　14.2　有根樹167
　14.3　道路網(wǎng)絡(luò)169
　14.4　本章注釋171
　14.5　參考文獻(xiàn)172
第15章　練習(xí)175