IEEEWorkshoponFault-Tol.Par.andDist.Syst.,CollegeStation,TX,June - .(Appearsin
`Fault-Tol.Par.andDist.Syst.,D.PradhanandD.Avresky,eds.,IEEEComp.Soc.Press,pp.-.)
`Fault-TolerantClockSynchronizationfor
`DistributedSystemswithHighMessageDelayVariation(cid:3)
`MarceloMoraesdeAzevedoandDouglasM.Blough
`DeparmentofElectricalandComputerEngineering
`UniversityofCalifornia,Irvine
`Irvine,CA  
`Abstract
`Fault-tolerantclocksynchronizationisanimportantrequirementinmanydistributedsys-
`tems,especiallyintime-criticalandsafety-criticalapplications.Frequently,interactivecon-
`vergencealgorithmsareusedforfault-tolerantclocksynchronization,providingadvantages
`suchasfullydistributedoperation,lowmessageexchangeoverhead,andsimplicityofimple-
`mentation.Thispaperpresentsthemeasuredperformanceofthreeinteractiveconvergence
`clocksynchronizationalgorithms.OurexperimentswereconductedinadistributedUNIX
`environmentfeaturinghighmessagedelayvariation,whichposessevereconstraintsonthe
`clocksynchronizationtightnessthatmaybeachieved.Thealgorithmsthatweretestedare:
`FTMA(fault-tolerantmidpointalgorithm)[ ],AEFTMA(adaptiveexponentialaveraging
`fault-tolerantmidpointalgorithm)[],andSWA(slidingwindowalgorithm)[ ].Ourex-
`perimentalresultsindicatethatSWAoutperformstheotheralgorithmsinthisenvironment,
`beingabletoachievetightersynchronizationunderdi(cid:11)erentsimulatedfaultconditions.The
`superiorityofSWAcanbeattributedtoitshighdegreeoffaulttolerance,combinedwithits
`abilitytotreatmessageswithmuchlongerthanexpecteddelaysasfaults.
` :Introduction
`Indistributedsystems,computerscooperatetoprovidetheexpectedfunctionalityto
`agivenapplication.Sometasksthatareoftenfoundinsuchsystemsare:synchronizing
`activitiesthatoccuratdi(cid:11)erentpointsofthesystem,orderingeventsintime,enforcing
`deadlines,andmeasuringelapsedtime.Asystemwithoneormoreoftheserequirements
`mustusepropersynchronizationmechanismstoestablishanagreed-uponglobaltimescale
`amongitscomponents.Particularlyinthecaseofsafety-criticalapplications,synchrony
`mustbemaintainedinspiteofthepresenceoffaultsinthesystem.
`Frequently,fault-tolerantclocksynchronizationisachievedviainteractiveconvergence
`algorithmsinwhichnodesexchangetheirclockvaluesanddetermineclockcorrectionterms
`atregularintervals.Thispaperpresentsthemeasuredperformanceofthreeinteractivecon-
`vergencealgorithms:theslidingwindowalgorithm(SWA)[ ],thefault-tolerantmidpoint
`algorithm(FTMA)[ ],andtheadaptiveexponentialaveragingfault-tolerantmidpointal-
`gorithm(AEFTMA)[].Themeasurementswerecarriedoutwithanapplication-level
`implementationrunninginadistributedUNIXenvironment[].Thisenvironmentposes
`somepracticalconstraintstoclocksynchronization,inparticularahighvariationinthe
`(cid:3)ThisresearchwassupportedinpartbyConselhoNacionaldeDesenvolvimentoCient(cid:19)(cid:16)(cid:12)coeTecnol(cid:19)ogico
`(CNPq-Brazil),underGrant / - ,bytheNationalScienceFoundationunderGrantCCR-  ,
`andbytheCaliforniaSpaceInstituteunderGrantCS-- .
`
`
`PAGE 1 OF 10
`
`SONOS EXHIBIT 1010
`IPR of U.S. Pat. No. 8,942,252
`
`

`

` IEEEWorkshoponFault-Tol.Par.andDist.Syst.,CollegeStation,TX,June - .(Appearsin
`Fault-Tol.Par.andDist.Syst.,D.PradhanandD.Avresky,eds.,IEEEComp.Soc.Press,pp.-.)
`messagedelay.Ourresultsarethereforerepresentativeofabroadclassofsystemswherea
`lowvariationinthemessagedelaycannotbeachieved.Ourexperimentalresultsindicate
`thatSWAmaintainstighterclocksynchronizationthantheotheralgorithms.Wewillshow
`thatthisresultsfromSWA'shigherdegreeoffaulttolerance[ ],togetherwithitsability
`totreatmessageswithmuchlongerthanexpecteddelaysasfaults.
`:Background:Interactiveconvergencealgorithms
`Inadistributedsystem,timeisusuallyobservableinalocalreferencereferredtoas
`clocktime.Clocktimesmaydi(cid:11)erbothinabsolutevalueandinratefromanassumed
`Newtoniantimeframe,whichisnotdirectlyobservableandisreferredtoasrealtime.
`TheclockofanodecanberepresentedbyamappingCfromrealtimetoclocktime.
`Forexample,Ci(t)=TmeansthatatrealtimettheclockofnodeihasvalueT.Clocksin
`di(cid:11)erentnodesinadistributedsystemtendtodriftapartfromeachotherwiththepassage
`oftime,becausetheytypicallydonottickatexactlythesamerate.Thisbringsaboutthe
`needofsomeformofclocksynchronizationschemeinsystemswhereaglobaltimescale
`mustexist.Moreover,clocksynchronizationmustoftenbeachievedinenvironmentsin
`whichchallengessuchasfaultsandhighmessagedelayvariationmayexist.
`Interactiveconvergenceisawidelyusedapproachtofault-tolerantclocksynchronization,
`beingsuitableforalargerangeofdistributedsystemsapplications.Clocksynchronization
`isaccomplishedinafullydistributedfashion,allowingeverynodetoexhibitequalfunc-
`tionalitywithregardtosynchronization.Nosinglepointoffailureexists,andexpensive
`modulestoprovidereal-timeclockreferencesarenotrequired.
`Interactiveconvergence
`algorithmsaredrivenbythemultipleclocksourcesnormallyfoundindistributedsystems,
`andthereforecanbeimplementedatlittleadditionalcost.Inaddition,suchalgorithms
`usuallyfeaturelowmessageexchangeoverhead,requiringonlyO(n)messagesperroundin
`ann-nodesystemwithbroadcastcapabilities.Interactiveconvergencealgorithmsprovide
`internalclocksynchronization,meaningthatthesystem'sglobaltimescaleisnotnecessarily
`synchronizedtoanexternaltimereference.
`Inaninteractiveconvergencealgorithm,nodesperiodicallyexchangesynchronization
`messagescontainingtheirclockvaluesandthenusethereceivedvaluestoadjusttheirclocks.
`Theintervaloftimebetweensuccessiveresynchronizationsisdubbedaresynchronization
`intervaloraroundofthealgorithmanditsdurationisdenotedbyTint.Anodethatis
`exchangingmessagesfortherthtimesincetheclocksynchronizationprocesswasstartedis
`saidtobeinitsrthresynchronizationinterval.Onetechniquethatcanbeusedtoexchange
`clockvaluesisbroadcasting,whichisinfactthemethodusedinourexperiments.
`Theprocessbywhichanodeassignsaclockvaluetobesentinanoutgoingmessage
`ortobeattachedtoanincomingmessageisreferredtoastime-stamping.Theclock
`valuethatissentinasynchronizationmessageisreferredtoasthesender'stime-stamp
`(Tsend).Similarly,theclockvaluethatisattachedtoanincomingsynchronizationmessage
`isreferredtoasthereceiver'stime-stamp(Trec).
`Assumethatatrealtimetrsend(i)nodeitime-stampsitsrthsynchronizationmessage
`withasender'stime-stampTrsend(i).Letthetotalmessagedelaybetweennodesiandj
`duringtherthresynchronizationintervalbedr(i;j),suchthati'smessageistime-stamped
`byjatrealtimetrrec(i;j)=trsend(i)+dr(i;j).
`Ifj'sclockreadsTrrec(i;j)atrealtime
`trrec(i;j),thentheclockvalueoficanbeestimatedbyjatrealtimetrj,trj(cid:21)trrec(i;j),by
`Cri;j(trj)=Trsend(i)+drmed(i;j)+(Cj(trj)(cid:0)Trrec(i;j)),wheredrmed(i;j)isj'sestimateforthe
`messagedelaybetweennodesiandjduringtherthresynchronizationinterval.
`TheclockdeviationbetweennodesiandjatrealtimetisCj(t)(cid:0)Ci(t).Theclocks
`
`
`PAGE 2 OF 10
`
`SONOS EXHIBIT 1010
`IPR of U.S. Pat. No. 8,942,252
`
`

`

` IEEEWorkshoponFault-Tol.Par.andDist.Syst.,CollegeStation,TX,June - .(Appearsin
`Fault-Tol.Par.andDist.Syst.,D.PradhanandD.Avresky,eds.,IEEEComp.Soc.Press,pp.-.)
`ofanytwononfaultynodesaandbinthesystemdeviatebyatmost(cid:1)intsecondsatany
`realtimet(cid:21),where(cid:1)intisreferredtoastheworst-caseclocksynchronizationtightness.
`Formally,a;b;t(cid:21);jCa(t)(cid:0)Cb(t)j(cid:20)(cid:1)int.
`Theestimatedclockdeviationbetweennodesiandjasmeasuredbynodejatrealtime
`trjduringtherthresynchronizationintervalisgivenby
`(cid:1)ri;j=Cj(trj)(cid:0)Cri;j(trj)=Trrec(i;j)(cid:0)Trsend(i)(cid:0)drmed(i;j)
`( )
`Tosimplifytheterminologyofthispaper,wehereafterusethetermclockdeviationto
`refertoaclockdeviationestimate.Wheneverappropriate,wewillremindthereaderthat
`adistinctionexistsasde(cid:12)nedabove.
`Attheendoftherthresynchronizationinterval,eachnodej, (cid:20)j(cid:20)n,willhave
`collectedavectorofclockdeviations(cid:1)rj=[(cid:1)r ;j(cid:1)r;j(cid:1)(cid:1)(cid:1)(cid:1)rj(cid:0) ;j(cid:1)rj+ ;j(cid:1)(cid:1)(cid:1)(cid:1)rn;j](note
`that(cid:1)rj;j=).AclockcorrectiontermCORRrjisthencalculatedfrom(cid:1)rjbymeansofa
`convergencefunction.Followingthisstep,thelocalclockofnodejisadjustedbyCORRrj.
`Toguaranteethataninteractiveconvergencealgorithmmaintainssynchronizationre-
`quiresthatclocksynchronizationmessagesbeexchangedwithsomeboundeddelaydmax.
`Messagedelayisexpectedtovaryintherange[dmin;dmax],withdvar=dmax(cid:0)dminbeing
`referredtoasthemessagedelayvariationanddvar=beingreferredtoasthereadingerror.
`Naturally,dvara(cid:11)ectstheworst-caseclocksynchronizationtightness((cid:1)int).
`LundeliusandLynch[]provedthatinasystemwithnclocksandmessagedelayvari-
`ationdvartheclocksynchronizationtightnesscannotbebetterthandvar( (cid:0) =n).Sucha
`lowerboundholdsunderthestrongassumptionsthatallclocksrunataperfectrateand
`thattherearenofailuresinthesystem.Underthesameassumptionsandalsoassuming
`thatclocksinitiallyhavearbitraryvalues,LundeliusandLynchgiveasimplealgorithm
`thatachievesthisbound.Clearly,thislowerboundalsoholdsforthemorerealisticcase
`thatweconsiderinwhichclocksdriftandfaultsoccur.
`Ourimplementationperformstime-stampingofmessagesintheapplicationlevel,using
`UNIXsystemcallsforthatpurpose.Thismechanismexhibitsahighlyvariabledelaybe-
`tweenthemomentatime-stampisobtainedandthecorrespondingmessageisactuallysent
`orreceived.Theresultingmessagedelayvariationinanapplication-levelsoftwareimple-
`mentationistypicallyseveralhundredsofmilliseconds[].AccordingtotheLundeliusand
`Lynchlowerbound,theworst-caseclocksynchronizationtightness((cid:1)int)shouldtherefore
`beonthesameorderofmagnitude.
`Aninterestingaspectofimplementingaclocksynchronizationalgorithmintheapplica-
`tionlevelisthatahighindependenceofthehardwareplatformisobtained.Therefore,this
`approachcanbereadilyusedinexistingsystems.
`Application-levelclocksynchronizationcanbeusedinmanyapplicationsthatdonot
`requiretightsynchronization.Nevertheless,wewouldstillliketohavethebesttightness
`thatcanbeachievedinthisenvironment.Consideringthisgoal,ourexperimentsevaluated
`threedi(cid:11)erentinteractiveconvergencefunctions:FTMA,AEFTMA,andSWA.
` :Descriptionofconvergencefunctions
`Asdescribedintheprevioussection,interactiveconvergencealgorithmsexhibitgreat
`proceduralsimilarity,withvariationsbeinglimitedtotheconvergencefunctionthatisused
`tocomputetheclockcorrectiontermateveryround.Intheremainderofthissection,we
`describetheconvergencefunctionsusedbyFTMA,AEFTMA,andSWA.
`
`
`
`PAGE 3 OF 10
`
`SONOS EXHIBIT 1010
`IPR of U.S. Pat. No. 8,942,252
`
`

`

` IEEEWorkshoponFault-Tol.Par.andDist.Syst.,CollegeStation,TX,June - .(Appearsin
`Fault-Tol.Par.andDist.Syst.,D.PradhanandD.Avresky,eds.,IEEEComp.Soc.Press,pp.-.)
` . :Fault-tolerantmidpointalgorithm
`Thefault-tolerantmidpointalgorithm(FTMA)[ ]reliesonthehypothesisthatatmost
`kclocksarefaultyatanyresynchronizationinterval.Atleastn= k+ nodesarerequired
`inthesystemtotoleratekByzantinefaults.
`Assumethat,atagivenroundrofthealgorithm,asortedclockdeviationvectorXrj=
`(cid:1)(cid:1)(cid:1)xn],xi(cid:20)xi+ ,isavailableatnodej(notethattheelementsinXrjare
`[x x(cid:1)(cid:1)(cid:1)xi
`exactlytheelementsin(cid:1)rj,exceptthatinXrjtheyaresorted).To(cid:12)ndtheclockcorrection
`term,FTMAdiscardstheklowestandthekhighestclockdeviationsandcomputesthe
`arithmeticmeanofxk+ andxn(cid:0)k;thatis,CORRrj=(xk+ +xn(cid:0)k)=.
` .:Adaptiveexponentialaveragingfault-tolerantmidpointalgorithm
`Theadaptiveexponentialaveragingfault-tolerantmidpointalgorithm(AEFTMA)[]isa
`variationoftheFTMAalgorithm[ ].AssumethatCORRrFTMAisthecorrectiontermcom-
`putedviathestandardFTMAconvergencefunction(i.e.,(xk+ +xn(cid:0)k)=)intherth
`resynchronizationintervalandthatCORRr(cid:0) AEFTMAisthecorrectiontermcomputedby
`InsteadofusingCORRrFTMAasthecorrectionterm
`AEFTMAinthepreviousround.
`duringtherthresynchronizationinterval,AEFTMAcomputesitscorrectiontermby
`CORRrAEFTMA=(cid:12)(r)(cid:1)CORRrFTMA+( (cid:0)(cid:12)(r))CORRr(cid:0) AEFTMA.
`(cid:12)(r)isaweightfactorine(cid:11)ectduringtherthresynchronizationinterval,suchthat
`(cid:20)(cid:12)(r)(cid:20) .Theweightfactor\smooths"theclockcorrectiontermCORRrAEFTMA,
`introducingalaggingmechanismbetweenadjacentrounds.Thisapproachfollowstheas-
`sumptionthatcorrectiontermsofsimilarmagnitudeareexpectedateveryresynchroniza-
`tioninterval,sincechangesinthedriftrateofclocksaregenerallycausedbyintrinsically
`slowphenomenasuchastemperaturevariationandcomponentaging.Therefore,excessive
`correctiontermsresultingfromlargemessagedelayvariationareattenuatedbyexponential
`averaging.Nevertheless,inordertoguaranteeafastrecoveryofsynchronyincaseoftran-
`sientfaultoccurrence,theweightfactorvariesadaptivelyaccordingtotheabsolutevalueof
`theclockcorrectiontermcomputedbyAEFTMAinthecurrentround(jCORRrAEFTMAj).
`Theadaptivecontroloftheweightfactormustbechosenaccordingtotheexpected
`messagedelayvariation,whichinanapplication-level
`implementationishighlydepen-
`dentonaspectssuchasCPUandnetworkutilizationandthepriorityassignedtothe
`clocksynchronizationprocess.Weusedinourimplementationa-levelstepwisefunction
`f(jCORRrAEFTMAj),whichselectsthenext-roundweightfactor(cid:12)(r+ )fromasetofvalues
`B=f: ;:;:; g.Selectionof(cid:12)(r+ )isaccomplishedbycomparingthecurrent-
`roundabsoluteclockcorrectiontermjCORRrAEFTMAjwithasetofthresholdsC=fms,
` ms, msg,suchthat(cid:12)(r+ )=: ifjCORRrAEFTMAj(cid:20)ms,(cid:12)(r+ )=:if
`ms<jCORRrAEFTMAj(cid:20) ms,(cid:12)(r+ )=:if ms<jCORRrAEFTMAj(cid:20) ms,
`and(cid:12)(r+ )= ifjCORRrAEFTMAj> ms.Suchafunctionwasselectedaccordingto
`thetypeofloadusedduringourexperiments,whichconsistedoflong-runapplicationsthat
`generatecontinuouslyhighCPUloadandnetworkutilization.
`Notethatwhen(cid:12)(r)= theclockcorrectiontermresultingfromAEFTMAequals
`thatcomputedviathestandardFTMAconvergencefunction.Thisallowssynchronyto
`bequicklyreestablishedinthepresenceofatransientfault,sincethelagginge(cid:11)ectof
`previousclockadjustmentspersistsforatmostoneroundafterthefaultoccurred.After
`that,AEFTMAentersamemorylessoperationmode,behavingexactlylikeFTMA,until
`(cid:12)(r)isagainreducedbelow .
`
`
`
`PAGE 4 OF 10
`
`SONOS EXHIBIT 1010
`IPR of U.S. Pat. No. 8,942,252
`
`

`

` IEEEWorkshoponFault-Tol.Par.andDist.Syst.,CollegeStation,TX,June - .(Appearsin
`Fault-Tol.Par.andDist.Syst.,D.PradhanandD.Avresky,eds.,IEEEComp.Soc.Press,pp.-.)
` . :Slidingwindowalgorithm
`Theslidingwindowalgorithm(SWA)toleratesconsiderablyhigherpercentagesofnon-
`Byzantinefaultsthanotherinteractiveconvergencealgorithms[ ].However,thealgorithm
`requiresthatthenumberofByzantinefaultsmustbelimitedtob(cid:20)n=,whichisaproper
`assumptionformanysystems.AbasicassumptionmadebySWAisthatthereadingsof
`di(cid:11)erent\good"clocksbyagivennodejshoulddi(cid:11)erbyasmallamount.Therefore,itis
`expectedthattheclockestimatescomputedbyjfromthemessagesreceivedfrom\good"
`clocksourceswillbeclusteredwithinalimitedrange.Thebasicoperationperformedby
`SWAconsistsoflocatingaclusterof\good"clockvaluesbymeansofaslidingwindow
`mechanism.Alternatively,SWAcanbeimplementedsuchthatidenti(cid:12)cationofclusters
`occursinaclockdeviationvector,whichistheapproachusedinourimplementation.
`Assumethat,atagivenroundrofthealgorithm,asortedclockdeviationvectorXrj=
`(cid:1)(cid:1)(cid:1)xn],xi(cid:20)xi+ ,isavailableatnodej(notethattheelementsinXrjare
`[x x(cid:1)(cid:1)(cid:1)xi
`exactlytheelementsin(cid:1)rj,exceptthatinXrjtheyaresorted).Startingattheleftmost
`elementofXrj,SWAslidesawindowofwidthwtolocateclustersofclockdeviationvalues.
`ThisisdonebyaligningtheleftborderofthewindowwitheachvaluexiXrj.The
`windowspanningtherangeofvalues[xi;xi+w]isreferredtoastheithwindowinstance
`(wi).Ifx`Xrjisthelargestclockdeviationvaluesuchthatxi(cid:20)x`(cid:20)xi+w,thenthe
`cardinalityofwi(thenumberofclockdeviationvaluesinwi)isgivenbypi=`(cid:0)i+ .
`Amongallnpossiblewindowinstances,SWAselectsawindowinstancewesuchthat
`max(p ;p;:::;pn)=pe.Iftwoormorewindowinstanceswa;wb;:::existsuchthatpa=
`pb=:::=pe,thenanadditionalcriterionisusedforwindowselection.Twopossibilities
`aretodeterministicallyselectthe(cid:12)rstwindowinstancewithcardinalitype,ortoselectthe
`windowinstancewithminimumvarianceamongthosewithcardinalitype.Onceawindow
`instanceweisselected,theclockcorrectiontermcanbecalculatedbytakingeitherthemean
`orthemedianofthevaluesinwe.Thisresultsinatotaloffourvariationsofthealgorithm:
`SWAmedian,SWAdetmedian,SWAmean,andSWAdetmean[ ].Duetoseveraladvantagesdiscussed
`in[ ],SWAdetmeanwasselectedforourimplementation.Theclockcorrectionterminnodej
`(CORRj)computedbySWAdetmeanisgivenbyCORRj=(pe)(cid:0) Pe+pe(cid:0)
`xi.
`i=e
`Thesizeofthewindowframe(w)isanimportantparameterinallvariationsofSWA.
`ForSWAdetmean,theoptimalwindowsizeis(cid:1)int+dvar[ ].Awindowofsizew= ms
`wasselectedfortheimplementationofSWAusedduringourexperiments.Thiswasdone
`becauseabout%ofall\good"clockdeviationestimatesthatwerecollectedduringour
`experimentswiththeSWAalgorithmremainbelowthe -msthreshold,meaningthata
`windowofsimilarsizecorrectlyselects\good"clockswithveryhighprobability.
`:Experimentalresults
`. :Messagedelaydistributionandalgorithmperformance
`Theexperimentsdescribedinthissectionwereconductedinanenvironmentinwhich
`themessagedelaytypicallyfollowsadistributionsimilartothatshowninFigure . The
`maincharacteristicofinterestisthelongandthintailofthedistribution.Althougha
`maximumdelaydmaxmaybepresent,itsvalueisusuallymuchgreaterthandmin.
`Whilethevastmajorityofmessagedelaysoccurinasmallrangearoundtheexpected
`delay,outliers(messageswithverylongdelays)dooccurwithsomeregularity.Itisthese
` Asimilardistributionwasreportedinadi(cid:11)erentenvironmentbyCristian[].
`
`
`
`PAGE 5 OF 10
`
`SONOS EXHIBIT 1010
`IPR of U.S. Pat. No. 8,942,252
`
`

`

`d
`
`min
`
`Message delay
`
`% of
`messages
`
`Figure 1. Typical message delay distribution
`
` IEEEWorkshoponFault-Tol.Par.andDist.Syst.,CollegeStation,TX,June - .(Appearsin
`Fault-Tol.Par.andDist.Syst.,D.PradhanandD.Avresky,eds.,IEEEComp.Soc.Press,pp.-.)
`outliersthatposedi(cid:14)cultyforclocksynchronizationalgorithms.Recall,however,that
`allconvergencefunctionsstudiedinthispaperprovideadegreeoffaulttolerance,and
`thereforehavesomecapabilityofrejectingoutliers.Naturally,theabilitysuchafunction
`hasin(cid:12)lteringoutliersdecreaseswiththenumberofexistingfaultsinthesystem.
`Inanycase,Figure illustratesthatasmallimprovementinthepercentageofoutliers
`thatarerejectedbyagivenconvergencefunctionproducesasigni(cid:12)cantreductioninthe
`rangeofthedelaysofthemessagesthattakepartinthecomputationoftheclockcorrection
`term.This,inturn,resultsinasigni(cid:12)cantimprovementinclocksynchronizationtightness.
`FTMA'sabilitytorejectoutliersdecreasesquicklyasthenumberoffaultoccurrencesin
`thesystemapproachesk.Inparticular,ifallktolerablefaultsoccur,asingleoutliercan
`severelya(cid:11)ectthecorrectiontermcomputedbyFTMA.AEFTMAoutperformsFTMAin
`thisaspectbymoderatingtheimpactofoutliersthroughitsexponential-averagingprocess.
`However,ifoutliersareproducedtoooftenoveranextendedperiodoftime(due,for
`example,toanextendedperiodofveryhighloadinthesystem),AEFTMAwilllosethe
`abilityto(cid:12)lterthem.SWA,ontheotherhand,naturallydiscardsoutliersduetoitshigh
`degreeoffaulttolerance[ ].Hence,evenwhenotheralgorithmshavereachedthelimitof
`theirfaulttolerance(andthereforehavelosttheirabilityto(cid:12)lteroutliers),SWAcontinues
`totreatoutliersasfaultyvaluesandnaturallydiscardsthem.
`.:Generalinformationabouttheexperiments
`Thealgorithmsdescribedintheprevioussectionwereimplementedinanapplication-
`levelprogramandtestedonanEthernetnetworkconnecting SUNworkstations.Data
`collectionwasachievedbywritingaspecialversionoftheclocksynchronizationsoftware,
`whichhasthecapabilityofsavingthefollowingvaluesattheendofeachroundofthe
`algorithm:clockdeviationvector,maximumandminimumclockdeviationinthatround,
`clockcorrectionterm,andnumberofmessagesreceivedduringthatround.Someofthe
`maincharacteristicsofourimplementationaretheutilizationofUNIXsystemcallsfor
`time-stampingofbothtransmittedandreceivedmessages,aresynchronizationintervalof
` s,andtheutilizationofabroadcastmechanismtoexchangeclockvalues.Broadcast
`isaccomplishedviaUDP(userdatagramprotocol)datagrams.Ourimplementationis
`describedinfurtherdetailin[].
`Di(cid:11)erentversionsofthesoftwarewerecreatedtoinjectfaultsintothesystem.Excessive
`clockdrift,lossofsynchronizationmessages,transientclockvaluechange,andtwo-faced
`faults(afaultynodethatsendsdi(cid:11)erentclockvaluestodi(cid:11)erentnodes)weresimulated
`duringourexperiments.Threefaultsofthesametypewereinjectedintothesystemineach
`experiment.Duetospaceconstraints,wepresentinthispaperonlytheresultsobtained
`whilesimulatingtwo-facedfaults.Theotherexperimentsaredescribedindetailin[].
`References[]and[],aswellassourceandexecutablecodesoftheclocksynchronizationsoft-
`wareusedinourexperiments,areavailableviaanonymousftpatmazatlan.ece.uci.edu,inthedirectory
`pub/clocksynch/unixcomplete.
`
`
`
`PAGE 6 OF 10
`
`SONOS EXHIBIT 1010
`IPR of U.S. Pat. No. 8,942,252
`
`

`

` IEEEWorkshoponFault-Tol.Par.andDist.Syst.,CollegeStation,TX,June - .(Appearsin
`Fault-Tol.Par.andDist.Syst.,D.PradhanandD.Avresky,eds.,IEEEComp.Soc.Press,pp.-.)
`Thetypesoffaultsthatweresimulatedinourexperimentsarerepresentativeofsome
`possiblebehaviorsaByzantinefaultynodecanexhibit.AlthoughaByzantinefaultmodel
`isusuallyconsideredforhighlycriticalapplications,thegeneralityofthemodelmotivated
`ustoadoptitinourimplementation.Themodelalsoallowedustoobtainamorecomplete
`evaluationofFTMA,AEFTMA,andSWAinanenvironmentwithhighmessagedelay
`variation,sincewewereabletoconductexperimentswithvarioustypesoffaults.
`Inallexperimentsdescribedinthispaper,theclocksynchronizationsoftwareranasa
`highprioritytask.Inaddition,twolong-runapplicationprogramswerestartedinevery
`nodeinthesystem,providingatestenvironmentwithhighCPUandnetworkutilization.
`OneoftheseprogramsmonitoredaspectssuchasCPUandnetworkutilization,whilethe
`otherconsistedofanexhaustivesearchprogram.Whilethe(cid:12)rstprogramgeneratesa
`reasonableamountofsystemCPUload,thesecondonegeneratesmainlyintensiveuser
`CPUload.Inaddition,networktra(cid:14)cisgeneratedbybothprograms,whichweredesigned
`tosaveresultsperiodicallytoexternalstorageusingtheEthernetlocalareanetwork.The
`datacollectedbythemonitoringprogramwascomparedwithdatafromtypicalworking
`mid-dayhours,showingasimilaramountofpeakCPUandnetworkutilization.
`Asummaryofthedatacollectedduringourexperimentswithsimulatedtwo-facedfaults
`ispresentedinTable .Thesedataarediscussedindetailinsubsequentsubsections.Note
`thatthissummarycontainsonlydatacollectedbynonfaultynodes,becausefaultynodes'
`valuesdonotcontributetoclocksynchronizationtightness.
`AfewcommentsmighthelpthereaderunderstandthedatapresentedinTable .All
`experimentsconsistedofsynchronizationrounds,inwhichfaultsweresimulatedduring
`rounds.Thedatacollectedduringroundsinwhichfaultswereabsentfromandpresent
`inthesystemissummarizedinthe(cid:12)rstandthelast(cid:12)verowsofTable ,respectively.
`Duringtheroundsinwhichfaultsweresimulated,theclockvaluesentbyafaultynode
`deviatedfromtheactualtimebyabout- secondforsomenodesandabout secondfor
`theremainingnodes.
`Inallrounds,clockdeviationestimateswerecomputedbynonfaultynodesaccordingto
`Equation .Thesmallestandthelargestclockdeviationestimatescomputedbetweenany
`twononfaultynodesiandjduringanexperimentarereferredtoasminimumandmaximum
`clockdeviationestimatesinTable ,respectively.Asexplainedabove,these(cid:12)guresare
`measuredintwosituations,namelywhenfaultsareabsentfromandwhenfaultsarepresent
`inthesystem.Notethat,duetotheinaccuracyintroducedbymessagedelayvariationin
`thereadingofclocks,theminimumandmaximumclockdeviationestimatesshownin
`Table cannotbeusedtoestimatetheworst-caseclocksynchronizationtightness((cid:1)int)
`oftheimplementation.Rather,thedi(cid:11)erencebetweenthesetwovaluesisrepresentativeof
`thesystem'smessagedelayvariation(dvar)anditsimpactontoclocksynchronization.The
`justi(cid:12)cationforthisisasfollows.TheestimateforthemessagedelayusedinEquation
`(drmed(i;j))istypicallynotmuchgreaterthantheminimumdelaydmin.However,duetothe
`natureofthemessagedelaydistributionshowninFigure ,largepositiveclockdeviation
`estimatescanbecomputedasadirectconsequenceoflargedelaysthatcanbeexperienced
`byparticularclocksynchronizationmessages.Inturn,thecombinede(cid:11)ectofinaccurate
`clockreadingsandfaultscancauseanodetocomputealargeclockcorrectionterm.When
`excessivecorrectionisappliedtoanode'sclock,thenodetendstocomputelargenegative
`clockdeviationestimatesinthefollowinground.
`Table alsoshowstheaverageandthemaximumclockcorrectiontermscomputedby
`nonfaultynodesduringtheexperiments,respectivelyintheabsenceandinthepresence
`offaults.Thesetwo(cid:12)guresaretrulyrepresentativeoftheclocksynchronizationtightness
`achievedbyeachinteractiveconvergencefunctionthatwetested.Infact,wecanestimate
`
`
`
`PAGE 7 OF 10
`
`SONOS EXHIBIT 1010
`IPR of U.S. Pat. No. 8,942,252
`
`

`

` IEEEWorkshoponFault-Tol.Par.andDist.Syst.,CollegeStation,TX,June - .(Appearsin
`Fault-Tol.Par.andDist.Syst.,D.PradhanandD.Avresky,eds.,IEEEComp.Soc.Press,pp.-.)
`alowerboundfor(cid:1)intbytakingonehalfofthemaximumclockcorrectiontermobserved
`duringeachexperiment(CORRmax).Therefore,duringanygivenexperimentdescribedin
`thissectiontheworst-caseclocksynchronizationtightnesssatis(cid:12)es(cid:1)int(cid:21)CORRmax=.
`Sincenogoodupperboundfor(cid:1)intcanbecalculatedfromourmeasurements,weuse
`CORRmaxasanestimatefortheworst-caseclocksynchronizationtightness.Thisassumes
`thatthesynchronizationalgorithmsworkproperly,andhencetheamountofcorrection
`performedisanindicationofhowtightlysynchronizedtheclocksare.Thisisjusti(cid:12)edin
`partbythefactthatthealgorithmsweemployhavebeenprovedcorrectinpreviousstudies.
`Asimilartechniquewasusedin[]toestimatethesynchronizationtightnessachievedby
`NTP(NetworkTimeProtocol).
`Faults
`Typeofmeasurement
`FTMA
`AEFTMA
`SWA
`Minimumclockdeviationestimate
`-ms
`-ms
`-ms
`Maximumclockdeviationestimate
`ms
` , ms
`ms
`AbsentAverageclockcorrectionterm
` ms
` ms
` ms
`Maximumclockcorrectionterm
`ms
` ms
`ms
`(cid:21) .ms(cid:21).ms(cid:21) ms
`Worst-casesync.tightness((cid:1)int)
`Minimumclockdeviationestimate
`- ,ms
`-ms
`- ms
`Maximumclockdeviationestimate
` , ms
` ,ms
` , ms
`PresentAverageclockcorrectionterm
` ms
` ms
` ms
`Maximumclockcorrectionterm
`ms
` ms
` ms
`(cid:21) .ms(cid:21) ms(cid:21)ms
`Worst-casesync.tightness((cid:1)int)
`. :ExperimentalresultswiththeFTMAalgorithm
`AsTable indicates,theFTMAalgorithmishighlysensitivetolargevariationsinthe
`messagedelay,particularlyinthepresenceoffaults.Beforefaultswereinjectedintothe
`system,clockdeviationestimatesrangingfrom-mstomswereobserved,whilethe
`largestclockcorrectiontermcomputedamongallnonfaultynodeswasms.Afterfaults
`wereinjectedintothesystem,clockdeviationestimatesvariedfrom- ,msto , ms,
`whilethelargestclockcorrectiontermwasms.
`Suchabehaviorcanbeexplainedbythesensitivityofanapplication-levelimplementation
`tothehighmessagedelayvariationusuallyobservedinanenvironmentwithhighCPUand
`networkloadlevels.Runningasanapplication-levelprogram,theclocksynchronization
`processmustcompetefortheCPU,beingunabletopreciselytime-stampmessageswhenever
`itisnotintherunningstate.Inaddition,highernetworkloadincreasestheprobabilityof
`occurrenceofcollisions,whichalsocontributestoalargermessagedelayvariation.
`Now,assumeasysteminwhichk(thenumberoftolerablefaults)faultynodesexist.
`Iftheclockofanonfaultynodeisreadwithalargeerrorduetoalongermessagedelay,
`acorrespondinglylargeclockdeviationestimateresults.Particularlyinthecaseofthe
`FTMAalgorithm,suchanestimatemaya(cid:11)ectthecomputationoftheclockcorrection
`termbyalargeamountsincetheactualnumberof\good"clockdeviationestimatesthat
`areavailableduringtheroundislessthan(n(cid:0)k).Inotherwords,nonfaultyclockvalues
`whicharereadwithalargeerrorcannotbeconsideredas\good"values.
`Ifthecombinednumberoffaultsandinaccuratelyreadclockvaluesexceedsk,anexces-
`siveestimateoftheclockcorrectiontermmayresult.DuetotheproblemthatFTMAhas
`
`
`Table 1. Summary of experimental results (simulation of two-faced faults)
`
`
`PAGE 8 OF 10
`
`SONOS EXHIBIT 1010
`IPR of U.S. Pat. No. 8,942,252
`
`

`

` IEEEWorkshoponFault-Tol.Par.andDist.Syst.,CollegeStation,TX,June - .(Appearsin
`Fault-Tol.Par.andDist.Syst.,D.PradhanandD.Avresky,eds.,IEEEComp.Soc.Press,pp.-.)
`inhandlingthisenvironment,itsworst-caseclocksynchronizationtightnessisnotgood.
`ForFTMA,(cid:1)intsatis(cid:12)es(cid:1)int(cid:21) :msand(cid:1)int(cid:21) :ms,respectively,beforeand
`afterinjectionoffaultsintothesystem.
`.:ExperimentalresultswiththeAEFTMAalgorithm
`AsTable indicates,theAEFTMAalgorithmprovidessomeimprovementincomparison
`totheFTMAalgorithm,bothwithrespecttothelowerboundfor(cid:1)intandwithrespect
`totheaverageclockcorrectionterm.Beforefaultswereinjectedintothesystem,clock
`deviationestimatesrangingfrom-msto , mswereobserved,whilethelargestclock
`correctiontermcomputedamongallnonfaultynodeswas ms.Afterfaultswereinjected
`intothesystem,clockdeviationestimatesvariedfrom-msto ,ms,withthelargest
`clockcorrectiontermbeingequalto ms.Hence,theworst-caseclocksynchronization
`tightnessresultingfromtheAEFTMAalgorithmsatis(cid:12)es(cid:1)int(cid:21):msand(cid:1)int(cid:21)
` ms,respectively,beforeandafterinjectionoffaultsintothesystem.
`ThebetterperformanceofAEFTMAincomparisontoFTMAcanbeattributedtothe
`laggingmechanismofAEFTMA,whichwasexplainedearlierinthispaper.Inthepresence
`ofinaccurateclockreadings,AEFTMAdelaysthecomputationofexcessiveclockcorrection
`termsaccordingtothecurrentvalueof(cid:12)(r).Inasystemwithcontinuouslyhighloadlevels,
`however,inaccurateclockreadingsmayoccurinseveralconsecutiverounds.Eventually,
`theweightfactorissettoalargervalue(suchas(cid:12)(r)= ),causingAEFTMAtobehave
`similarlytoFTMA.Notethatsuchabehaviorislesslikelytohappeninanenvironment
`wherehigherCPUandnetworkutilizationlevelsoccurinbursts.
`.:ExperimentalresultswiththeSWAalgorithm
`AsTable indicates,SWAprovidesasigni(cid:12)cantimprovementincomparisontothe
`previousalgorithms,particularlyinthepresenceoffaults.Beforefaultswereinjected
`intothesystem,clockdeviationestimatesrangingfrom-mstomswereobserved,
`whilethelargestclockcorrectiontermcomputedamongallnonfaultynodeswasms.
`Afterfaultswereinjectedintothesystem,clockdeviationestimatesvariedfrom- ms
`to , ms,withthelargestclockcorrectiontermbeingequalto ms.Theworst-case
`clocksynchronizationtightnessresultingfromtheSWAalgorithmsatis(cid:12)es(cid:1)int(cid:21) ms
`and(cid:1)int(cid:21)ms,respectively,beforeandafterinjectionoffaultsintothesystem.
`Notethatasigni(cid:12)cantimprovementinboththelowerboundfor(cid:1)intandtheaverage
`clockcorrectiontermisachievedbySWAafterfaultsareinjectedintothesystem.This
`isaclearindicationthatSWAcorrectlyselects\good"clockvaluestocomputetheclock
`correctionterm,(cid:12)lteringoutinaccurateclockreadingswithitsslidingwindowmechanism.
`Inotherwords,largeclockdeviationestimatesresultingfrommessageswithlongdelaysare
`treatedasfaultsandarecorrectlyeliminatedfromthecomputationoftheclockcorrection
`term.Notethatthisbehavioralsocontributestoreducingtherangeintheclockdeviation
`estimatesincomparisontoFTMAandAEFTMA.
`ThecapabilityofSWAtoselectclustersofgoodclockvaluesisextremelygood.The
`largestclockcorrectiontermshowninTable ( ms)resultedfromtheonesingleround
`inwhichSWAselectedaclusterofinaccurateclockreadingsduringtheexperiment,which
`mightoccurwhenmultiplemessagesarereceivedfromnonfaultynodeswithnearlyidentical
`longdelays.Theprobabilityofoccurrenceofamisplacedwindowincreaseswhenfewer
`\good"clocksarepresentinthesystemduetotheoccurrenceoffaults.Eveninthepresence
`offaults,theprobabilityofoccurrenceofamisplacedwindowframeisverysmall.During
`theexperimentcurrentlybeingdescribed,misplacedwindowframesoccurredduringonly
`
`
`
`PAGE 9 OF 10
`
`SONOS EXHIBIT 1010
`IPR of U.S. Pat. No. 8,942,252
`
`

`

` IEEEWorkshoponFault-Tol.Par.andDist.Syst.,CollegeStation,TX,June - .(Appearsin
`Fault-Tol.Par.andDist.Syst.,D.PradhanandD.Avresky,eds.,IEEEComp.Soc.Press,pp.-.)
`.%oftheroundsamongallnonfaultyworkstations.During .%oftherounds,the
`clockcorrectiontermscomputedbySWAinthepresenceoftwo-facedfaultswerelessthan
`ms.Infact,asshowninTable ,theaveragecorrectionterm(andhencetheaverage
`estimatedsynchronizationtightness)inthissituationisonly ms,whichisapproximately
`oneorderofmagnitudebetterthanthecorrespondingaveragesofFTMAandAEFTMA.
`:Conclusion
`Inthispaper,wepresentedthemeasuredperformanceofthreedi(cid:11)erentfault-tolerant
`clocksynchronizationalgorithmsinadistributedUNIXenvironment.Thealgorithmsthat
`weretestedinthisenvironmentwerethefault-tolerantmidpointalgorithm,theadaptive
`exponentialaveragingfault-tolerantmidpointalgorithm,andtheslidingwindowalgorithm.
`Amajorobstacletoachievingclocksynchronizationismessagedelayvariation.Our
`experimentswerecarriedoutwithanapplication-levelimplementation,andtheyrevealed
`thatthemessagedelaycanvarybyseveralhundredsofmilliseconds.Atheoreticallower
`boundfortheworst-caseclocksynchronizationtightness((cid:1)int)thatcanbeachievedin
`anenvironmentwithmessagedelayvariationdvarisdvar( (cid:0) =n)[].Accordingtothis
`lowerbound,oneshouldexpectthe(cid:1)