分布式系统课件：chapter7

ConsistencyandReplicationChapter77.1.1ReasonsforReplication:1)reliability2)performanceCaveatGaininperformanceCostofincreasedbandwidthformaintainingreplicationIntroduction(7.1)Dataaregenerallyreplicatedtoenhancereliabilityorimproveperformanceindistributedsystemorparallelcomputerssystem.Howtokeepreplicasconsistentisoneofthemajorproblems(whenonecopyisupdated,weneedtoensurethattheothercopiesareupdatedaswell)7.1.2ObjectReplication1)Adistributedremoteobjectissharedbymultipleclients-------howtoprotecttheobjectagainstsimultaneousaccessbymultipleclients.2)Adistributedremoteobjectisreplicatedatdifferentnode-------howtoensurethatconcurrentinvocationsareperformedinthecorrectorderateachofthereplicas.Introduction(7.1)ObjectReplication(1)Organizationofadistributedremoteobjectsharedbytwodifferentclients.ObjectReplication(2)Aremoteobjectcapableofhandlingconcurrentinvocationsonitsown.AremoteobjectforwhichanobjectadapterisrequiredtohandleconcurrentinvocationsObjectReplication(2)Fig(a):Forexample,javaobject----whichcanbeconstructedasamonitorbydeclaringtheobject’smethodtobesynchronized.publicsynchronizedvoidenter(Objectitem){ while(count==BUFFER_SIZE) Thread.yield(); ++count; buffer[in]=item; in=(in+1)%BUFFER_SIZE;}ObjectReplication(2)ObjectReplication(3)Adistributedsystemforreplication-awaredistributedobjects.（SOS，Globeetc.）Adistributedsystemresponsibleforreplicamanagement(CORBAetc.)ObjectReplication(3)7.1.3ReplicationasScalingTechniquePlacingcopiesofdataandobjectsclosetotheprocessesusingthemcanimproveperformancethroughreductionofaccesstime,andthussolvescalabilityproblems.Replicationandcachingforperformancearewidelyappliedasscalingtechniques.dilemmaproblem:Ontheonehand,scalabilityproblemcanbealleviatedbyapplyingreplicationandcaching,leadingtoimprovedperformance.Ontheotherhand,tokeepallcopiesconsistentgenerallyrequiresglobalsynchronization,whichisinherentlycostlyintermsofperformance.ObjectReplication(3)1.DATA-CENTRICCONSISTENCYMODELS.2.CLIENT-CENTRICCONSISTENCYMODELS两种一致性模型DATA-CENTRICCONSISTENCYMODELS(7.2)Adatastoremaybephysicallydistributedacrossmultiplemachines-----(distributed)sharedmemory,(distributed)shareddatabase,ora(distributed)filesystem.Adataoperationisclassifiedas:writeoperationreadoperation.Inparticular,eachprocessthatcanaccessdatafromthestoreisassumedtohavealocal(ornearby)copyavailableoftheentirestore.Writeoperationsarepropagatedtotheothercopies.Data-CentricConsistencyModelsThegeneralorganizationofalogicaldatastore,physicallydistributedandreplicatedacrossmultipleprocesses.Data-CentricConsistencyModelsAconsistencymodelisessentiallyacontractbetweenprocess(read/write)andthedatastore.Itsaysthatifprocessesagreetoobeycertainrules,thestorepromisestoworkcorrectly.Data-CentricConsistencyModelsIntheabsenceofaglobalclock,itisdifficulttodefinepreciselywhichwriteoperationisthelastone,soweneedtoprovidedefinitions,leadingtoarangeofconsistencymodels.Eachmodeleffectivelyrestricts（限定）thevaluesthatareadoperationonadataitemcanreturn.StrictConsistency(7.2.1)strictconsistency:

Anyreadonadataitemxreturnsavaluecorrespondingtotheresultofthemostrecentwriteonx.例：单一处理机遵守严格一致性，有如下程序：A=1；A=2；PRINT（A）；打印1或2以外的任何值是编程者无法理解的。StrictConsistency(7.2.1)假设在DCS中，有如下情形(t1<t2)：NodeANode

BP1x

…

read(B:xatt1)P2

…1nsWrite(B:xatt2)若按严格一致性，A都应该读出原来的值。然而，若T2-T1=1ns(1纳秒=0.000000001秒)，而机器距离3米，从A到B传送读操作并使之先于写操作，信号则必须以十倍光速的速度传递，与爱因斯坦相对论矛盾。StrictConsistency(7.2.1)Behavioroftwoprocesses,operatingonthesamedataitem.(a)Astrictlyconsistentstore.(b)Astorethatisnotstrictlyconsistent.StrictConsistency(7.2.1)严格一致性的存储器，写操作在任一时刻对所有进程都是可见的，系统维护一个绝对全局时间。一旦存储器中的值改变，不管读写之间的事件间隔多小，不管哪个进程执行读操作，也不管进程在何处，以后读出的都是新更改的值。同样，不管后面的写操作有多迅速，执行读操作仍应读出原来的值。严格一致性是理想的编程模式，在分布式系统中，这几乎不可能实现。StrictConsistency(7.2.1)wewillrelaxthismodelbyconsideringtimeintervalsinsteadofabsolutetime,anddefinepreciselywhatisacceptablebehaviorforconflictingoperationsinadistributedsystem.LinearizabilityandSequentialConsistency(7.2.2)Sequentialconsistent(顺序一致)是比严格一致稍弱的模式，Lamport（1979）首先定义了顺序一致性应符合的条件：Theresultofanyexecutionisthesameasifthe(readandwrite)operationbyallprocessesonthedatastorewereexecutedinsomesequentialorderandtheoperationsofeachindividualprocessappearinthissequenceintheorderspecifiedbyitsprogram.

任何操作的执行结果都应该与所有的进程以程序规定的顺序，好象在各自单个进程执行的顺序一致。表明:对于在不同机器上并发运行的进程，任何有效的交错都是可以接受的行为，但所有进程必须遵守同一访问顺序。LinearizabilityandSequentialConsistency(7.2.2)Asequentiallyconsistentdatastore.Adatastorethatisnotsequentiallyconsistent.顺序一致存储器不保证读返回的值是1ns、1ms甚至1分钟以前另一进程写入的。它只保证所有进程以相同的顺序看见存储器访问。如图a)，或许会得到图b)的结果。如果缺少明确的同步操作，则结果是不确定的。LinearizabilityandSequentialConsistency(2)Threeconcurrentlyexecutingprocesses.ProcessP1ProcessP2ProcessP3x=1;print(y,z);y=1;print(x,z);z=1;print(x,y);LinearizabilityandSequentialConsistency(2)6个独立的语句，有720(6！)种可能的执行顺序。从x=1开始考虑的顺序有120(5！)种,其中只有1/4（y=1/z=1在print()前,各1/2）即30个是有效的。另外30个有效顺序是以y=1开头的，还有30个以z=1开头。共有90个有效执行顺序。LinearizabilityandSequentialConsistency(3)Fourvalidexecutionsequencesfortheprocessesofthepreviousslide.Theverticalaxisistime.x=1;print((y,z);y=1;print(x,z);z=1;print(x,y);Prints:001011Signature:

001011(a)x=1;y=1;print(x,z);print(y,z);z=1;print(x,y);Prints:101011Signature:

101011(b)y=1;z=1;print(x,y);print(x,z);x=1;print(y,z);Prints:010111Signature:010111(c)y=1;x=1;z=1;print(x,z);print(y,z);print(x,y);Prints:111111Signature:111111(d)LinearizabilityandSequentialConsistency(3)Linearizabilityconsistency(weakerthanstrictconsistency,strongerthansequentialconsistency):Theresultofanyexecutionisthesameasifthe(readandwrite)operationbyallprocessesonthedatastorewereexecutedinsomesequentialorderandtheoperationsofeachindividualprocessappearinthissequenceintheorderspecifiedbyitsprogram.Inaddition,iftsOP1(x)<tsOP2(y),thenoperationOP1(xshouldprecedeOP2(y)inthissequence.(与顺序一致性同，但是应满足时间戳的顺序)(LettsOP1(x)denotethetimestampassignedtooperationOPthatisperformedondataitemx)LinearizabilityandSequentialConsistency(3)Acommonapproachtoformallyexpresssequentialconsistencyisasfollows(Ahamadetal.,1992;Mizunoetal.,1995).EachprocessPihasanassociatedexecutionEi,whichisasequenceofreadandwriteoperationsbyprocessPiperformedonadatastoreS.ThissequenceadherestotheprogramorderassociatedwithPi.Forexample.

E1:W1(x)a;E2:W2(x)b;E3:R3(x)b,R3(x)a;E4:R4(x)b,R4(x)a;ThenH=W1(x)b,R3(x)b,R4(x)b,W2(x)a,R3(x)a,R4(x)aCasualConsistency(7.2.3)Necessarycondition:Writesthatarepotentiallycasuallyrelatedmustbeseenbyallprocessesinthesameorder.Concurrentwritesmaybeseeninadifferentorderondifferentmachines.有因果关系的写操作，相关进程看到是一致的。CasualConsistency(2)Thissequenceisallowedwithacasually-consistentstore,butnotwithsequentiallyorstrictlyconsistentstore.(W2(x)bandW1(x)careconcurrent).有因果关系写无因果关系写CasualConsistency(3)Aviolationofacasually-consistentstore（不满足）.Acorrectsequenceofeventsinacasually-consistentstore.Implement:requiringkeepingtrackofwhichprocesseshaveseenwhichwrites(实现因果一致性需要由记录来跟踪哪个进程看到哪个写操作。这要建立和维护一个依赖图：即一个操作依赖于其它什么操作)。FIFOConsistency(orPRAM)(7.2.4)NecessaryCondition:

Writesdonebyasingleprocessareseenbyallotherprocessesintheorderinwhichtheywereissued,butwritesfromdifferentprocessesmaybeseeninadifferentorderbydifferentprocesses(一个进程的写操作可以被其它进程以指定的顺序接收到，但不同进程的写操作在不同进程看来次序可以是不同的).

PRAM一致性由LIPTON和SANDBERG（1988）提出，PRAM代表管道RAM，由于一个进程的写操作可以是流水线的，即进程不必在开始下一个操作之前等待一操作结束。只要求一个进程以一定顺序的写操作被所有进程看到。FIFOConsistencyAvalidsequenceofeventsofFIFOconsistency它不保证不同进程看到的写操作顺序是一致的，除非是一个源的一个或多个写操作，才必须按次序到达，就好象在管道中。由不同进程产生的写操作是并发的。

themodelcanbeimplementedbysimplytaggingeachwriteoperationwitha(process,sequencenumber)pair,andperformingwritesperprocessintheorderoftheirsequencenumber.指定顺序FIFOConsistencyStatementexecutionasseenbythethreeprocessesfromthepreviousslide.Thestatementsinboldaretheonesthatgeneratetheoutputshown.(结果只受本进程顺序影响)x=1;print(y,z);y=1;print(x,z);z=1;print(x,y);Prints:00(a)x=1;y=1;print(x,z);print(y,z);z=1;print(x,y);Prints:10(b)y=1;print(x,z);z=1;print(x,y);x=1;print(y,z);Prints:01(c)FIFOConsistency在FIFO一致下,不同进程所看到的语句执行顺序不同,如图(a)显示P1怎样看到事件，而(b)显示P2所看到的，(C)则是P3所见。对于顺序一致存储器,三个不同显示是不允许的。如果使三个进程的输出顺序相接,得到结果为001001，这在顺序一致性下是不可能的。两者的关键不同在于：前者尽管未确定语句（和存储器访问）的执行顺序,但至少所有进程都遵守共同的顺序。后者就不遵守。不同进程看到的操作顺序不同。FIFOConsistencyTwoconcurrentprocesses.GOODMAN（1989）提出了一种略微不同但仍支持PRAM一致的存储器形式。如上述例子中，在顺序一致下只能出现三种结果之一:1）P1被KILL;2）P2被KILL;3）两者都不被KILL。但是，在FIFO一致下,可能两个进程都被KILL，即若P1在看到P2中B赋值之前读取B,P2在看到P1中A赋值之前读取A。ProcessP1ProcessP2x=1;if(y==0)kill(P2);y=1;if(x==0)kill(P1);WeakConsistency(7.2.5)尽管FIFO一致性比强模式的更好,但它仍对很多应用程序做了不必要的限制，即要求一个进程以一定顺序的写操作被所有进程看到，并非所有应用程序要看到所有写操作。比如在临界区中一个进程循环读写被复制数据。只需让进程完成临界区操作以后,将最后结果发送到各处,而不用太关心甚至不用关心中间结果是否也顺序发送到所有结点。WeakConsistency(7.2.5)Properties(Duboisetal.1986):AccessestosynchronizationvariablesassociatedwithadatastorearesequentiallyconsistentNooperationonasynchronizationvariableisallowedtobeperformeduntilallpreviouswriteshavebeencompletedeverywhereNoreadorwriteoperationondataitemsareallowedtobeperformeduntilallpreviousoperationstosynchronizationvariableshavebeenperformed.WeakConsistency(7.2.5)1．对同步变量的访问是顺序一致的(所有进程以相同顺序看到对同步变量的访问)；2．在所有先前的写操作完成之前,不能访问同步变量(同步访问开始前。在更新共享数据后做同步操作，进程可将新值传遍所有存储器)；3．在先前所有同步变量的访问完成前，不能访问（读或写）数据(访问一般非同步变量，不管是读是写，只有在所有前序的同步操作结束后方可进行。在读共享数据前做同步操作，可以保证进程读到最新值)；它是对一组操作的一致性约束,而不是单独的读或写。当基本上以簇的形式（短时间内有很多访问，每一访问时间都不长）访问共享变量时，这个模型很有用。WeakConsistencyAprogramfragmentinwhichsomevariablesmaybekeptinregisters.若允许另外一个进程可随意读取存储器的话，只需让编译器写一标志位说明存储器没有更新。若另一进程访问A，它会在标志位上等待。该思想已经得到许多应用，例如：一个优化的编译器可以在寄存器中计算a和b，并保存片刻，不更新存储器，只有当调用函数f后才将a和b当前值返还存储器。inta,b,c,d,e,x,y; /*variables*/

int*p,*q; /*pointers*/

intf(int*p,int*q); /*functionprototype*/a=x*x; /*astoredinregister*/

b=y*y; /*baswell*/

c=a*a*a+b*b+a*b; /*usedlater*/

d=a*a*c; /*usedlater*/

p=&a; /*pgetsaddressofa*/

q=&b /*qgetsaddressofb*/

e=f(p,q) /*functioncall*/WeakConsistencyAvalidsequenceofeventsforweakconsistency.Aninvalidsequenceforweakconsistency.ReleaseConsistency(7.2.6)弱一致性存在的问题，即当访问同步变量时，存储器并不知道这是因为进程已完成对共享变量的写操作还是要开始读共享变量。若存储器能够区分进入还是离开临界区的话，应用起来会更有效。因此，引入释放一致性（Gharachorlooetal.,1990），这里需要提供两种操作：获取（acquire）——访问用于通知存储器系统临界区已就绪。释放(release)——访问表明临界区刚退出。程序员都需要在程序中编写明确的代码说明何时做这些操作。ReleaseConsistency(7.2.6)Avalideventsequenceforreleaseconsistency.ReleaseConsistencyRules:Beforeareadorwriteoperationonshareddataisperformed,allpreviousacquiresdonebytheprocessmusthavecompletedsuccessfully.Beforeareleaseisallowedtobeperformed,allpreviousreadsandwritesbytheprocessmusthavecompletedAccessestosynchronizationvariablesareFIFOconsistent(sequentialconsistencyisnotrequired).ReleaseConsistency遵守以下规定：1．在访问共享变量前，进程所有先前的获取访问都必须成功地完成；2．在允许释放访问前，进程先前的所有读写操作都必须结束；3．获取访问和释放访问必须是FIFO一致的。ReleaseConsistency释放一致性在DSM中的简单应用（为多处理机而设计的）。为了执行获取操作，进程将消息发送给同步管理者，要求A在一特殊的锁定上执行获取访问。在没有竞争时，请求获准，获取访问完成。对共享数据的读写就可以在本地开始了。它们不用传送到其他机器。当执行释放访问时，修改过的数据被传送到使用它们的机器上。当每个机器确认收到数据后，同步管理者被告知可以执行释放了。EntryConsistency(7.2.7)Conditions:Anacquireaccessofasynchronizationvariableisnotallowedtoperformwithrespecttoaprocessuntilallupdatestotheguardedshareddatahavebeenperformedwithrespecttothatprocess.Beforeanexclusivemodeaccesstoasynchronizationvariablebyaprocessisallowedtoperformwithrespecttothatprocess,nootherprocessmayholdthesynchronizationvariable,noteveninnonexclusivemode.Afteranexclusivemodeaccesstoasynchronizationvariablehasbeenperformed,anyotherprocess'snextnonexclusivemodeaccesstothatsynchronizationvariablemaynotbeperformeduntilithasperformedwithrespecttothatvariable'sowner.

EntryConsistency(7.2.7)1．只有某一进程的保护共享变量全部被更新以后，该进程才允许执行同步变量的获取访问(当进程执行获取访问时，所有被保护数据的远程修改都必须是可见的)；2．在一进程以互斥模式访问该进程的同步变量之前，不允许其它进程持有此同步变量(在更新一个共享变量前，进程必须以互斥方式进入临界区，以确定没有其它进程同时更新它)；3．在结束互斥模式下对一个同步变量的访问后，任意其它进程必须与该变量的拥有者核查，才能试图以非互斥模式访问该同步变量(若进程试图以非互斥方式进入临界区，它必须与保护此临界区的同步变量的拥有者核查，以获得被保护共享变量的最新拷贝)。EntryConsistencyAvalideventsequenceforentryconsistency.SummaryofConsistencyModelsConsistencymodelsnotusingsynchronizationoperations.Modelswithsynchronizationoperations.ConsistencyDescriptionStrictAbsolutetimeorderingofallsharedaccessesmatters.LinearizabilityAllprocessesmustseeallsharedaccessesinthesameorder.Accessesarefurthermoreorderedaccordingtoa(nonunique)globaltimestampSequentialAllprocessesseeallsharedaccessesinthesameorder.AccessesarenotorderedintimeCausalAllprocessesseecausally-relatedsharedaccessesinthesameorder.FIFOAllprocessesseewritesfromeachotherintheordertheywereused.Writesfromdifferentprocessesmaynotalwaysbeseeninthatorder(a)ConsistencyDescriptionWeakShareddatacanbecountedontobeconsistentonlyafterasynchronizationisdoneReleaseShareddataaremadeconsistentwhenacriticalregionisexitedEntryShareddatapertainingtoacriticalregionaremadeconsistentwhenacriticalregionisentered.(b)Client-CentricConsistencyModels(7.3)Inthissection,wetakealookataspecialclassofdistributeddatastores,whicharecharacterizedbythelackofsimultaneousupdates,orwhensuchupdateshappen,theycaneasilyberesolved.Client-centricconsistencyprovidesguaranteesforasingleclientconcerningtheconsistencyofaccessestoadatastorebythatclient.NoguaranteesaregivenconcerningconcurrentaccessesbydifferentclientsEventualConsistency(7.3.1)Theprincipleofamobileuseraccessingdifferentreplicasofadistributeddatabase.EventualConsistencyTherearemanycasesof(large-scale)distributedandreplicateddatabasesthattoleratearelativelyhighdegreeofinconsistency.Theyhaveincommonthatifnoupdatestakeplaceforalongtime,allreplicaswillgraduallybecomeconsistent.Thisofconsistencyiscalledeventualconsistency.Forexample,DNS,WWW,etc.（WS(xi[t])表示在时刻t，本地副本Li上的一系列write操作的结果，t可以省略）。Monotonic-ReadConsistency(7.3.2)Condition:Ifaprocessreadsthevalueofadataitemx,anysuccessivereadoperationonxbythatprocesswillalwaysreturnthatsamevalueoramorerecentvalue.

(toguaranteethatifaprocesshasseenavalueofxattimet,itwillneverseeanolderversionofxatalatertime).MonotonicReadsThereadoperationsperformedbyasingleprocessPattwodifferentlocalcopiesofthesamedatastore.Amonotonic-readconsistentdatastore;Adatastorethatdoesnotprovidemonotonicreads;Monotonic-WriteConsistence(7.3.3)Condition:Awriteoperationbyaprocessonadataitemxiscompletedbeforeanysuccessivewriteoperationonxbythesameprocess.MonotonicWritesThewriteoperationsperformedbyasingleprocessPattwodifferentlocalcopiesofthesamedatastoreAmonotonic-writeconsistentdatastore.Adatastorethatdoesnotprovidemonotonic-writeconsistency(missingW(x1)).Read-Your-WritesConsistency(7.3.4)Condition:Theeffectofawriteoperationbyaprocessonadataitemxwillalwaysbeseenbyasuccessivereadoperationonxbythesameprocess.Read-Your-WritesConsistency(7.3.4)Adatastorethatprovidesread-your-writesconsistency.Adatastorethatdoesnot(W(x1)notbeenpropagatedtoL2).Writes-Follow-ReadsConsistency(7.3.5)Condition:Awriteoperationbyaprocessonadataitemxfollowingapreviousreadoperationonxbythesameprocess,isguaranteedtotakeplaceonthesameoramorerecentvalueofthatwasread.(Inotherwords,anysuccessivewriteoperationbyaprocessonadataitemxwillbeperformedonacopyofxthatisuptodatewiththevaluemostrecentlyreadbythatprocess)

Whichcanbeusedtoguaranteethatusersofanetworknewsgroupseeapostingofareactiontoanarticleonlyaftertheyhaveseentheoriginalarticle.WritesFollowReadsAwrites-follow-readsconsistentdatastoreAdatastorethatdoesnotprovidewrites-follow-readsconsistencyImplementation(7.3.6)Anativeimplementation:Eachwriteoperationisassignedagloballyuniqueidentifierbytheserverthatacceptstheoperationforthefirsttime(initiatedbyserver).Foreachclient,wekeeptrackoftwosetsofwriteidentifiers.Thereadset={thewriteidentifiersrelevantforthereadoperationsperformedbyaclient}.Forexample:Pid-read-set={wid1,wid2,……widn}Thewriteset={theidentifiersofthewritesperformedbytheclient}.Implementation(7.3.6)monotonic-readconsistency:

whenaclientperformsareadoperationataserver,thatserverishandedtheclient’sreadsettocheckwhetheralltheidentifiedwriteshavetakenplacelocally.Ifnot:1)itcontactstheotherserverstoensurethatitisbroughtuptodatebeforecarryingoutthereadoperation.or2)thereadoperationisforwardedtoaserverwherethewriteoperationsthatalreadytakenplace.

Afterthereadoperationisperformed,thewriteoperationsthathavetakenplaceattheselectedserverandwhicharerelevantforthereadoperation,areaddedtotheclient’sreadset.Implementation(7.3.6)ClientARead-setReadImplementation(7.3.6)monotonic-writeconsistency:wheneveraclientinitiateanewwriteoperationataserver,thatserverishandedovertheclient’swriteset.Itthenensuresthattheidentifiedwriteoperationsareperformedfirstandinthecorrectorder.Afterperformingthenewoperation,thatoperation’swriteidentifierisaddedtothewriteset.Implementation(7.3.6)ClientAWrite-setWriteImplementation(7.3.6)read-your-writesconsistency:Requiringthattheserverwherethereadoperationisperformedhasseenallthewriteoperationsintheclient’swriteset.1)Thewritescansimplybefetchedfromotherserversbeforethereadoperationisperformed.2)Theclient-sidesoftwarecansearchforaserverwheretheidentifiedwriteoperationsintheclient’swritesethavealreadybeenperformed.Implementation(7.3.6)ClientAWrite-setReadImplementation(7.3.6)writes-follow-readsconsistency:bringingtheselectedserveruptodatewiththewriteoperationsintheclient’sreadset,andthenlateraddingtheidentifierofthewriteoperationtothewriteset,alongwiththeidentifiersinthereadset.Implementation(7.3.6)ClientARead-setWriteImprovingEfficiencySetssizesession:Client’sreadandwriteoperationsaregroupedintosessionsassociatedwithanapplication,whichopenedwhentheapplicationstartsandisclosedwhenitexits.Setsrepresentation:ts(WID),ts---timestampDISTRIBUTIONPROTOCOLS(7.4)Discussingthedifferentwaysofpropagating(distributingupdatestoreplicas).Decidingwhere,when,andbywhomcopiesofthedatastorearetobeplaced.ReplicaPlacement(7.4.1)Thelogicalorganizationofdifferentkindsofcopiesofadatastoreintothreeconcentricrings.TheinitialsetofreplicasthatconstituteadistributeddatastoreServer-InitiatedReplicasKnowsaspushcaches.服务器根据需要动态进行复制：1)toreducetheloadonaserver2)tobemigrated,orreplicatedtoserverplacedintheproximityofclientsthatissuemanyrequestsforthosefiles.Eachserverkeepstrackofaccesscountsperfile,andwhereaccessrequestscomefrom.Server-InitiatedReplicasCountingaccessrequestsfromdifferentclients.Server-InitiatedReplicascntQ(P,F)-allaccesscount(atQ)forFatQfromC1andC2(C1andC2sharethesameclosestserverP)del(S,F)-deletionthresholdrep(S,F)-replicationthresholdIfcnt(S,F)<del(S,F)thenremoveFfromS;Ifcnt(S,F)>rep(S,F)thenreplicateFatS;Ifdel(S,F)<cnt(P,F)andcnt(P,F)<rep(S,F)thenonlytobemigrated.Client-InitiatedReplicasKnownasclientcaches.

creatingacacheattheclientwhenneededandmanagingthecacheisleftentirelytothatclientUpdatePropagation(7.4.2)threepropagations:1.Propagateonlyanotificationofanupdate(knownasinvalidationprotocols)2.Transferdatafromonecopytoanother.3.Propagatetheupdateoperationtoothercopies.EnsuringrelevantconsistencyaccordingtoneedPullversusPushProtocolsAcomparisonbetweenpush-basedandpull-basedprotocolsinthecaseofmultipleclient,singleserversystems.IssuePush-basedPull-basedStateofserverListofclientreplicasandcachesNoneMessagessentUpdate(andpossiblyfetchupdatelater)PollandupdateResponsetimeatclientImmediate(orfetch-updatetime)Fetch-updatetimeIfinvalidationprotocolEpidemicProtocolsImplementeventual-consistentbasedonepidemics.aserverPpicksanotherserverQatrandom,andsubsequentlyexchangesupdateswithQ.Threeapproaches:1.PonlypushesitsownupdatestoQ2.PonlypullsinnewupdatesfromQ3.P