复制成功
  • 图案背景
  • 纯色背景
  •   |  注册
  • /
  • 批注本地保存成功,开通会员云端永久保存 去开通
  • Introduction to Reliable and Secure Distributed Programming

    下载积分:800

    内容提示: Introduction to Reliable and Secure DistributedProgramming Christian CachinLu´ ıs Rodrigues• Rachid GuerraouiIntroduction toReliable and SecureDistributed ProgrammingSecond Edition123 Dr. Christian CachinIBM Research Z¨ urichS¨ aumerstrasse 48803 R¨ uschlikonSwitzerlandcca@zurich.ibm.comProf. Dr. Rachid GuerraouiEcole PolytechniqueF´ ed´ erale Lausanne (EPFL)Fac. Informatique et CommunicationsLab. Programmation Distribu´ ee (LPD)Station 141015 LausanneBat. INRSwitzerlandRachid.Guerraoui@epfl...

    亚博足球app下载格式:PDF| 浏览次数:29| 上传日期:2012-09-28 13:21:53| 亚博足球app下载星级:
    Introduction to Reliable and Secure DistributedProgramming Christian CachinLu´ ıs Rodrigues• Rachid GuerraouiIntroduction toReliable and SecureDistributed ProgrammingSecond Edition123 Dr. Christian CachinIBM Research Z¨ urichS¨ aumerstrasse 48803 R¨ uschlikonSwitzerlandcca@zurich.ibm.comProf. Dr. Rachid GuerraouiEcole PolytechniqueF´ ed´ erale Lausanne (EPFL)Fac. Informatique et CommunicationsLab. Programmation Distribu´ ee (LPD)Station 141015 LausanneBat. INRSwitzerlandRachid.Guerraoui@epfl.chProf. Lu´ ıs RodriguesINESC-IDInstituto Superior T´ ecnicoRua Alves Redol 91000-029 LisboaPortugaller@ist.utl.ptISBN 978-3-642-15259-7DOI 10.1007/978-3-642-15260-3Springer Heidelberg Dordrecht London New Yorke-ISBN 978-3-642-15260-3Library of Congress Control Number: 2011921701ACM Computing Classification (1998): C.2, F.2, G.2c  Springer-Verlag Berlin Heidelberg 2011, 2006This work is subject to copyright. All rights are reserved, whether the whole or part of the material isconcerned, specifically the rights oftranslation, reprinting, reuse ofillustrations, recitation, broadcasting,reproduction on microfilm or in any other way, and storage in data banks. Duplication ofthis publicationor parts thereof is permitted only under the provisions of the German Copyright Law of September 9,1965, in its current version, and permission for use must always be obtained from Springer. Violationsare liable to prosecution under the German Copyright Law.The use of general descriptive names, registered names, trademarks, etc. in this publication does notimply, even in the absence ofa specific statement, that such names are exempt from the relevant protectivelaws and regulations and therefore free for general use.Cover design: KuenkelLopka GmbHPrinted on acid-free paperSpringer is part of Springer Science+Business Media (www.springer.com) To Irene, Philippe and Andr´ e.To Maria and Sarah.To Hugo and Sara. PrefaceThis book provides an introduction to distributed programming abstractions andpresents the fundamental algorithms that implement them in several distributed en-vironments. The reader is given insight into the important problems of distributedcomputing and the main algorithmic techniques used to solve these problems.Through examples the reader can learn how these methods can be applied to build-ing distributed applications. The central theme of the book is the tolerance touncertainty and adversarial influence in a distributed system, which may arise fromnetwork delays, faults, or even malicious attacks.ContentIn modern computing, a program usually encompasses multiple processes. A pro-cess is simply an abstraction that may represent a physical computer or a virtualone, a processor within a computer, or a specific thread of execution in a concur-rent system. The fundamental problem with devising such distributed programs isto have all processes cooperate on some common task. Of course, traditional cen-tralized algorithmic issues still need to be dealt with for each process individually.Distributed environments, which may range from a single computer to a data centeror even a global system available around the clock, pose additional challenges: howto achieve a robust form of cooperation despite process failures, disconnections ofsome of the processes, or even malicious attacks on some processes? Distributedalgorithms should be dependable, offer reliability and security, and have predictablebehavior even under negative influence from the environment.If no cooperation were required, a distributed program would simply consist ofa set of independent centralized programs, each running on a specific process, andlittle benefit could be obtained from the availability of several processes in a dis-tributed environment. It was the need for cooperation that revealed many of thefascinating problems addressed by this book, problems that need to be solved tomake distributed computing a reality. The book not only introduces the reader tothese problem statements, it also presents ways to solve them in different contexts.Not surprisingly, distributed programming can be significantly simplified ifthe difficulty of robust cooperation is encapsulated within specific abstractions.By encapsulating all the tricky algorithmic issues, such distributed programmingabstractions bridge the gap between network communication layers, which arevii viiiPrefaceusually frugal in terms of dependability guarantees, and distributed applicationlayers, which usually demand highly dependable primitives.The book presents various distributed programming abstractions and describesalgorithms that implement them. In a sense, we give the distributed applicationprogrammer a library of abstract interface specifications, and give the distributedsystem builder a library ofalgorithms that implement the specifications.A significant amount of the preparation time for this book was devoted to for-mulating a collection of exercises and developing their solutions. We stronglyencourage the reader to work out the exercises. We believe that no reasonableunderstanding can be achieved in a passive way. This is especially true in the fieldof distributed computing, where the human mind too often follows some attractivebut misleading intuition. The book also includes the solutions for all exercises, toemphasize ourintentionto make theman integral partofthe content. Many exercisesare rather easy and can be discussed within an undergraduate teaching classroom.Other exercises are more difficult and need more time. These can typically bestudied individually.PresentationThe book as such is self-contained. This has been made possible because the fieldof distributed algorithms has reached a certain level of maturity, where distract-ing details can be abstracted away for reasoning about distributed algorithms. Suchdetails include the behavior ofthe communication network, its various kinds offail-ures, as well as implementations ofcryptographic primitives; all ofthem are treatedin-depth by other works. Elementary knowledge about algorithms, first-order logic,programminglanguages, networking, security, andoperatingsystems mightbe help-ful. But we believe that most of our abstractions and algorithms can be understoodwith minimal knowledge about these notions.The book follows an incremental approach and was primarily written as a text-book for teaching at the undergraduate or basic graduate level. It introduces thefundamental elements of distributed computing in an intuitive manner and buildssophisticated distributed programming abstractions from elementary ones in a mod-ular way. Whenever we devise algorithms to implement a given abstraction, weconsider a simple distributed-system model first, and then we revisit the algorithmsin more challenging models. In other words, we first devise algorithms by makingstrong simplifying assumptions on the distributed environment, and then we discusshow to weaken those assumptions.We have tried to balance intuition and presentation simplicity on the one handwith rigor on the other hand. Sometimes rigor was affected, and this might not havebeen always on purpose. The focus here is rather on abstraction specifications andalgorithms, not on computability and complexity. Indeed, there is no theorem inthis book. Correctness arguments are given with the aim ofbetter understanding thealgorithms: they are not formal correctness proofs per se. PrefaceixOrganizationThe book has six chapters, grouped in two parts. The first part establishes thecommon ground:• In Chapter 1, we motivate the need for distributed programming abstractionsby discussing various applications that typically make use of such abstractions.The chapter also introduces the modular notation and the pseudo code used todescribe the algorithms in the book.• In Chapter 2, we present different kinds of assumptions about the underlyingdistributed environment. We introduce a family ofdistributed-system models forthis purpose. Basically, a model describes the low-level abstractions on whichmore sophisticated ones are built. These include process and communication linkabstractions. This chapter might be considered as a reference to other chapters.The remaining four chapters make up the second part of the book. Each chapter isdevoted to one problem, containing a broad class ofrelated abstractions and variousalgorithms implementing them. We will go fromthe simplerabstractions to the moresophisticated ones:• In Chapter 3, we introduce communication abstractions for distributed program-ming. They permit the broadcasting of a message to a group of processes andoffer diverse reliability guarantees for delivering messages to the processes. Forinstance, we discuss how to make sure that a message delivered to one processis also delivered to all other processes, despite the crash of the original senderprocess.• In Chapter 4, we discuss shared memory abstractions, which encapsulate simpleforms ofdistributedstorage objects, accessed by readand write operations. Thesecould be files in a distributed storage system or registers in the memory of amulti-processorcomputer. We cover methods for reading and writing data valuesby clients, such that a value stored by a set of processes can later be retrieved,even ifsome of the processes crash, have erased the value, or report wrong data.• In Chapter 5, we address the consensus abstraction through which a set of pro-cesses can decide on a common value, based on values that the processes initiallypropose. They must reach the same decision despite faulty processes, which mayhave crashed or may even actively try to prevent the others from reaching acommon decision.• In Chapter 6, we consider variants ofconsensus, which are obtained by extend-ing or modifying the consensus abstraction according to the needs of importantapplications. This includes total-order broadcast, terminating reliable broadcast,(non-blocking) atomic commitment, group membership, and view-synchronouscommunication.The distributed algorithms we study not only differ according to the actual ab-straction they implement, but also according to the assumptions they make on theunderlying distributed environment. We call the set of initial abstractions that analgorithm takes for granted a distributed-system model. Many aspects have a funda-mental impact on how an algorithm is designed, such as the reliability of the links, xPrefacethe degree of synchrony of the system, the severity of the failures, and whether adeterministic or a randomized solution is sought.In several places throughout the book, the same basic distributed program-ming primitive is implemented in multiple distributed-system models. The intentionbehind this is two-fold: first, to create insight into the specific problems encoun-tered in a particular system model, and second, to illustrate how the choice of amodel affects the implementation ofa primitive.A detailed study ofall chapters and the associated exercises constitutes a rich andthorough introduction to the field. Focusing on each chapter solely for the specifica-tions ofthe abstractions and their underlying algorithms in their simplest form, i.e.,for the simplest system model with crash failures only, would constitute a shorter,more elementary course. Such a course could provide a nice companion to a morepractice-oriented course on distributed programming.Changes Made for the Second EditionThis edition is a thoroughly revised version of the first edition. Most parts of thebook have been updated. But the biggest change was to expand the scope of thebook to a new dimension, addressing the key concept of security against maliciousactions. Abstractions andalgorithms in amodel ofdistributedcomputing that allowsadversarial attacks have become known as Byzantine fault-tolerance.The first edition ofthe book was titled “Introduction to Reliable Distributed Pro-gramming.” By adding one word (“secure”) to the title – and adding one co-author–the evolutionofthe bookreflects the developments in the field ofdistributedsystemsand in the real world. Since the first edition was published in 2006, it has becomeclear that most practical distributed systems are threatened by intrusions and thatinsiders cannot be ruled out as the source ofmalicious attacks. Building dependabledistributed systems nowadays requires an interdisciplinary effort, with inputs fromdistributed algorithms, security, and other domains.On the technical level, the syntax formodules and the names ofsome events havechanged, in order to add more structure for presenting the algorithms. A modulemay now exist in multiple instances at the same time within an algorithm, and everyinstance is named by a unique identifier for this purpose. We believe that this hassimplified the presentation ofseveral important algorithms.The first edition of this book contained a companion set of running examplesimplemented in the Java programming language, using the Appia protocol compo-sition framework. The implementation addresses systems subject to crash failuresand is available from the book’s online website.Online ResourcesMore information about the book, including the implementation of many protocolsfrom the first edition, tutorial presentation material, classroom slides, and errata, isavailable online on the book’s website at:http: //distributedprogramming. net PrefacexiReferencesWe have been exploring the world of distributed programming abstractions foralmost two decades now. The material of this book has been influenced by manyresearchers in the field of distributed computing. A special mention is due to LeslieLamport and Nancy Lynch for having posed fascinating problems in distributedcomputing, and to the Cornell school of reliable distributed computing, includ-ing¨Ozalp Babaoglu, Ken Birman, Keith Marzullo, Robbert van Rennesse, RickSchlichting, Fred Schneider, and Sam Toueg.Many other researchers have directly or indirectly inspired the material of thisbook. We did our best to reference their work throughout the text. All chaptersend with notes that give context information and historical references; our intentionbehind them is to provide hints for further reading, to trace the history of the pre-sented concepts, as well as to give credit to the people who invented and workedout the concepts. At the end of the book, we reference books on other aspects ofdistributed computing for further reading.AcknowledgmentsWe would like to express our deepest gratitude to our undergraduate and graduatestudents from the´Ecole Polytechnique F´ ed´ erale de Lausanne (EPFL) and the Uni-versity of Lisboa (UL), for serving as reviewers of preliminary drafts of this book.Indeed, they had no choice and needed to prepare for their exams anyway! But theywere indulgent toward the bugs and typos that could be found in earlier versions ofthe book as well as associated slides, and they provided us with useful feedback.Partha Dutta, Corine Hari, Michal Kapalka, Petr Kouznetsov, Ron Levy, MaximeMonod, Bastian Pochon, and Jesper Spring, graduate students from the School ofComputerand Communication Sciences ofEPFL, Filipe Ara´ ujo and Hugo Miranda,graduate students fromthe DistributedAlgorithms andNetworkProtocol(DIALNP)group at the Departamento de Inform´ atica da Faculdade de Ciˆ encias da Universi-dade de Lisboa (UL), Leila Khalil and Robert Basmadjian, graduate students fromthe Lebanese University in Beirut, as well as Ali Ghodsi, graduate student fromthe Swedish Institute of Computer Science (SICS) in Stockholm, suggested manyimprovements to the algorithms presented in the book.Several implementations for the “hands-on” part ofthe book were developed by,or with the help of, Alexandre Pinto, a key member of the Appia team, comple-mented with inputs from several DIALNP team members and students, includingNuno Carvalho, Maria Jo˜ ao Monteiro, and Lu´ ıs Sardinha.Finally, we would like to thank all our colleagues who were kind enough to com-ment on earlier drafts ofthis book. These include Felix Gaertner, Benoit Garbinato,and Maarten van Steen. xiiPrefaceAcknowledgments for the Second EditionWork on the second edition ofthis book started while Christian Cachin was on sab-batical leave from IBM Research at EPFL in 2009. We are grateful for the supportofEPFL and IBM Research.We thank again the students at EPFL and the University of Lisboa, who workedwith the book, forimprovingthe first edition. We extendourgratitude to the studentsat the Instituto Superior T´ ecnico (IST) of the Universidade T´ ecnica de Lisboa, atETH Z¨ urich, and at EPFL, who were exposed to preliminary drafts ofthe additionalmaterial included in the second edition, for their helpful feedback.We are grateful to many attentive readers of the first edition and to those whocommented on earlier drafts of the second edition, for pointing out problemsand suggesting improvements. In particular, we thank Zinaida Benenson, AlyssonBessani, Diego Biurrun, Filipe Crist´ ov˜ ao, Dan Dobre, Felix Freiling, Ali Ghodsi,Seif Haridi, Mat´ uˇ s Harvan, R¨ udiger Kapitza, Nikola Kneˇ zevi´ c, Andreas Knobel,Mihai Letia, Thomas Locher, Hein Meling, Hugo Miranda, Lu´ ıs Pina, MartinSchaub, and Marko Vukoli´ c.Christian CachinRachid GuerraouiLu´ ıs Rodrigues Contents1Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.1Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.2Distributed Programming Abstractions. . . . . . . . . . . . . . . . . . . . . . . . .1.2.1Inherent Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.2.2Distribution as an Artifact . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.3The End-to-End Argument . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.4Software Components . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.4.1Composition Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.4.2Programming Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111.4.3Modules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131.5Classes ofAlgorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161.6Chapter Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17113467882Basic Abstractions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192.1Distributed Computation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202.1.1Processes and Messages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202.1.2Automata and Steps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202.1.3Safety and Liveness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222.2Abstracting Processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242.2.1Process Failures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242.2.2Crashes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242.2.3Omissions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262.2.4Crashes with Recoveries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262.2.5Eavesdropping Faults . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282.2.6Arbitrary Faults . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292.3Cryptographic Abstractions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302.3.1Hash Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302.3.2Message-Authentication Codes (MACs) . . . . . . . . . . . . . . . . . 302.3.3Digital Signatures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 312.4Abstracting Communication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322.4.1Link Failures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332.4.2Fair-Loss Links . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 342.4.3Stubborn Links . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352.4.4Perfect Links . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 372.4.5Logged Perfect Links . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38xiii xivContents2.4.62.4.7Timing Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 442.5.1Asynchronous System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 442.5.2Synchronous System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 452.5.3Partial Synchrony . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47Abstracting Time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 482.6.1Failure Detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 482.6.2Perfect Failure Detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 492.6.3Leader Election. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 512.6.4Eventually Perfect Failure Detection . . . . . . . . . . . . . . . . . . . . 532.6.5Eventual Leader Election. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 562.6.6Byzantine Leader Election . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60Distributed-System Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 632.7.1Combining Abstractions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 632.7.2Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 642.7.3Quorums . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 652.7.4Measuring Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 682.10 Chapter Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71Authenticated Perfect Links . . . . . . . . . . . . . . . . . . . . . . . . . . . 40On the Link Abstractions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 432.52.62.72.82.93Reliable Broadcast . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 733.1Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 733.1.1Client–Server Computing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 733.1.2Multiparticipant Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 743.2Best-Effort Broadcast . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 753.2.1Specification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 753.2.2Fail-Silent Algorithm: Basic Broadcast . . . . . . . . . . . . . . . . . . 763.3Regular Reliable Broadcast . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 773.3.1Specification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 773.3.2Fail-Stop Algorithm: Lazy Reliable Broadcast . . . . . . . . . . . . 783.3.3Fail-Silent Algorithm: Eager Reliable Broadcast . . . . . . . . . . 793.4Uniform Reliable Broadcast. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 813.4.1Specification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 813.4.2Fail-Stop Algorithm:All-Ack Uniform Reliable Broadcast . . . . . . . . . . . . . . . . . . . . 823.4.3Fail-Silent Algorithm:Majority-Ack Uniform Reliable Broadcast . . . . . . . . . . . . . . . 843.5Stubborn Broadcast . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 853.5.1Specification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 853.5.2Fail-Recovery Algorithm: Basic Stubborn Broadcast. . . . . . . 863.6Logged Best-Effort Broadcast . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 873.6.1Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 873.6.2Specification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 883.6.3Fail-Recovery Algorithm: Logged Basic Broadcast . . . . . . . . 89 Contentsxv3.7Logged Uniform Reliable Broadcast. . . . . . . . . . . . . . . . . . . . . . . . . . . 903.7.1Specification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 903.7.2Fail-Recovery Algorithm:Logged Majority-Ack Uniform Reliable Broadcast . . . . . . . . 90Probabilistic Broadcast . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 923.8.1The Scalability ofReliable Broadcast . . . . . . . . . . . . . . . . . . . 923.8.2Epidemic Dissemination . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 933.8.3Specification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 943.8.4Randomized Algorithm: Eager Probabilistic Broadcast . . . . . 943.8.5Randomized Algorithm: Lazy Probabilistic Broadcast . . . . . 97FIFO and Causal Broadcast . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1003.9.1Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1013.9.2FIFO-Order Specification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1013.9.3Fail-Silent Algorithm: Broadcast with Sequence Number . . . 1013.9.4Causal-Order Specification . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1033.9.5Fail-Silent Algorithm: No-Waiting Causal Broadcast . . . . . . 1043.9.6Fail-Stop Algorithm: Garbage-Collection ofCausal Past . . . 1063.9.7Fail-Silent Algorithm: Waiting Causal Broadcast . . . . . . . . . . 1083.10 Byzantine Consistent Broadcast . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1103.10.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1103.10.2 Specification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1113.10.3 Fail-Arbitrary Algorithm:Authenticated Echo Broadcast . . . . . . . . . . . . . . . . . . . . . . . . . 1123.10.4 Fail-Arbitrary Algorithm: Signed Echo Broadcast . . . . . . . . . 1143.11 Byzantine Reliable Broadcast . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1163.11.1 Specification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1173.11.2 Fail-Arbitrary Algorithm:Authenticated Double-Echo Broadcast . . . . . . . . . . . . . . . . . . 1173.12 Byzantine Broadcast Channels. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1203.12.1 Specifications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1203.12.2 Fail-Arbitrary Algorithm: Byzantine Consistent Channel . . . 1223.12.3 Fail-Arbitrary Algorithm: Byzantine Reliable Channel . . . . . 1233.13 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1243.14 Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1263.15 Chapter Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1343.83.94Shared Memory. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1374.1Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1384.1.1Shared Storage in a Distributed System . . . . . . . . . . . . . . . . . . 1384.1.2Register Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1384.1.3Completeness and Precedence . . . . . . . . . . . . . . . . . . . . . . . . . 1414.2(1, N) Regular Register . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1424.2.1Specification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1424.2.2Fail-Stop Algorithm:Read-One Write-All Regular Register . . . . . . . . . . . . . . . . . . . 144 xviContents4.2.3Fail-Silent Algorithm:Majority Voting Regular Register . . . . . . . . . . . . . . . . . . . . . . . 146(1, N) Atomic Register . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1494.3.1Specification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1494.3.2Transformation:From (1, N) Regular to (1, N) Atomic Registers. . . . . . . . . . 1514.3.3Fail-Stop Algorithm:Read-Impose Write-All (1, N) Atomic Register . . . . . . . . . . 1564.3.4Fail-Silent Algorithm:Read-Impose Write-Majority (1, N) Atomic Register . . . . . . 157(N, N) Atomic Register . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1594.4.1Multiple Writers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1594.4.2Specification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1604.4.3Transformation:From (1, N) Atomic to (N, N) Atomic Registers . . . . . . . . . 1614.4.4Fail-Stop Algorithm:Read-Impose Write-Consult-All (N, N) Atomic Reg.. . . . . . 1654.4.5Fail-Silent Algorithm:Read-Impose Write-Consult-Majority (N, N)Atomic Reg. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167(1, N) Logged Regular Register . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1704.5.1Precedence in the Fail-Recovery Model . . . . . . . . . . . . . . . . . 1704.5.2Specification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1704.5.3Fail-Recovery Algorithm: Logged Majority Voting . . . . . . . . 172(1, N) Byzantine Safe Register . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1754.6.1Specification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1764.6.2Fail-Arbitrary Algorithm: Byzantine Masking Quorum. . . . . 177(1, N) Byzantine Regular Register . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1794.7.1Specification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1794.7.2Fail-Arbitrary Algorithm:Authenticated-Data Byzantine Quorum . . . . . . . . . . . . . . . . . . 1804.7.3Fail-Arbitrary Algorithm:Double-Write Byzantine Quorum. . . . . . . . . . . . . . . . . . . . . . . 182(1, N) Byzantine Atomic Register . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1884.8.1Specification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1894.8.2Fail-Arbitrary Algorithm:Byzantine Quorum with Listeners . . . . . . . . . . . . . . . . . . . . . . 189Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1944.10 Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1954.11 Chapter Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2004.34.44.54.64.74.84.95Consensus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2035.1Regular Consensus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2045.1.1Specification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2045.1.2Fail-Stop Algorithm: Flooding Consensus . . . . . . . . . . . . . . . 2055.1.3Fail-Stop Algorithm: Hierarchical Consensus . . . . . . . . . . . . . 208 Contentsxvii5.2Uniform Consensus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2115.2.1Specification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2115.2.2Fail-Stop Algorithm: Flooding Uniform Consensus . . . . . . . . 2125.2.3Fail-Stop Algorithm: Hierarchical Uniform Consensus . . . . . 213Uniform Consensus in the Fail-Noisy Model . . . . . . . . . . . . . . . . . . . . 2165.3.1Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2165.3.2Epoch-Change . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2175.3.3Epoch Consensus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2205.3.4Fail-Noisy ...

    关注我们

  • 新浪微博
  • 关注微信公众号

  • 打印亚博足球app下载
  • 复制文本
  • 下载Introduction to Reliable and Secure Distributed Programming.XDF
  • 您选择了以下内容