正版新书]分布式算法 典藏版(美)南希·A.林奇9787111724247

目    录<br />Distributed Algorithms<br />译者序<br />前言<br />第1章  引言  1<br />1.1  相关主题  1<br />1.2  我们的观点  2<br />1.3  本书内容综述  4<br />1.4  参考文献注释  7<br />1.5  标记  8<br />第一部分  同步网络算法<br />第2章  建模I：同步网络模型  10<br />2.1  同步网络系统  10<br />2.2  故障  11<br />2.3  输入和输出  11<br />2.4  运行  12<br />2.5  证明方法  12<br />2.6  复杂度度量  12<br />2.7  随机化  13<br />2.8  参考文献注释  13<br />第3章  同步环中的领导者选择  14<br />3.1  问题  14<br />3.2  相同进程的不可能性结果  15<br />3.3  基本算法  15<br />3.4  通信复杂度为O (nlogn）的算法  17<br />3.5  非基于比较的算法  20<br />3.5.1  时间片算法  20<br />3.5.2  变速算法  20<br />3.6  基于比较的算法的下界  22<br />3.7  非基于比较的算法的下界*  26<br />3.8  参考文献注释  27<br />3.9  习题  27<br />第4章  一般同步网络中的算法  29<br />4.1  一般网络中的领导者选举  29<br />4.1.1  问题  29<br />4.1.2  简单的洪泛算法  29<br />4.1.3  降低通信复杂度  31<br />4.2  广度优先搜索  32<br />4.2.1  问题  33<br />4.2.2  基本的广度优先搜索算法  33<br />4.2.3  应用  34<br />4.3  最短路径  35<br />4.4  最小生成树  36<br />4.4.1  问题  36<br />4.4.2  基本定理  36<br />4.4.3  算法  38<br />4.5  优选独立集  40<br />4.5.1  问题  40<br />4.5.2  随机化算法  41<br />4.5.3  分析*  42<br />4.6  参考文献注释  44<br />4.7  习题  44<br />第5章  链路故障时的分布式<br />一致性  46<br />5.1  协同攻击问题—确定性版本  46<br />5.2  协同攻击问题—随机化版本  48<br />5.2.1  形式化模型  49<br />5.2.2  算法  49<br />5.2.3  不一致的下限  52<br />5.3  参考文献注释  54<br />5.4  习题  54<br />第6章  进程故障下的分布式<br />一致性  56<br />6.1  问题  57<br />6.2  针对停止故障的算法  58<br />6.2.1  基本算法  58<br />6.2.2  减少通信  60<br />6.2.3  指数信息收集算法  61<br />6.2.4  带鉴别的Byzantine一致性  66<br />6.3  针对Byzantine故障的算法  66<br />6.3.1  举例  67<br />6.3.2  Byzantine一致性问题的EIG<br />算法  68<br />6.3.3  使用二元Byzantine一致性的<br />一般Byzantine一致性问题  71<br />6.3.4  减少通信开销  72<br />6.4  Byzantine一致性问题中进程的<br />个数  75<br />6.5  一般图中的Byzantine一致性<br />问题  78<br />6.6  弱Byzantine一致性  81<br />6.7  有停止故障时的轮数  82<br />6.8  参考文献注释  88<br />6.9  习题  89<br />第7章  更多的一致性问题  93<br />7.1  k一致性问题  93<br />7.1.1  问题  93<br />7.1.2  算法  94<br />7.1.3  下界*  95<br />7.2  近似一致性  103<br />7.3  提交问题  106<br />7.3.1  问题  106<br />7.3.2  两阶段提交  107<br />7.3.3  三阶段提交  108<br />7.3.4  消息数的下界  110<br />7.4  参考文献注释  112<br />7.5  习题  112<br />第二部分  异步算法<br />第8章  建模II：异步系统模型  116<br />8.1  输入/输出自动机  116<br />8.2  自动机的操作  120<br />8.2.1  合成  120<br />8.2.2  隐藏  123<br />8.3  公平性  123<br />8.4  问题的输入和输出  126<br />8.5  属性与证明方法  126<br />8.5.1  不变式断言  126<br />8.5.2  轨迹属性  126<br />8.5.3  安全与活性属性  127<br />8.5.4  合成推理  129<br />8.5.5  层次化证明  131<br />8.6  复杂度衡量  133<br />8.7  不可区分的运行  134<br />8.8  随机化  134<br />8.9  参考文献注释  134<br />8.10  习题  135<br />第二部分A?异步共享存储器算法<br />第9章  建模III：异步共享存储器<br />模型  138<br />9.1  共享存储器系统  138<br />9.2  环境模型  140<br />9.3  不可区分状态  141<br />9.4  共享变量类型  142<br />9.5  复杂度衡量  145<br />9.6  故障  146<br />9.7  随机化  146<br />9.8  参考文献注释  146<br />9.9  习题  146<br />第10章  互斥  148<br />10.1  异步共享存储器模型  148<br />10.2  问题  150<br />10.3  Dijkstra的互斥算法  153<br />10.3.1  算法  153<br />10.3.2  正确性证明  156<br />10.3.3  互斥条件的一个断言式<br />证明  158<br />10.3.4  运行时间  159<br />10.4  互斥算法的更强条件  160<br />10.5  锁定权互斥算法  162<br />10.5.1  双进程算法  162<br />10.5.2  n进程算法  165<br />10.5.3  锦标赛算法  169<br />10.6  使用单写者共享寄存器的算法  172<br />10.7  Bakery算法  174<br />10.8  寄存器数量的下界  176<br />10.8.1  基本事实  177<br />10.8.2  单写者共享变量  177<br />10.8.3  多写者共享变量  178<br />10.9  使用读–改–写共享变量的<br />互斥  182<br />10.9.1  基本问题  182<br />10.9.2  有界绕过次数  183<br />10.9.3  锁定权  188<br />10.9.4  模拟证明  190<br />10.10  参考文献注释  193<br />10.11  习题  193<br />第11章  资源分配  197<br />11.1?问题  197<br />11.1.1  显式资源规格说明和互斥规格说明  197<br />11.1.2  资源分配问题  198<br />11.1.3  哲学家用餐问题  199<br />11.1.4  解法的受限形式  200<br />11.2  对称哲学家用餐算法的<br />不存在性  200<br />11.3  右–左哲学家用餐算法  202<br />11.3.1  等待链  202<br />11.3.2  基本算法  203<br />11.3.3  扩展  205<br />11.4  随机哲学家用餐算法*  208<br />11.4.1  算法*  208<br />11.4.2  正确性*  210<br />11.5  参考文献注释  216<br />11.6  习题  216<br />第12章  一致性  218<br />12.1?问题  218<br />12.2  使用读/写共享存储器的一致性<br />问题  220<br />12.2.1    221<br />12.2.2  术语  221<br />12.2.3  双价初始化  222<br />12.2.4  无等待终止性的不可能性  222<br />12.2.5  单故障终止性的不可能性<br />结果  224<br />12.3  读/改/写共享存储器上的<br />一致性问题  227<br />12.4  其他共享存储器类型  227<br />12.5  异步共享存储器系统中的可<br />计算性*  227<br />12.6  参考文献注释  229<br />12.7  习题  229<br />第13章  原子对象  232<br />13.1  定义和基本结论  232<br />13.1.1  原子对象的定义  233<br />13.1.2  规范无等待原子对象<br />自动机  238<br />13.1.3  原子对象的合成  240<br />13.1.4  原子对象和共享变量  240<br />13.1.5  显示原子性的一个充分<br />条件  245<br />13.2  用读/写变量实现读–改–写<br />原子对象  246<br />13.3  共享存储器的原子快照  247<br />13.3.1  问题  247<br />13.3.2  带无界变量的一个算法  248<br />13.3.3  带有界变量的一个算法*  251<br />13.4  读/写原子对象  254<br />13.4.1  问题  254<br />13.4.2  证明原子性的其他引理  255<br />13.4.3  带无界变量的一个算法  256<br />13.4.4  两个写者的有界算法  259<br />13.4.5  使用快照的算法   263<br />13.5  参考文献注释  264<br />13.6  习题  265<br />第二部分B  异步网络算法<br />第14章  建模IV：异步网络模型  268<br />14.1  发送/接收系统  268<br />14.1.1  进程  268<br />14.1.2  发送/接收通道  269<br />14.1.3  异步发送/接收系统  272<br />14.1.4  使用可靠FIFO通道的发送/<br />接收系统的属性  272<br />14.1.5  复杂度度量  273<br />14.2  广播系统  274<br />14.2.1  进程  274<br />14.2.2  广播通道  274<br />14.2.3  异步广播系统  275<br />14.2.4  采用可靠广播通道的广播系统的属性  275<br />14.2.5  复杂度度量  275<br />14.3  多播系统  275<br />14.3.1  进程  276<br />14.3.2  多播通道  276<br />14.3.3  异步多播系统  276<br />14.4  参考文献注释  277<br />14.5  习题  277<br />第15章  基本异步网络算法  279<br />15.1  环中的领导者选举  279<br />15.1.1  LCR算法  279<br />15.1.2  HS算法  283<br />15.1.3  PetersonLeader算法  283<br />15.1.4  通信复杂度的下界  286<br />15.2  任意网络中的领导者选举  291<br />15.3  生成树的构造、广播和敛播  292<br />15.4  广度优先搜索和最短路径  295<br />15.5  最小生成树  300<br />15.5.1  问题描述  301<br />15.5.2  同步算法：回顾  301<br />15.5.3  GHS算法：概要  302<br />15.5.4  更详细的算法  303<br />15.5.5  特殊消息  305<br />15.5.6  复杂度分析  306<br />15.5.7  GHS算法的正确性证明  307<br />15.5.8  简单“同步”策略  308<br />15.5.9  应用到领导者选举算法中  308<br />15.6  参考文献注释  309<br />15.7  习题  309<br />第16章  同步器  313<br />16.1  问题  313<br />16.2  局部同步器  315<br />16.3  安全同步器  319<br />16.3.1  前端自动机  320<br />16.3.2  通道自动机  321<br />16.3.3  安全同步器的任务  321<br />16.3.4  正确性  322<br />16.4  安全同步器的实现  322<br />16.4.1  同步器Alpha  322<br />16.4.2  同步器Beta  323<br />16.4.3  同步器Gamma  323<br />16.5  应用  327<br />16.5.1  领导者选举  327<br />16.5.2  广度优先搜索  327<br />16.5.3  最短路径  328<br />16.5.4  广播与确认  328<br />16.5.5  优选独立集  328<br />16.6  时间下界  328<br />16.7  参考文献注释  331<br />16.8  习题  331<br />第17章  共享存储器与网络  333<br />17.1  从异步共享存储器模型到异步<br />网络模型的转换  333<br />17.1.1  问题  333<br />17.1.2  无故障时的策略  334<br />17.1.3  容忍进程故障的算法  339<br />17.1.4  对于n/2故障的不可能性<br />结果  342<br />17.2  从异步网络模型到异步共享存储器模型的转换  343<br />17.2.1  发送/接收系统  344<br />17.2.2  广播系统  345<br />17.2.3  异步网络中一致性的<br />不可能性  346<br />17.3  参考文献注释  346<br />17.4  习题  346<br />第18章  逻辑时间  348<br />18.1  异步网络的逻辑时间  348<br />18.1.1  发送/接收系统  348<br />18.1.2  广播系统  350<br />18.2  使用逻辑时间的异步算法  351<br />18.2.1  时钟的走动  351<br />18.2.2  延迟未来事件  352<br />18.3  应用  353<br />18.3.1  银行系统  353<br />18.3.2  全局快照  355<br />18.3.3  模拟一台单状态机  356<br />18.4  从实际时间算法到逻辑时间算法的变换*  359<br />18.5  参考文献注释  359<br />18.6  习题  360<br />第19章  一致全局快照和稳定属性<br />检测  362<br />19.1  发散算法的终止检测  362<br />19.1.1  问题  362<br />19.1.2  DijkstraScholten算法  363<br />19.2  一致全局快照  367<br />19.2.1  问题  367<br />19.2.2  ChandyLamport算法  368<br />19.2.3  应用  372<br />19.3  参考文献注释  374<br />19.4  习题  374<br />第20章  网络资源分配  376<br />20.1  互斥  376<br />20.1.1  问题  376<br />20.1.2  模拟共享存储器  377<br />20.1.3  循环令牌算法  377<br />20.1.4  基于逻辑时间的算法  379<br />20.1.5  LogicalTimeME算法的改进  381<br />20.2  通用资源分配  383<br />20.2.1  问题  383<br />20.2.2  着色算法  384<br />20.2.3  基于逻辑时间的算法  385<br />20.2.4  无环有向图算法  385<br />20.2.5  哲学家饮水*  386<br />20.3  参考文献注释  390<br />20.4  习题  391<br />第21章  带进程故障的异步网络<br />计算  393<br />21.1  网络模型  393<br />21.2  有故障环境中一致性的<br />不可能性  394<br />21.3  随机算法  395<br />21.4  故障检测器  398<br />21.5  k一致性  401<br />21.6  近似一致性  401<br />21.7  异步网络的计算能力*  403<br />21.8  参考文献注释  403<br />21.9  习题  404<br />第22章  数据链路协议  406<br />22.1  问题阐述  406<br />22.2  Stenning协议  407<br />22.3  位变换协议  410<br />22.4  可容忍消息重排序的有界tag<br />协议  413<br />22.4.1  关于可容忍消息重排序和<br />重复的不可能性结论  414<br />22.4.2  可容忍消息丢失和重排序的<br />有界tag协议  416<br />22.4.3  不存在可容忍消息丢失和<br />重排序的高效协议  419<br />22.5  可容忍进程崩溃  422<br />22.5.1  简单的不可能性结论  423<br />22.5.2  更复杂的不可能性结论  423<br />22.5.3  实用的协议  426<br />22.6  参考文献注释  431<br />22.7  习题  431<br />第三部分  部分同步算法<br />第23章  建模V：部分同步系统<br />模型  434<br />23.1  MMT定时自动机  434<br />23.1.1  基本定义  434<br />23.1.2  操作  438<br />23.2  通用定时自动机  440<br />23.2.1  基本定义  440<br />23.2.2  将MMT自动机转化为通用<br />定时自动机  444<br />23.2.3  动作  446<br />23.3  属性和证明方法  448<br />23.3.1  不变式断言  448<br />23.3.2  定时轨迹属性  450<br />23.3.3  模拟关系  450<br />23.4  构造共享存储器和网络系统的<br />模型  456<br />23.4.1  共享存储器系统  456<br />23.4.2  网络  456<br />23.5  参考文献注释  456<br />23.6  习题  457<br />第24章  部分同步的互斥性  459<br />24.1  问题  459<br />24.2  单寄存器算法  460<br />24.3  对定时故障的恢复性  466<br />24.4  不可能性结果  469<br />24.4.1  时间下界  469<br />24.4.2  最终时间界限的不可能性<br />结果*  469<br />24.5  参考文献注释   470<br />24.6  习题  470<br />第25章  部分同步的一致性  473<br />25.1  问题  473<br />25.2  故障检测器  474<br />25.3  基本结论  475<br />25.3.1  上界  475<br />25.3.2  下界  476<br />25.4  有效算法  478<br />25.4.1  算法  478<br />25.4.2  安全属性  479<br />25.4.3  活性和复杂度  480<br />25.5  涉及时间不确定性的下界*  483<br />25.6  其他结果*  487<br />25.6.1  同步进程、异步通道*  487<br />25.6.2  异步进程、同步通道*  488<br />25.6.3  最终时间界限*  488<br />25.7  小结  490<br />25.8  参考文献注释  490<br />25.9  习题  491<br />参考文献  493