a core programming model for global computing

ULMACoreProgrammingModelforGlobalComputing(*)G´erardBoudolINRIASophiaAntipolisBP93–06902SophiaAntipolisCedex,FranceAbstractWeproposeaprogrammingmodeltoaddresstheunreliablecharacterofaccessingresourcesinaglobalcomputingcontext,focusingongivingaprecisesemanticsforasmall,yetexpressivecorelanguage.Todesignthelanguage,weuseideasandprogrammingconstructsfromthesynchronousprogrammingstyle,thatallowustodealwiththesuspensivecharacterofsomeoperations,andtoprogramreactivebehaviour.Wealsointroduceconstructsforprogrammingmobileagents,thatmovetogetherwiththeirstate,whichconsistsofacontrolstackandastore.Thismakestheaccesstoreferencesalsopotentiallysuspensive.Weshowhowtopredict,byastaticanalysis,thatsomeusesofreferencesmaybeconsideredassafe,thatis,theydonotneedtestingthepresenceofthereference.1.IntroductionAccordingtotheglobalcomputingvision,“Inthefuturemostobjectsthatweworkwithwillbeequippedwithprocessorsandembeddedsoftware[...]Manyoftheseobjectswillbeabletocommuni-catewitheachotherandtointeractwiththeenvironment”[19].Inaword:processorseverywhere.Thisisgraduallybecomingareality:besidescomputersandlaptops,orpersonalassistants,nowa-daystelephonesandsmartcardsalsoareequippedwithprocessors,aswellascars,planes,audioandvideodevices,householdappliances,etc.Thenaquestionis:willwebeabletoexploitsuchahighlydistributedcomputingpower?Howwillwecomputeinsuchacontext?Thereareclearlymanynewfeaturestodealwith,andmanyproblemstoaddressinordertobeableto“computeglobally”.Forinstance,thedistributedprocessorsarenotorganizedintoanetworkintheusualsense.Newprotocolshavetobeinvented.Offerredhardwareandsoftwareresourcesarehighlyheterogeneous,andinsomecasestherunningapplicationshavetodealwithphysicallylimitedresources.Theglobalcomputingcontextisalsohighlyunreliableinmanyrespects,and,inpartic-ular,securityissuesmaybecomecritical.AspointedoutbyCardelli[9,10],theglobalcomputingcontextintroducesnewobservables,“soradicallydifferentfromthecurrentcomputationalnormthattheyamounttoanewmodelofcomputation”.Hetheninvented,togetherwithGordon,theMobileAmbients[12],asacomputingmodeltodealwiththecrossingofbarriers.Inthispaperweaddressonespecificaspectofthisglobalcomputingvision,namelythefactthat“Theavailabilityandresponsivenessofresources[...]areunpredictableanddifficulttocontrol”(*)WorkpartiallysupportedbytheMIKADOprojectoftheIST-FETGlobalComputingInitiative,andtheCRISSprojectoftheACIS´ecurit´eInformatique.1[19].Thisisindeedsomethingthateverybodycanalreadyexperimentwhilebrowsingtheweb:quiteoften,weobservethatanURLappearsinaccessible,forvariousreasonswhicharenotalwaysclearlyidentified–failureofanode,insufficientbandwidth,congestion,transientdisconnection,impossibilitytocrossafirewall,etc.Wewouldliketohavesomeabilitytoreactandtakeactionstobypasstheseobstacles.ThisiswhatCardelliprovidedforus,withservicecombinatorsforscriptingtheactivityofwebbrowsing[11].Cardelli’scombinatorsarequitespecific,however:onlythetimeandrateoftransmissioncanbeusedasparametersforareaction.Wewouldliketohaveprogrammingconstructstodealwithmoregeneralsituationswheretheavailabilityandresponsivenessofresourcesisnotguaranteed.Thisisnotprovidedbytraditionalcomputingmodels.Forinstance,inaLAN,thefactthatsomefileisunreachableisconsideredasanerror–unlessthisisprescribedbysomesecuritypolicy–,andalatencyperiodthatexceedsnormalresponsetimesandcommunicationdelaysisthesignofafailure.Inglobalcomputing,bycontrast,tryingtoaccesssomethingwhichis,maybetemporarily,absentorunavailableappearstobetherule,ratherthantheexception.Suchafailureshouldnotberegardedasafatalerror.Weshouldratherhavemeanstodetectandreacttothelackofsomething.Atypicalscenariowherethesepartialfailuresoccuristheoneofmobilecode,whichisthoughtofasageneraltechniquetocopewiththenewobservablefeaturesoftheglobalcomputingcontext[10,17].Forinstance,amobilecode(whichmaybecodeembeddedinamobiledevice)mayfailtolinkwithsomespecificlibrariesitmightneedatavisitedsite,ifthesitedoesnotprovidethem.Inthiscase,adefaultbehaviourshouldbetriggered.Conversely,themobilecodemaybeunreachablefromasitewhichissupposedtomaintainconnectionswithit.Insuchacase,theuserwhohasdelegatedthemobileagent,orwhotriestocontactaremotemobiledevice,forinstance,hastowaitand,afterawhile,takesomedecisions.Themodelweshallusetodealwithabsence,waiting,andreactionsisbasicallythatofsyn-chronousprogramming[2,18].Thisdoesnotmeanthat,inourapproach,somethinglikethewebistoberegardedasasynchronoussystem.Werathertaketheviewthattheglobalcomputingworldisa(wide)GALS,thatis,a“globallyasynchronous,locallysynchronous”network.Onlyatalocalleveldoesanotionoftimemakesense,whichservesasthebasisfortakingdecisionstoreact.Asregardsthewaytoprogramreactions,wefollowtheEsterelimperative(orcontrol-oriented)style[4,5],whichseemsmoreappropriateforourpurposethantheLustredataflowstyle[18].However,inEsterelaprogramisnotalways“causallycorrect”,andastaticanalysisisneededtocheckcorrectness.Thischeckingisnotcompositional,andmorespecifically,theparallelcompositionofcausallycorrectprogramsisnotalwayscorrect.Fromthepointofviewofglobalcomputing,thisisunfort