搜索
1分布式系统2008春季学期期末考试北京大学计算机系，2008年6月9日院系：学号：姓名：一、概念题（共50分）1.Totally-orderedmulticast(5pt)Amulticastoperationbywhichallmessagesaredeliveredinthesameordertoeachreceiver.2.Distributedsystem(5pt)Adistributedsystemisacollectionofindependentcomputersthatappearstoitsusersasasinglecoheretsystem.Youknowyouhave[adistributedsystem]whenthecrashofacomputeryou'veneverheardofstopsyoufromgettinganyworkdone.“(--LeslieLamport)3.Availability,Reliability(5pt)Availability:Readinessforusage。说明系统已准备好，马上就可以使用。通常，它指在任何给定的时刻，系统都可以正确地操作，可根据用户的行为来执行它的功能。换句话说，高度可用的系统在任何给定的时刻都能及时地工作。Reliability:Continuityofservicedelivery。指系统可以无故障地持续运行。与可用性相反，可靠性是根据时间间隔而不是任何时刻来进行定义的。4.Omissionfailures(5pt)Acomponentfailstorespondtoincomingrequests.Receiveomission:Failstoreceiveincomingmessages.Sendomission:Failstosendmessages5.BullyAlgorithm(5pt)Whenanyprocessnoticesthatthecoordinatorisnolongerrespondingtorequests,itinitiatesanelection.Aprocess,P,holdsanelectionasfollows:1)PsendsanELECTIONmessagetoallprocesseswithhighernumbers.2)Ifnooneresponds,Pwinstheelectionandbecomescoordinator.3)Ifoneofthehigher-upsanswers,ittakesover.P’sjobisdone.26.close-to-opencacheconsistency(5pt)TheNFSstandardrequiresclientstomaintainclose-to-opencachecoherencywhenmultipleclientsaccessthesamefiles.Thismeansflushingallfiledataandmetadatachangeswhenaclientclosesafile,andimmediatelyandunconditionallyretrievingafile'sattributeswhenitisopenedviatheopen()systemcallAPI.Inthisway,changesmadebyoneclientappearassoonasafileisopenedonanyotherclient.7.Primary-backupprotocols(5pt)Protocolsthatallowprocessestoperformreadoperationsonalocallyavailablecopy,butshouldforwardwriteoperationstoa(fixed)primarycopy.8.Securechannals(5pt)Theybothknowwhoisontheotherside(authenticated).Theybothknowthatmessagescannotbetamperedwith(integrity).Theybothknowmessagescannotleakaway(confidentiality).9.Cloudcomputing(5pt)ApopularphrasethatisshorthandforapplicationsthatweredevelopedtoberichInternetapplicationsthatrunontheInternet(orcloud).Inthecloudcomputingparadigm,softwarethatistraditionallyinstalledonpersonalcomputersisshiftedorextendedtobeaccessibleviatheInternet.Thesecloudapplicationsorcloudappsutilizemassivedatacentersandpowerfulserversthathostwebapplicationsandwebservices.TheycanbeaccessedbyanyonewithasuitableInternetconnectionandastandardwebbrowser.10.MapReduce(5pt)MapReduce是一个编程模型和用来处理和产生大规模数据集。用户指定一个映射函数处理一个键/值对来产生中间的键/值对集合，还指定一个缩小函数来合并所有的与同一中间键相关的中间值。用这个函数风格写的程序自动并行化并且在一大集群机器上执行。运行时系统关心分割输入数据的细节，通过一系列的机器调度程序的执行，处理机器故障，以及管理所需的机器内部通信。这使得没有任何并行和分布式系统经验的程序员能够容易地利用一个大的分布式系统的资源。3二、简答题（共50分）1．1)Explainthevaluesforthefingertableofnode9inthefollowingChordDHT-basedsystem.2)Assumenode4isrequestedtolookupkey29.Howisthiskeyresolved?Youmustexplainyouranswer!(10pt)FPp[i]=succ(p+2i−1),withi≥1.Inthisexample,FP9[1]=succ(9+20)=succ(10)=11.Likewise,FP9[2]=succ(9+2)=succ(11)=11,andsoon.Node4willfirstlookfortheentrythatsatisfiesFT4[j]≤29FT4[j+1],whichinthisexampleisentry5,whereweneedtoapplymoduloarithmetic.Therefore,therequestisforwardedtonode20,whichwillthen,forsimilarreasons,forwardittonode28.Node28willfindthat29liesbetween28(itsownID)andFT28[1],sothatitsendstherequesttonode1.Thelatterisresponsibleforkey29.2．Explaintheprincipleofanepidemicprotocol.(5pt)YouranswershouldatleastincludethataprocessPrandomlyselectsanotherprocessQtoexchangenewdataitems,followingeitherapull,push,orpush-pullprotocol.43.Whyisthefollowingdatastorenotsequentiallyconsistent?Isitcausallyconsistent?Besuretoexplainyouranswer.(5pt)P1:W(x)a---------------------------------------------P2:W(x)b---------------------------------------------P3:R(x)bR(x)a---------------------------------------------P4:R(x)aR(x)bItisnotsequentiallyconsistentbecauseP3andP4arereadingtheeffectsofconcurrentwrites(byrespectivelyP1andP2)indifferentorders.Itiscausallyconsistentbecausetherearenocausalrelationshipsthatneedtobeobeyed.4.Whatisakfault-tolerantgroup,andhowdoeskdependonfailuresemantics?(5pt)Akfault-tolerantgroupofprocessesisagroupthatcontinuestooperateasexpectedeveninthepresenceofkfailingprocesses.Inthecaseofcrash/performancefailures,youneedk+1processes;whendealingwithByzantinefailuresbutprocessesdonotcommunicatewitheachother,youneed2k+1memberssothatyoucanperformmajorityvoting.Withcommunicationbetweenprocesses,3k+1membersareneeded.5.ExplainthebasicPaxosprotocol(10pt)ThisprotocolisthemostbasicofthePaxosfamily;itisnottheprotocolwhichistypicallyimplementedinadeployment(seeMulti-Paxos).EachinstanceoftheBasicPaxosprotocoldecidesonasingleoutputvalue.Theprotocolproceedsoverseveralrounds,asuccessfulroundhastwophases:Phase1a:PrepareAProposer(theleader)selectsaproposalnumberNandsendsaPreparemessagetoaQuorumofAcceptors.Phase1b:Promise5IftheproposalnumberNislargerthananypreviousproposal,theneachAcceptorpromisesnottoacceptproposalslessthanN,andsendsthevalueitlastacceptedforthisinstancetotheProposer(theleader).Otherwiseadenialissent(Nak).Phase2a:Accept!IftheProposerreceivesresponsesfromaQuorumofAcceptors,itmaynowChooseavaluetobeagreedupon.IfanyoftheAcceptorshavealreadyacceptedavalue,theleader