Agreement Protocols, distributed File Systems, Distributed Shared Memory

Agreement Protocols, Distributed Resource Management: Issues in distributed File Systems, Mechanism for building distributed file systems, Design issues in Distributed Shared Memory, Algorithm for Implementation of Distributed Shared Memory.

1. DISTRIBUTED SYSTEMS
ShikhaGautam
Assistant Professor
KIET, Ghaziabad

2. UNIT-3
•AgreementProtocols
•DistributedResourceManagement:Issuesin
distributedFileSystems,Mechanismfor
buildingdistributedfilesystems,Designissues
inDistributedSharedMemory,Algorithmfor
ImplementationofDistributedShared
Memory.

3. Agreement Protocols
•Akindofco-operationorunityoraccordanceamongprocesses.
•Asweknowthatallthenodesinadistributedsystemareworking
togetherinacooperationtoachieveacommongoals.Hence
cooperationamongtheprocessisverynecessary.
•AgreementprotocolisusedtoensurethatDSisabletoachievethe
commongoalevenafteroccurrenceofvariousfailuresinDistributed
system.
•TherearesomestandardagreementprobleminDC.Wewillsee
eachproblemandtrytofindsomeprotocoloralgorithmtosolvethe
agreementproblem.

5. Why Agreement Protocol
•Agreementisalwaysrequiredtoachieveacommongoalin
distributedsystem.
•Whentherearesometypesoffaultyprocessespresentinthe
distributedsystematthattimeweneedtomakesurethat
performanceofdistributedsystemshouldnotbeaffectedatthat
timeweimplementsomeagreementprotocol(algorithms),sothat
outputofdistributedshouldnotbeincorrectorshouldnotbe
affected.
•ToachievereliabilityofDistributedsystem.So,mainly
agreementprotocolsareusedforfault(failure)toleranceinDS

6. Problem which require Agreement
• Leader Election
• Distributed Transaction
• Mutual exclusion
• Any many more ….

7. System Model
AgreementProblemshavebeenstudiedunder
followingSystemModel:
1.‘n’processorsandatmost‘m’oftheprocessors
canbefaulty.
2.Processorscandirectlycommunicatewithother
processorsbymessagepassing.
3.Receiverknowstheidentityofthesender.
4.Communicationmediumisreliable.

8. Model of processor Failures
ProcessorCanFailinthreemodes:
1.CrashFailure:Processorstopsandneverresumesoperation.
2.Send/ReceiveOmission:ProcessorOmitstosend/receive
messagetosomeprocessors
3.MaliciousFailure:mostdangerousone
(i)AlsoknownasByzantineFailure.
(ii)Processormaysendfictitiousvalues/messagetootherprocessesto
confusethem.
(iii)Toughtodetect/correct.

9. Classification of Messages in DS
1.AuthenticatedMessages:Alsoknownassigned
Message.Processorcannotforge/changeareceived
message.Processorcanverifytheauthenticityofthe
message.Itiseasiertoreachonanagreementinthis
casebecausefaultyprocessorsarecapableofdoingless
damage.
2.Non-AuthenticatedMessages:Alsoknownas
OralMessage.Processorcanforge/changeareceived
messageandclaimstohavereceiveditfromothers.
Processorcannotverifytheauthenticityofthemessage
inthiscase.

10. We will find agreement solution in two mode
of communication under various failure

11. ClassificationofComputation:
1.Synchronousmode:
•Finitemessagedelay.
•Thismodelspecifythattheprocessinthesystem
executestepbystepi.e.lockupstepmanner.
•Onestepisknownasround.
•Aprocessreceivesmessages(1round),performsa
computation(2round),andsendmessagestoother
processes(3round).
•Ifthereisanydelaybetweenmessagesthen
computationworkwillslowdownanddecreasethe
performanceofthesystem.

12. 2.Asynchronousmode:
•Infinitemessagedelay.
•Nonlockupstepmanner.
•Thecomputationatprocessesdoesnotproceedin
steps.
•Aprocesscansendandreceivemessagesandperform
computationatanytimewithoutanysequenceof
steps.

13. Agreement Problem Types
1.Byzantine Agreement problem.
The Byzantine Agreement problem is a primitive to
the other two problems. So, The other two
Agreement Problems are:
2.The Consensus Problem.
3.The Interactive Consistency Problem.

14. Problem
Who Initiates
Value
Final
Agreement
Byzantine
Agreement
One ProcessorSingle Value
ConsensusAll Processors Single Value
Interactive
ConsistencyAll Processors
A Vector of
Values

15. Byzantine General Problem
(Inspired from Byzantine Empire)
Therewasbyzantineempireinmiddleages….there
weresomearmygeneralswhowereprotectingthe
city.Nowallgeneralhavetomakeanagreementor
somenegotiationtoprotectthecity.Ifanygeneralis
foundtobetraitorstheywillnotbeabletoprotect
thecity.hencetheyhavetoagreeonsomecommon
termsandthenonlytheycanprotectthebyzantine
empire.
PresentpartofByzantineEmpireisknowns
Turkey(Istanbul).

17. 1. Byzantine Problem in DS
Anarbitrarilychosenprocessor,calledthesource
processor,broadcastsitsinitialvaluetoallother
processors.
Agreement:Allnon-faultyprocessorsshould
agreeonthesamevalue.
Validity:Ifthesourceprocessorisnon-faulty,
thenthecommonagreeduponvaluebyallnon-
faultyprocessorsmustbesameastheinitialvalue
ofthesource.

18. Termination:Eachnon-faultyprocessormust
eventuallydecideonavalue.
•TwoImportantPointstoberemember:
1.Ifsourceisfaultythenallnon-faulty
processescanagreeonanycommonvalue.
2.Valueagreeduponbyfaultyprocessorsis
irrelevant.

19. Agreement algorithm for No-failure
•Agreement can easily achieved in constant no of
message exchange.
•Both synchronous and asynchronous mode will
always achieveagreement .Because when all
process are working fine then they are eventually
satisfying the property of Distributed system and
with constant no of message exchange we can
achieve i.e. all nodes in a distributed system are
working in a cooperation to achieve some
common goal.

20. Agreement Protocol in Crash
Failure Process

21. Solution for Byzantine Agreement
Problem
Lamportet.alproposedanalgorithmfor
byzantineagreementproblemwhichisknown
asLamport-Shostak-PeaseAlgorithm.
•SourceBroadcastsitsinitialvaluetoallotherprocessors.
•Processorssendtheirvaluestootherprocessorsandalso
receivedvaluesfromothers.
•DuringExecutionfaultyprocessorsmayconfusebysending
conflictingvalues.
•Howeveriffaultyprocessorsdominateinnumber,theycan
preventnon-faultyprocessorsfromreachinganagreement.
•So,thenooffaultyprocessorsshouldnotexceedcertain
limit.

22. Lamport-Shostak-Pease Algorithm
ThisalgorithmisalsoknownasOralMessage
Algorithm(OM).
•Consideringthereare‘n’processorsand‘m’faulty
processors.
•Peaseshowedthatinafullyconnectednetwork,itis
impossibletoreachanagreementifnumberfaulty
processors‘m’exceeds(n-1)/3
•i.e.n>=(3m+1)

23. Algorithm is Recursively defined as follows:
•Algorithm OM(0), i.e. (m=0)
Step 1: Source processor sends its values to every
processor.
Step 2: Each processor uses the value it receives from
source (If no value is received default value 0 is used).

24. • Algorithm OM(m), i.e. (m>0)
Step 1: The source processor sends its value to
every processor.
Step 2: If a processor does not receive value it uses
a default value of zero.
Step 3: For each processor Pi, let vi be the value
processor receives from source, then it behaves like
source processor.
Step 4: If for a processor Pi, Vj(j!=i) is the value
received from Pj, the Pi uses the majority value as
agreement value.

25. Byzantine Agreement can not have solution when
among three processors if one processor is faulty.

26. 2. The Consensus Problem
Hereallprocesshavesomeinitialvaluethey
broadcasttheirinitialvaluestoallothersprocess
andsatisfythefollowingcondition:
Agreement:Allnon-faultyprocessesmustagreeon
samesinglevalues.
Validity:ifallnonfaultyprocesseshavethesame
initialvalue,thentheagreedvaluebyallthenon-
faultyprocessesmustbethatsamevalue.

27. Termination: Each non-faulty process must
eventually decide on a value.
•Two Important Points to be remember:
1.If initial value of non-faulty processors are
different then all non-faulty then processors
can agree on any common value.
2.Value agreed upon by faulty processors is
irrelevant.

28. 3. The Interactive Consistency Problem
Every processor broadcasts its initial value to all other processors.
The initial values of the processors may be different . A protocol for
the interactive consistency problem should meet the following
conditions:
Agreement: All non-faulty processes must agree on the same array of
values A[v1 : : : vn].
Validity: If processor Pi is non-faulty and its initial value is vi , then all
non-faulty processes agree on vi as the ithelement of the array A. If
process j is faulty, then the non-faulty processes can agree on any
value for A[j].
Termination: Each non-faulty process must eventually decide on the
array A.

30. Metrics to measure performance of
Agreement Protocol
•Time: Time taken to reach an agreement under a
protocol. The time is usually expressed as the
number of rounds needed to reach an agreement.
•Message Traffic: Number of messages exchanged
to reach an agreement.
•Storage Overhead: Amount of information that
need to be stored at processors during execution
of the protocol.

31. • There are some solution that solve agreement problems by
satisfying all condition of agreement problem in case of
synchronous system.
• But in case of asynchronous models , agreement problem are
not solvable. However we can solve agreement problem in
asynchronous System after converting agreement problem in its
weaker version. That means agreement problem are reduce to
some weaker version :
Weaker version of agreement problem are:
1.k-set consensus
2.Approximate consensus
3.Renaming problem
4.Terminating reliable broadcast ( it is a kind of problem which
require consensus.)

32. Applications of AgreementProtocol
1.Clock Synchronization in Distributed Systems:
•Distributed Systems require physical clocks to synchronized
but physical clocks have drift problem. So, they must
periodically resynchronized.
•Such periodically synchronization becomes extremely difficult
if the Byzantine failures are allowed.
•This is due to the fact that faulty processors can report different
clock value to different processors.
•Agreement Protocols may help to reach a common clock value.

33. 2.Atomic Commit in Distributed Database:
•DDBS sites must agree whether to commit or abort the
transaction.
•In first Phase, sites execute their part of a distributed
transaction and broadcast their decisions to all other
sites.
•In Second Phase, each site based on what is received
from other sites in the first phase, decides whether to
commit or abort.

34. Two-phase commit in Distributed
Systems
Motivation: sending money

35. Single-server: ACID

36. Distributed transactions?

37. Two-Phase Commit (2PC)

40. Safety versus liveness

41. A correct atomic commit protocol

42. A correct atomic commit protocol

43. A correct atomic commit protocol

44. A correct atomic commit protocol

46. Distributed Resource
Management
Issues in distributed File Systems,
Mechanism for building distributed file
systems, Design issues in Distributed Shared
Memory, Algorithm for Implementation of
Distributed Shared Memory.

47. •FileSystemworkastheresourcemanagementcomponent,
whichmanagestheavailabilityoffilesindistributed
system.
•Acommonfilesystemthatcanbesharedbyallthe
autonomouscomputersinthesystem.i.e.filescanbestored
atanymachineandthecomputationcanbeperformedatany
machine.
Twoimportantgoals:
1.Networktransparency–toaccessfilesdistributedoveranetwork.
Ideally,usersdonothavetobeawareofthelocationoffilestoaccess
them.
2.HighAvailability-toprovidehighavailability.Usersshouldhavethe
sameeasyaccesstofiles,irrespectiveoftheirphysicallocation.
Distributed File Systems

49. Figure:
Architecture of a Distributed File System

50. Architecture
•FileserversandFileclientsinterconnectedby
acommunicationnetwork.
•Twomostimportantcomponents:
1.NameServer:maplogicalnamestostored
object’s(files,directories)physicallocation.
2.CacheManager:performfilecaching.Can
presentonbothserversandclients.
1.Cacheontheclientdealswithnetworklatency
2.Cacheontheserverdealswithdisklatency

51. •Typicalstepstoaccessdata:
1.checkclientcache,ifpresent,returndata.
2.Checklocaldisk,ifpresent,loadintolocalcache,
returndata.
3.Sendrequesttofileserver
4....
5.servercheckscache,ifpresent,loadintoclient
cache,returndata
6.diskread
7.loadintoservercache
8.loadintoclientcache
9.returndata

52. 1.NamingandTransparency
2.RemotefileaccessandCaching
3.ReplicationandConcurrentfileupdates
4.Availability
5.Scalability
6.Semantics
Issues in distributed File Systems

53. 1. Naming and Transparency

54. •Transparencyshouldalsobeachievedatvarious
levels:
1.StructureTransparency
2.AccessTransparency
3.NamingTransparency
4.ReplicationTransparency
5.LocationTransparency
6.MobilityTransparency
7.PerformanceTransparency
8.ScalingTransparency

55. 2. Remote file access and Caching

56. 3. Concurrent file updates
•Serverdataisreplicatedacrossmultiple
machines.
•Needtoensureconsistencyoffileswhenafile
isupdatedbymultipleclients.
•Changestoafilebyoneclientshouldnot
interferewiththeoperationsofotherclients.

57. 4. Availability
•howtokeepreplicasconsistent.
•howtodetectinconsistenciesamongreplicas.
•consistencyproblemmaydecreasethe
availability.
•ReplicaManagement:votingmechanismto
readandwritetoreplica.

58. 5. Scalability
•Howtomeetthedemandofagrowing
system?
•Thebiggesthurdle:consistencyissue

59. 6. Semantics
•Whatauserwants?strictconsistency.
•Userscanusuallytolerateacertaindegreeof
errorsinfilehandling--noneedtoenforce
strictconsistency.

60. Mechanism for building Distributed
File Systems
1.Mounting:
Amountmechanismallowsthebinding
togetherofdifferentfilenamespacestoform
asinglehierarchicallystructuredname
space.

62. 2. Caching
•Cachingiscommonlyemployedindistributedfiles
systemstoreducedelaysintheaccessingofdata.
•Infilecaching,acopyofdatastoredataremotefile
serverisbroughttotheclientwhenreferencedby
theclient.
•Subsequentaccesstothedataisperformedlocally
attheclient,therebyreducingaccessdelaysdueto
networklatency.
•Cachingexploitsthetemporallocalityofreference
exhibitedbyprograms.
•Thetemporallocalityofreferencereferstothefact
thatafilerecentlyaccessedislikelytobeaccessed
againinthenearfuture.

63. 3. Hint
•Analternativeapproachisusedwhencacheddataarenot
expectedtobecompletelyaccurate.
•However,validcacheentriesimproveperformance
substantiallywithoutincurringthecostofmaintainingcost
consistency.
•Theclassofapplicationsthatcanutilizehintsarethosewhich
canrecoverafterdiscoveringthatthecacheddataareinvalid.
•Forexample,afterthenameofafileordirectoryismappedto
thephysicalobject,theaddressoftheobjectcanbestoredas
ahintinthecache.
•Iftheaddressfailstomaptotheobjectinthefollowing
attempt,thecachedaddressispurgedfromthecache.
•Thefileserverconsultsthenameservertodeterminethe
actuallocationofthefileordirectoryandupdatesthecache.

64. 4. Bulk Data Transfer
•Transferringdatainbulkreducestheprotocol
processingoverheadatbothserversandclients.
•Inbulkdatatransfer,multipleconsecutivedata
blocksaretransferredfromserverstoclientsinstead
ofjusttheblockreferencedbyclients.
•Bulktransfersreducefileaccessoverheadthrough
obtainingamultiplenumberofblockswithasingle
seek;byformattingandtransmittingamultiple
numberoflargepacketsinasinglecontextswitch;
andbyreducingthenumberofacknowledgements
thatneedtobesent.

65. 5. Encryption
•Encryptionisusedforenforcingsecurityin
distributedsystems.
•Inthisscheme,twoentitieswishingto
communicatewitheachotherestablishakeyfor
conversationwiththehelpofanauthentication
server.
•Itisimportanttonotethattheconversationkey
isdeterminedbytheauthenticationserver,butis
neverspentinplain(unencrypted)texttoeither
oftheentities.

66. Distributed Shared Memory
•Ideaofdistributedsharedmemoryistoprovideanenvironment
wherecomputerssupportasharedaddressspacethatismadeby
physicallydispersedmemories.
•Itreferstosharedmemoryparadigmappliedtolooselycoupled
distributedmemorysystems.Itgivesthesystemsillusionof
physicallysharedmemory.
•Memorymappingmanagerisresponsibleformappingbetween
localmemoriesandthesharedmemoryaddressspace.
•Anyprocessorcanaccessanymemorylocationintheaddress
spacedirectly.
•Chiefresponsibilityistokeeptheaddressspacecoherentatthe
times.

68. Architecture
•EachnodeofthesystemconsistofoneormoreCPUs
andmemoryunit.
•Nodesareconnectedbyhighspeedcommunication
network.
•Simplemessagepassingsystemfornodestoexchange
information.
•Mainmemoryofindividualnodesisusedtocachepieces
ofsharedmemoryspace.
•Sharedmemoryexistonlyvirtually.
•Memorymappingmanagerroutinemapslocalmemory
tosharedvirtualmemory.

70. •Thesharedmemorymodelprovidesavirtual
addressspacewhichissharedbyallnodesina
distributedsystem.
•Thebasicunitofcachingisamemoryblock.
•Sharedmemoryspaceispartitionedintoblocks.
•Datacachingisusedtoreducenetworklatency.
•Themissingblockismigratefromtheremote
nodetotheclientprocess’snodeandoperating
systemmapsintotheapplication’saddressspace.
•Datablockkeepmigratingfromonenodeto
anotherondemandbutnocommunicationis
visibletotheuserprocesses.

71. Advantages of DSM(or DSVM)
1.SimplerAbstraction:shieldstheapplication
programmersfromlowlevelconcern.
2.Betterportabilityofdistributedapplication
programs:Theaccessprotocolusedincase
ofDSMisconsistentwiththewaysequential
applicationaccessdatathisallowsforamore
naturaltransitionfromsequentialto
distributedapplication.

72. 3.Betterperformance:duetoLocalityofdata,
Ondemanddatamoment,Largememory
spaceastotalmemorysizeisthesumofthe
memorysizeofallthenodesinthesystem.
4.Flexiblecommunicationenvironment
5.Ondemandmigrationofdatabetween
processors.

73. Design issues in Distributed Shared
Memory
1.Granularity
2.StructureofSharedmemory
3.Memory coherence and access
synchronization
4.Datalocationandaccess
5.Replacementstrategy
6.Thrashing
7.Heterogeneity

74. 1. Granularity:
•Computationgranularityreferstothesizeofthe
sharingunit.Itcanbeabyte,aword,apageor
othertypeofunit.
•Choosingtherightgranularityisamajorissuein
distributedsharedmemorybecauseitdeals
withtheamountofcomputationdonebetween
synchronizationorcommunicationpoints.
•Otherissueis,movingaroundcodeanddatain
thenetworksinvolveslatencyandoverheadfrom
networkprotocols.

75. 2. Structure of Shared memory
•Structurereferstothelayoutoftheshared
datainmemory.
•Dependentonthetypeofapplicationsthat
thedistributedsharedmemorysystemis
intendedtosupport.

76. 3. Memory coherence and access
synchronization
•InaDSMsystemthatallowsreplicationofshareddata
item,copiesofshareddataitemmaysimultaneously
beavailableinthemainmemoriesofanumberof
nodes.
•Tosolvethememorycoherenceproblemthatdealwith
theconsistencyofapieceofshareddatalyinginthe
mainmemoriesoftwoormorenodes.
•Theremightbesomepotentialconsistencyproblems
whendifferentprocessorsaccess,cacheandupdate
thesharedsinglememoryspace.

77. 4. Data location and access
•TosharedatainaDSM,shouldbepossibleto
locateandretrievethedataaccessedbya
userprocess.

78. 5. Replacement strategy
•Ifthelocalmemoryofanodeisfull,acache
missatthatnodeimpliesnotonlyafetchof
accesseddatablockfromaremotenodebut
alsoareplacement.
•Datablockmustbereplacedbythenewdata
block.

79. 6. Thrashing
•Thrashingoccurswhenacomputer'svirtualmemory
resourcesareoverused,thiscausestheperformanceof
thecomputertodegradeorcollapse.
•Theproblemofthrashingmayoccurwhendataitemin
thesamedatablockarebeingupdatedbymultiple
nodeatthesametime.
•Problemmayoccurwithanyblocksize,itismorelikely
withlargerblocksize.

80. 7. Heterogeneity
•TheDSMsystembuiltforhomogeneous
systemneednotaddresstheheterogeneity
issue.

81. •Somosttheimportantissuesare:
-Howtokeeptrackofthelocationofremote
data
-Howtominimizecommunicationoverhead
whenaccessingremotedata
-Howtoaccessconcurrentlyremotedataat
severalnodes

82. Algorithm for Implementation of
Distributed Shared Memory
1.TheCentralServerAlgorithm
2.TheMigrationAlgorithm
3.TheRead-ReplicationAlgorithm
4.TheFull–ReplicationAlgorithm

83. 1. The Central Server Algorithm
•Centralservermaintainsallshareddata:
–Readrequest:returnsdataitem.
–Writerequest:updatesdataandreturnsacknowledgement
message.

84. •Implementation:
–Atimeoutisusedtoresendarequestifacknowledgment
fails.
–Associatedsequencenumberscanbeusedtodetect
duplicatewriterequests
–Ifanapplication’srequesttoaccessshareddatafails
repeatedly,afailureconditionissenttotheapplication
–Itissimplertoimplementbutthecentralservercanbecome
bottleneckandtoovercomethisshareddatacanbe
distributedamongseveralservers.
•Issues:performanceandreliability.
•Possiblesolutions:
–Partitionshareddatabetweenseveralservers
–Useamappingfunctiontodistribute/locatedata

85. 2. The Migration Algorithm
•Everydataaccessrequestisforwardedtolocationofdata
whileinthisdataisshippedtolocationofdataaccessrequest
whichallowssubsequentaccesstobeperformedlocally.
•Itallowsonlyonenodetoaccessashareddataatatime.
•Thewholeblockcontainingdataitemmigratesinsteadof
individualitemrequested.
•ThisalgorithmprovidesanopportunitytointegrateDSMwith
virtualmemoryprovidedbyoperatingsystematindividual
nodes.

86. •Advantages:Takesadvantageofthelocalityof
reference.
•Tolocatearemotedataobject:
–Usealocationserver
–Maintainhintsateachnode
–Broadcastquery
•Issues
–Onlyonenodecanaccessadataobjectatatime
–Thrashingcanoccur:tominimizeit,setminimum
timedataobjectresidesatanode

87. •Thisextendsthemigrationalgorithmbyreplicatingdata
blockstomultiplenodesandallowingmultiplenodesto
havereadaccessoronenodetohavebothreadwrite
access.
•Afterawrite,allcopiesareinvalidatedorupdated.
•DSMhastokeeptrackoflocationsofallcopiesofdata
objects.
•Advantage:
Theread-replicationcanleadtosubstantial
performanceimprovementsiftheratioofreadsto
writesislarge.
Itimprovessystemperformancebyallowing
multiplenodestoaccessdataconcurrently.
3. The Read-Replication Algorithm

88. Thewriteoperationinthisisexpensiveasallcopiesofashared
blockatvariousnodeswilleitherhavetoinvalidatedorupdated
withthecurrentvaluetomaintainconsistencyofshareddata
block.

89. •Itisanextensionofreadreplicationalgorithmwhich
allowsmultiplenodestohavebothreadandwrite
accesstoshareddatablocks.
•Issue:Sincemanynodescanwriteshareddata
concurrently,theaccesstoshareddatamustbe
controlledtomaintainit’sconsistency.
4. The Full–Replication Algorithm

90. •Solution:useofgap-freesequencer
Allwritessenttosequencer.
allnodeswishingtomodifyshareddatawillsend
themodificationtosequencerwhichwillthen
assignasequencenumberandmulticastthe
modificationwithsequencenumbertoallnodes
thathaveacopyofshareddataitem.
Eachnodeperformswritesaccordingto
sequencenumbers.
Agapinsequencenumbersindicatesamissing
writerequest:nodeasksforretransmissionof
missingwriterequests.