On real-time and non real-time distributed computi

OnReal-TimeandNonReal-TimeDistributedComputingG.LeLannINRIA-BP10578153LeChesnayCedex,FranceE-ma~l:[e-mail],takinganalgorithmicviewpoint,weexplorethedifferencesexistingbetweentheclassofnonreal-timecomputingproblems(R~)versustheclassofreal-timecomputingproblems(~).WeshowhowaprobleminclassRNcanbetransformedintoitscounterpartinclass~.Claimsofreal-timebehaviormadeforsolutionstoprob-lemsinclass~areexamined.Ahexampleofadistributedcomputing.....I....problemarisingmclassIsstudmd,alongwithitssolutmn.Itisshownwhyoff-linestrategiesorschedulingalgorithmsthatarenotdrivenbyreal-time/timelinessrequirements~areincorrectforclass~.Finally,aunifiedapproachtoconceivingandmeasuringtheefficiencyofsolutionstoproblemsinclassesR~and~isproposedandillustratedwithafewexamples.1INTRODUCTIONOverthelast20years,thedistributedalgorithmscommunityhasspentconsider-ableeffortsolvingproblemsintheareasofserializableorlinearizableconcurrentcomputing.TheseproblemsbelongtoaclassdenotedR~,theclassofnonreM-timecomputingproblems.Separately,overthelast30years,thereal-timealgorithmscommunityhasspentconsiderableeffortsolvingschedulingproblemsintheareaofcentralizedcomputing,consideringpreemptableandnon-preemptableresources.Onlyre-centlyhasdistributedcomputingreceivedsomeattention.Theseproblemsbe-longtoaclassdenoted~,theclassofreal-timecomputingproblems.Inthispaper,takinganalgorithmicviewpoint,weembarkonexploringthedifferencesbetweenbothclasses.Thescopeofthispaperisrestrictedtothatofdeterministicalgorithms.Besidesintellectualinterest,investigationoftheseissuesisexpectedtobringthetwocommunitiescloser,viatheclarificationofafewessentialconcepts.Inparticular,wehaveobservedthatthequalifiersreal-timeanddistributedmaynotcarrythesamemeaninginbothcommunities.Broadlyspeaking,withfewexceptions,thedistributedalgorithmscommunitydoesnotconsiderproblemspecificationsthatincludereal-timerequirements.Conversely,thereal-timealgorithmscommunityoftenfailstounderstandwhatisimpliedwithconsideringadistributedcomputingproblem.Theremainderofthispaperisorganizedasfollows.Insection2,weintroducethedistinctiveattributesofclass~.Insection3,weexamineclaimsofreal-time52behaviormadeforsolutionstoproblemsinclassR~.Insection4,weintroduceaproblemofdistributedcomputingthatbelongstoclass~,alongwithitssolution.Aunifiedapproachtoconceivingandmeasuringtheefficiencyofsolutionstoproblemsinbothclassesisproposedinsection5.Inthispaper,wehavepurposedlyputmoreemphasisonproblemsandsolu-tionsinclass~,giventheintendedaudience.2CLASS~VERSUSCLASSR~RPROBLEMSQuiteoften,itisbelievedthatreal-timemeansfast.Forexample,thedistinc-tionbetweenmeetingspecifictimeboundsthatarespecifiedapriori(whichisametric-freeproblem)ontheonehand,andobservableresponsetimesaresmall(whichisanimplementationdependentconsideration)ontheotherhand,doesnotseemtobewellunderstood.F~rexample,ithasbeenrecentlystatedthat...protocolslikeIsis,Horus,TransisandTotemarereal-timeprotocolsifoneisconcernedwithreal-timedeadlinesofminutesortensofseconds....Astheseprotocols-andtherelatedAsynchronousConsensusproblem-arereasonablyweltunderstood,itseemsappropriatetousethemtocarryoutananalysisinordertoexplainwhystatementssuchastheonereportedabovearemeaningless.Wewillfirstintroducesomenotations,andthenpresentthedistinctiveat-tributesofproblemsinclass~,beforeproceedingwiththeanalysisinsection3.2.1NotationsCorrectnessRecallthat,inthecontextofthispaper,asolutionisanalgo-rithmanditsassociatedmodelsandproofs.ThespecificationofanyproblemPcomprisesthefollowingsubsets:-thespecificationofsomeassumptions,denoted-thespecificationofthepropertiessought,denotedA.AssumptionsareequivalenttoaxiomsinMathematics.Essentially,assump-tionscoverthemodelsconsidered,namelythecomputationalmodels,thefailuremodels,themodelsofeventreleases.Examplesofpropertiesofinterestaresafety,liveness,timeliness.Similarly,thespecificationofanysolutionAcomprisesthefollowingsubsets,inadditiontothespecificationofA:-thespecificationofsomeassumptions,denoted7,-thepresentationoftheproofsthatsomepropertiesFhold,given7.Wheneveramodelorasetofpropertiesxldominatesanothermodeloranothersetofpropertiesx2,i.e.xlismoregeneralthanx2,thiswillbedenotedbyxl__Dx2,_Dbeingtheinclusionsymbol.ItissaidthatAsolvesproblemPifthefollowingcorrectnessconditionshold:53[ccl]:F(A)DA(P)and[cc2]:7(A)__DA(P).Formostproblems,establishingcorrectnessconditionsentailstheexpressionoffeasibilityconditions,denoted[fc].Ausefulinterpretationofthesecorrectnessconditionsisasfollows:withA,asystemisprovedtobeendowedwithpropertiesthatareatleastequalto(asstrongas)thoserequired,assumingadvanceknowledgethatisatmostequalto(notricherthan)thatgivenintheexpositionofP.Theseconditionsmayseemtrivial.Nevertheless,quitesurprisingly,manypublishedpapersdescriberesultsthatviolate[cct]or[cc2]orboth.Typically,somepapersexploretradeoffsbetweenvarioussolutions,andconcludewithsomeparticulardecisionsuchasAtisbetterthanA2,becauseAtislesscostlythanA~,totallyignoringthefactthatA1islesscostlyforthesolereasonthatA1isbasedonpostulatinggl,whichviola