Experience-based trust Enabling effective resource selection in a grid environment

NathanGriffiths1andKuo-MingChao2

1

DepartmentofComputerScience,UniversityofWarwick,

Coventry,CV47AL,UKnathan@dcs.warwick.ac.uk

2

SchoolofMIS,CoventryUniversity,

Coventry,CV15FB,UKk.chao@coventry.ac.uk

Abstract

TheGridvisionistoallowheterogeneouscomputationalresourcestobesharedandutilisedglobally.Gridusersareabletosubmittaskstoremoteresourcesforexecution.However,theseresourcesmaybeunreliableandthereisariskthatsubmittedtasksmayfailorcostmorethanexpected.Thenotionoftrustisoftenusedinagent-basedsystemstomanagesuchrisk,andinthispaperweapplytrusttotheproblemofresourceselectioninGridcomputing.Weproposeanumberofresourceselectionalgorithmsbasedupontrust,andevaluatetheireffectivenessinasimulatedGrid.

1Introduction

Distributedcomputersystemscanbeviewedasmulti-agentsystemsinwhichindivid-ualautonomousagentscooperatetoachievetheirobjectives.Itisthroughcooperationthatsuchagentsareabletofunctioneffectively,sincetheytypicallylacktheknowl-edge,capabilitiesorresourcestoachievetheirobjectivesalone.Gridcomputingcanbeviewedasamulti-agentsystemthatallowsuserstodiscover,selectanduseremoteresources[15].Theprocessofausersubmittingatasktoaresource,andthatresourceperformingthetaskontheuser’sbehalf,canbeviewedascooperation.Bothusersandresourceshavecontrolovertheirownbehaviour,andsoareautonomousagentshavingtheirowndecisionmakingmechanisms.Bydefinition,however,autonomousagentsthatcontroltheirownbehaviouralsocontrolhowtheycooperate.Inparticu-lar,autonomousagentsdetermineforthemselveswhentoinitiatecooperation,whentoofferit,andwhentorescindcooperativecommitments.Consequently,whenagents

cooperate,anyoneofthemcanceasecooperationatanytime,(typically)causingthewholeinteractiontofail.InaGridcomputingenvironmentautonomymanifestsitselfthroughusersandresourcesbeingabletochangethenatureoftheircooperation,orevenceasingtocooperate,atanytime.Forexample,aresourcemayreducethepri-orityofauser’staskcausingittooverrun,ormayceaseprocessingoneuser’staskinfavourofanother.

Whenenteringintocooperation,agentsinamulti-agentsystemareenteringintoanuncertaininteractioninwhichthereisariskoffailureduetothedecisionsandac-tionsofothers.Tofunctioneffectivelyagentsmustmanagethisrisk,andthenotionoftrustcanusedtoprovideasuitablemechanism.Inthispaper,wedescribehowtheconceptoftrustcanbeusedtomanagecooperativeinteractions,inthecontextofGridcomputing.Inparticular,weprovideamechanismforuseragentstousetrustforresourceselection,i.e.tochoosethemostappropriateresourceforatask.AlthoughseveralresearchershaveconsideredtheproblemofresourceselectioninaGriden-vironmentfromtheperspectiveofminimisingcost[3,16],relativelyfewhavebeenconcernedwithminimisingtaskfailure[1,2].Thosethatdoconsiderfailuretendtouserestrictivetrustmodels,andoftendonotconsiderthecostoftaskexecution1.

Inthefollowingsection,weintroducetheGridcontextinmoredetailandillustratetheproblemsthattrustcanaddress.InSection3wedescribethenotionoftrust,andthetrustmodelthatweuse,andinSection4wedescribehowtrustcanbecomparedusingastrict,stratified,orwindowedapproach.TheapplicationoftrusttotheresourceselectionproblemisdescribedinSection5.OurapproachhasbeenimplementedinasimulatedGridasdescribedinSection6,andinSection7wegivedetailsofourresults.Finally,inSection8wegiveourconclusionsandoutlineongoingwork.

2Context:GridComputing

Gridcomputingprovidesamechanismforuserstodiscover,selectandutiliseremoteresources.AlthoughmostexistingGridsarefairlylocalised,theGridvisionistoallowresourcesharingonaglobalscale,whereresourceschargeusersforexecutingtheirtasks.Resourcesareheterogeneous,geographicallydistributedandlocallycontrolled,andhavespecificindividualcapabilitiesintermsoftheirprocessorarchitecture,net-workbandwidthetc.thataremadeavailableforanassociatedcost.Gridresourcesmaybeunreliableandmayerroneouslyfailtoexecuteatask,orcircumstancesmaycausethemtodelayordropexecutionofaremoteuser’stask.Anexampleoftheformeriswherehardwareornetworkproblemscauseatasktofail.Thelattercaseisillustratedbyaresourcedroppingatasksubmittedbyoneuser,infavourofthatsubmittedbyanotheruserwhoisconsideredtobeofhigherpriority.Forexample,remoteusers’tasksmaybedroppedinfavouroflocalusers,ortaskssubmittedbylowpayingusersmaybedroppedinfavourofauserthatpaysahigherrate.

Whendeterminingwhichresourcetosubmitataskto,aGriduserwilltypicallytrytominimisethecostofexecutingthetask(possiblyconsideringtimeinadditiontofinancialcost)andtominimisetheriskofthetaskfailing.Theseaimsmayconflict

ResourceMachinePEPEPEPEresultstask submitUser agentResource modelUserFigure1:Asingleuser’sperspectiveoftheGridasamulti-agentsystem.witheachother,sincecheapresourcesmaybeunreliableandreliableresourcesmaybeexpensive.Therefore,ausermustbalancethesecriteriaaccordingtotheirownprefer-ences.Additionally,usersshouldgenerallyaimtouseabroadselectionofresources,toavoidrelianceonanarrowsetofresources.Ifauserinteractsonlywithasmallsetofresourcesthatsubsequentlybecomeunreliable,thatuserwillnothavealterna-tivefamiliarresourcestosubmittasksto,butmustsearchforalternativesandrebuildresourcefamiliarity.

Thefactorsthatauserconsiderswhenselectingaresourcedependbothonitsin-dividualdecisionmakingmechanism,andonthenatureofitsindividualGridcontext.Thecontextisimportantsinceitdetermines,amongotherthings,thesignificanceoffailureintermsofcost.Inthispaper,weassumethatallofauserstasksmustbecom-pletedandfailurehasanassociatedcostpenalty.Thus,ifaresourcefailstocompleteatasktheuserincursacostpenalty(i.e.afine)andmustfindanalternativeresourcetosubmitthetaskto.Theoverallcostofprocessingataskisthereforerelatedtotheriskoffailure,sinceinadditiontothefundamentalexecutioncosttheremaybepenaltiesforsubmittingtaskstounreliableresources.

TheGridenvironmentisillustratedinFigure1,whereresources(whichcompriseasetofmachinesthatinturncompriseasetofprocessingelements)areshownasresourceagentsandhumanusersarerepresentedbyuseragents.Userssubmittaskstoresourcesviatheircorrespondinguseragents.Allofauser’sinteractionswithre-sourcesareperformedviaitsuseragentwhichassistsinmanagingtheseinteractions.Inparticular,theresponsibilityofselectinganappropriateresourceforataskisde-volvedtotheuseragent,whichisconfiguredtoreflecttheuser’spreferences(e.g.inbalancingcostandrisk).Ourfocusinthispaperisprimarilyconcernedwiththeuseoftrustinresourceselectionand,althoughcostisclearlyrelevant,wearenotconcernedwiththedetailsofspecificeconomicmodelsofGridcomputing.Therefore,weadoptasimpleflatcommoditymarketmodelinwhichresourcesspecifytheirservicepriceandchargeusersaccordingtohowmuchresourceisconsumed[3].

3Trust

Thenotionoftrustisrecognisedasameansofassessingthepotentialriskininter-actions[5,7,12].Trustrepresentsanagent’sestimateofhowlikelyanotheragentistofulfilitscooperativecommitments.Whenconsideringuncertaininteractions,anagentcanuseitstrustofpotentialcooperativepartnerstoevaluatetheriskoffailure.Therearetwomaincategoriesoftrust:experience-basedandrecommendation-based.

3

Intheformer,anagent’sassessmentoftrustispurelybasedonitsownexperiences,whileinthelattertrustisbasedoninformationprovidedbyotheragents(possiblysup-plementedbyindividualexperience).Experience-basedtrustfitsnaturallyintheGridcontext.Usersinteractwithresourcesandinfertrustbasedontheirexperiencesand,overtime,improvetheirtrustmodels.Recommendation-basedtrustrequiresuserstoshareinformationabouttheirexperienceswitharesourcewithotherpotentialusersoftheresource.Althoughthisisapotentiallyusefulmechanism,thereareanumberofobstaclestoitsuseforaGriddomain.Inparticular,thereisnointrinsicmotivationforinformationsharing.Indeed,ifausergivespositivefeedbackaboutaresourcethismayjeopardiseanyabilityforitsfutureusesinceothersaremorelikelytousetheresource(reducingitsavailability).Therearealsogeneralissuestoaddressregardingrecommendation-basedtrustconcerningthesubjectivityandcontext-specificnatureoffeedback.Otherresearchersare,however,consideringtheseproblemstoallowutilisa-tionofrecommendation-basedtrustintheGriddomain[9,14].Ourworkisorthogonaltothis,andweenvisageexperience-basedandrecommendation-basedtrustbeingcom-binedinthefuturetoprovideasingletrustmechanism.Forthepurposesofthispaper,however,wearesolelyconcernedwithexperience-basedtrust.

3.1TrustFramework

WebaseourmodeloftrustonGambetta’stheoreticalwork[7],Marsh’sformalism[12],andtheworkofGriffiths[6,8],anddefinethetrustTinanagentα,tobearealnumberintheintervalbetween0and1:Tα∈[0,1].Thenumbersmerelyrepresentcompara-tivevalues,andhavenostrongsemanticmeaninginthemselves.Valuesapproaching0representcompletedistrust,andthoseapproaching1representcompleteblindtrust.Thereisaninverserelationshipbetweentrustandtheperceivedriskofaninteraction:cooperatingwithatrustedagenthasalowperceivedriskoffailure,whilethereisahighriskassociatedwithdistrustedagents.Trustvaluesrepresenttheviewofanin-dividualagent,subjectivelybasedonitsexperience,andarenotdirectlycomparableacrossagents.

Trustvaluesareassociatedwithameasureofconfidence,andasanagentgainsexperienceitsconfidenceincreases.Withnopriorexperience,trusttakesaninitialvalueaccordingtoanagent’sdisposition:optimisticorpessimistic.Optimisticagentsascribeahighinitialtrustvaluetoothers(implyingalowperceivedrisk),andpes-simistsascribelowvalues.Thisdispositionalsodetermineshowtrustisupdatedafterinteractions[13].Aftersuccessfulinteractions,optimistsincreasetheirtrustmorethanpessimistsand,conversely,afterunsuccessfulinteractionspessimistsdecreasetheirtrustmorethanoptimists.Anagent’sdispositioncomprises:theinitialtrust,Tinitial,ascribedpriortointeractingandfunctionsforupdatingtrustaftersuccessfulandun-successfulinteractions,updatesuccess,andupdatefailrespectively.Thesefunctionsforupdatingtrustaresimpleheuristics,andthereisnostandarddefinitionforthem.In-stead,itistheresponsibilityofthesystemdesignertochooseanappropriateheuristic.Inthispaperweusethefollowingdefinitionsfortheupdatefunctions:

updatesuccess(T)=T+((1−T)×(ds×T))updatefail(T)=T−((1−T)×(df×T))

4

wheredsanddfareweightingfactorsdefinedbythedisposition2.

Overtimetrustvaluesmaybecomeinaccurateandoutdatediftheexperiencesthatgaverisetothemarenolongerrelevant.Theenvironmentmaychange,andaresourcethatwasreliablepreviouslymaynolongerbeso.Toaddressthisproblem,weapplyadecayfunctiontoconvergeeachtrustvaluetoTinitialinthelackofanysubsequentexperience.Thus,unlessreinforcedbyrecentcooperativeactivity,thepositiveeffectofsuccessfulinteractionsreducesovertime,asdoesthenegativeeffectoffailedinter-actions.Thedecayfunctionisdefinedas:

decay(T)=T−((T−Tinitial)/dd)

whereddadecayratedefinedbytheagent’sdisposition.

Toimproveitstrustmodelsanagentmayalsoexplorealternativeresourcesforlowprioritytasks.Agentstypicallyonlyinteractwithothersthatareconsideredtrustwor-thy.Thus,theretendstobeasubsetofresourcesthatareinteractedwith,anditisthissubsetforwhomtheagentwillbeconfidentaboutitstrustvalues.Toreducetheriskofareliableagentbeingoutsidethissubset,agentscanperiodicallyselectresourcesfromoutsidethesettoverifyitsjudgementiscorrectandattempttodiscoveradditionaltrustedresources3.

4Numerical,StratifiedandWindowedTrust

Inourapproachtrustismodelledasanumericalvalue,howeversomeresearchersnotethatusingcontinuousnumericalvaluescanintroduceambiguitysincethesemanticsarehardtorepresent[1,12].Thealternativeapproachistodividethetrustcontinuumintoasetoflabelledstrata.Abdul-RahmanandHailes,forexample,takethisapproach,providingfourdistincttruststrata(“verytrustworthy”,“trustworthy”,“untrustworthy”,and“veryuntrustworthy”)thattheyargueprovidesaclearsemanticsfordifferenttrustvalues[1].Theadvantageofthisapproachisthat“trustworthy”foroneagentshouldcorrespondto“trustworthy”foranother,avoidingtheproblemofdefiningthemean-ingofanumericalvalue.However,thesesemanticsarestillsubjective,anddifferentagentsmayascribethesameexperiencestodifferentstrata;experiencesthatrateashighlytrustworthyforoneagentmayonlyrateastrustworthyforanother.Afurtherproblemwithstratifyingtrustisalossofsensitivityandaccuracy,sincecomparisonsbecomecoarsegrainedwithnowaytodistinguishbetweenagentswithinastratum.ForthisreasonMarshrejectstheuseofstratainfavourofnumericalvalues[12].Inourapproach,toavoidlossofsensitivityandaccuracy,wealsorepresenttrustbynu-mericalvalues.Furthermore,updatingtrustafterinteractionsissimplefornumericvalues,whilstthosemodelsthatusestratificationglossoverhowagentsdetermineatruststratafromtheirexperiences[1,2].

Theadvantageoftruststrataisthatselectionbetweenresourcesissimplified.Inourmodel,supposethatausermustselectbetweentworesourceswithtrustvalues0.5

and0.50001.Theusermusteitherconcludethatthisdifferenceisinsignificantandtheresourcesareequallytrusted,orthatthereisarealdifferenceintrustandthelatterresourceismoretrustworthy.Theuseofstrataavoidsthisproblem,sincetherearenonumericalvaluesforconsideration.Ideally,atrustmodelwouldhavethesensitivityandaccuracyofanumericalapproach,combinedwiththeeaseofcomparisonfromastratifiedapproach.Tothisend,weproposetwosimplemodificationstoourtrustmodelatthetimeoftrustcomparisons:variablystratifiedandwindowedtrust.

Intheformer,trustvaluesaretranslatedintostrataimmediatelybeforecomparison.Thenumberofstrataisvariable,withfewerstrataprovidingthesimplestbutleastprecisecomparison,whilemorestratareducesthecomparisonadvantagebutretainsprecision.Forexample,Abdul-RahmanandHailes’stratacanbemodelledbydividingthetrustintervalintothefollowingequalparts,

verytrustworthy:0.75<=trust<=1trustworthy:0.5<=trust<0.75untrustworthy:0.25<=trust<0.5veryuntrustworthy:0<=trust<0.25.Thedisadvantageofstratifyingtrustisthatanequaldifferenceinvaluesisnotsignificantwithinastratum,butiswhenitliesacrossstrata.Forexample,usingtheabovestrataadifferenceof0.1isnotsignificantforagentswithtrustvalues0.6and0.7(i.e.bothare“trustworthy”),butitisforagentswithvaluesof0.7and0.8(i.e.theformeris“trustworthy”andthelatter“verytrustworthy”).

Oursecondmodificationistouseavariablesizewindowwhenconsideringtrustvalues,suchthatvalueswithinthewindowareconsideredequal.Thisisasimilartostratifiedtrust,butavoidstheproblemsacrossstrataboundaries.Windowedtrustcanbethoughtofasstratifiedtrustwithmovableboundaries.Forexample,ifweuseawindowsize,ortrustdistance,of0.1,thenagentswithtrustvalues0.6and0.7areconsideredequal,asareagentswithtrustvaluesof0.7and0.8.However,theagentwillstilldistinguishbetweentrustvaluesof0.6and0.8.Thetrustdistanceisvariable,andsimilarlytostratifiedtrust,alargerdistanceprovidesthesimplestbutleastprecisecomparison,whilesmallervaluesreducethecomparisonadvantagesbutretainprecision.

5ResourceSelection

Whenselectingaresourceausermustfirstconsiderwhethertheresourcehasthere-quiredcapabilities(e.g.processorarchitecture,networkbandwidthetc.),andsecondwhetheritislikelytocompletethetasksuccessfully.Thefirstoftheseconsiderationsissimple—eitheraresourcehastherequiredcapabilitiesoritdoesnot.Thosethatdonotcanberejected,otherwisefactorssuchascostandreliabilitymustbeconsidered.Thesefactorsaremorecomplex,sincetheyhavevaryingdegreesandmaybebasedonuncertaininformation.Trustenablesanagenttoconsiderthesefactors.Auserislikelytopreferaresourcethatgenerallycompletestasksontimeandrarelyfails,toonethatfrequentlyfails.Thisisembodiedbythetrustascribedtoaresource.Toselectaresourceanagentshouldbalancetrustworthinessagainstcost.Selectingaresource

6

inthismannerisaheuristicdecisionandthereareseveralpossibleapproaches.Thispaperproposessixfundamentaloptions,asintroducedbelow.

5.1Cost

Thesimplestapproachtominimisingexecutioncostistoselecttheresourcethathasthelowestexpectedcost,basedonitspublishedcost-per-second.However,thiswillonlybesuccessfulifresourcesarehonestandreliable.Ifaresourcetakeslongerthanexpectedtoprocessthetask,orfailstoexecuteit,thenthisapproachwillnotresultinthelowestoverallcost.Ifexecutiontakeslongerthanexpectedthentheuserwillbechargedfortheadditionalprocessingtime.Shouldtaskexecutionfailthenanal-ternativeresourcemustbefound,andtheuserwillbechargedapenaltyforfailure.Theproblemisthattheriskofresourcefailureandunreliabilityisnotconsideredwhenselectingaresource.

5.2StrictTrust

Tominimisetheriskoffailure,anagentcanselectthemosttrustedcapableresource(providedtheagentisconfidentofitsmodels4).Ifseveralresourcesareequallyhighlytrusted,thenoneisselectedarbitrarily.Forlowprioritytaskstheagentperiodicallyse-lectsaresourcethatisnottrusted,bywayofexplorationasdescribedinSection3.Thisapproachensuresthattheresourcethatisperceivedtobethelowestriskisselected.However,theuserisforcedtodistinguishbetweenresourceswherethereisonlyasmallnumericaldifferenceintrust.Sincetrustissolelybasedonexperience,smalldifferencesinthenumericalvaluemaynotbesufficienttomakemeaningfuljudge-ments.Althoughsmalldifferencesmayarisefromgenuinedifferencesinreliability,theymayalsoarisefromslightdifferencesintheextentorrecencyofpriorexperience.Thus,thereisariskofoverfittingbydrawingconclusionsfromtrustvalueswheredifferencesarisefromirrelevantartifactsofthedata.

Afurtherdisadvantagetousingstricttrustisthatittendstoleadtoaverynarrowsetofresourcesbeingused.Sinceusersmayselectresourcesbasedonsmallnumericaldifferences,thesesmalldifferencesarereinforcedbytheresultinginteractions.Overtime,aninsignificantdifferenceintrustcanbemagnifiedsignificantly.Forexample,ifresourceR1istrustedonlyslightlymorethanR2thenafteraperiodofsuccessfulinteractionsthetrustofR1maybesignificantlymorethanR2.Thus,infutureinterac-tionsR1islikelytoremainmoretrustedthatR2evenifinrealitythereisnosignificantdifference.Thisisproblematicsince,asdescribedinSection2,abroadselectionofresourceshouldbeusedtoensureresilience.

5.3StratifiedTrust

Toavoidthenarrowresourceusagethatresultsfromstricttrustwecanusestratifiedtrustatthecomparisonstage.Theresourcethatismosttrustedaccordingtothetrust

stratumthatthenumericalvalueliesinisselected.Whereseveralresourcesareequallymosttrusted,oneisselectedarbitrarily.Again,wherethetaskisoflowprioritytheagentperiodicallyselectsaresourcethatisnottrustedbywayofexploration.Thisapproachavoidstheproblemofoverfittingsmallnumericaldifferences,butatthecostofalossofprecision.Thenumberofstrataisvariable,andtheeffectofstratasizeisdiscussedinSection7.

5.4StratifiedTrustwithCost

Usingstratifiedtrustforresourceselectionminimisestheriskoffailure,andavoidsoverfitting,howevernoconsiderationisgiventothecostoftaskexecution.Therefore,weproposeafourthselectionmethodthatinitiallyusesstratifiedtrustasdescribedabove,butthenselectsthecheapestofthemosttrustedresources,basedontheirad-vertisedcost-per-second.Thus,anagentfirstdeterminesthecapableresources,thenextractsthemosttrustedofthese,andfinallyselectsthecheapest.

Thechoiceofstratasizeiscrucialtotheeffectivenessofthisapproach.Iftoofewstrataareused,anagentisunabletodistinguishbetweenresourcesaccordingtoreli-ability;iftoomanystrataareusedthereislikelytobeasinglemost-trustedresourceleavingnoopportunitytodistinguishbasedoncost.Thenumberofstrataeffectivelydeterminestheemphasisgiventoreliabilityversuscost—morestrataemphasisesre-liabilityandreducestheinfluenceofcost,andvisaversa.Again,theeffectofdifferentstratasizesisdiscussedinSection7.

5.5WindowedTrust

Stratifiedtrustavoidstheoverfittingassociatedwithstricttrust,however,asnotedinSection4,itsuffersfromproblemsatstrataboundaries.Thealternativeistousewindowedtrust,inwhichthemosttrustedresourceisselectedaccordingtothetrustwindowthatthenumericalvalueliesin.Whereseveralresourcesareequallymosttrusted,oneisselectedarbitrarily.Again,agentsperiodicallyselectaresourcethatisnottrustedbywayofexploration.Thisapproachavoidsboththeoverfittingproblemandtheeffectsofstrataboundaries.Similarlytostratifiedtrust,thetrustdistance(i.e.thewindowsize)isvariable,withalargerdistancegivinghigherprecision,butattheriskofoverfitting.Section7discussestheeffectsoftrustdistance.

5.6WindowedTrustwithCost

Ourfinalselectionapproachcombineswindowedtrustwithcost.Similarlytostratifiedtrustwithcost,auserfirstdeterminesthecapableresources,thendeterminesthemosttrustedoftheseaccordingtowindowedtrust,andfinallyselectsthecheapest.Again,thesizeoftrustdistanceisimportant,withsmallerdistancesemphasisingreliabilityandreducingtheinfluenceofcost,andvisaversa.TheeffectsofdifferenttrustdistancesarediscussedinSection7.

8

6ExperimentalScenario

TheresourceselectionmechanismsdescribedabovehavebeenexploredusingtheGridSimsimulationtoolkit[4].Thistoolkitprovidesafeasiblewaytoexperimentwithsuchalgorithmsonareasonablylarge-scaleGridofheterogeneousresources.TheoverheadsandresourcerequirementsofinvestigatingthesealgorithmsinaphysicalGridareprohibitive,sincesignificantaccesstoGridresourceswouldberequired.OurfutureaimistoinstantiatethemosteffectiveofourresourceselectionmechanismsinarealGridenvironmentaftervalidationviasimulation.

IntheGridSimtoolkit,resourcescompriseasetofmachinesthatinturncompriseasetofprocessingelements(PEs).Eachresourcehascertaincapabilities,definedbyitscommunicationbandwidthandtheconfigurationandprocessorarchitectureofitsPEs.Atrun-timeresourceshaveavariableload,duetotasksbeingprocessedonbehalfofusersandduetobackgroundprocessing.Resourceload,atleastinpart,determineshowlongittakestoprocessagiventask.InGridSimeachresourcehasanassociated“calendar”,specifiedwhenconfiguringasimulation,thatdefineshowbackgroundloadvariesaccordingtotimeofday(i.e.peakandoff-peakloads),dayoftheweekandholidaysetc.WehaveextendedtheGridSimtoolkittoallowthesimulationofunreliableresources,andinourGridSimextensionresourceshaveanadditionalcharacteristicdefiningtheirreliabilityintermsofafailurerate.

Totestthevalidityofourapproach,andtheresourceselectionalgorithmsdescribedabove,aseriesofexperimentswereperformed.Arangeofuseragentswithdifferentdispositions,fromoptimistictopessimistic,wereusedinaselectionofGridcontexts,rangingfromthemajorityofresourcesbeingreliable,throughamixedset,tothemajor-ityofresourcesbeingunreliable.Eachoftheresourceselectionproposedalgorithmswasused,withvaryingnumbersoftruststrata(from1to5000)andtrustdistances(from0.0001to1).Forcontrolpurposesarandomselectionalgorithmwasalsoused,whereuseragentssimplysubmittedtaskstorandomresources.Variousnumbersofusersandresourceswereexperimentedwith,howevermostoftheresultspresentedbe-lowarefor30resourcesand10users.Eachusergeneratesarandomsetof500taskstobecompletedwithvaryinglengths,bandwidthrequirements,andpriorities.Foreachconfigurationoftheexperimentaldomainweperformed10runs,andtheresultsshownbelowrepresenttheaveragevaluesacrossthoseruns.

7ResultsandEvaluation

Inthissectionwepresentresultsobtainedfromusingtheresourceselectionalgorithmsdescribedabove.Weareprimarilyconcernedwiththreefactors:failurerate,exe-cutioncost,andtotalcost(i.e.executioncostplusanyfailurepenalties).Webeginbyfirstcomparingthestratifiedtrustmethodswithothersandsecondconsideringthewindowedtrustmethods,inbothcasesinvestigatingtheimpactofstratasizeandtrustdistance.Finally,weconsidertheeffectsoftheGridcontextintermsoftheproportionsofreliableandunreliableresources,andattempttoidentifythebestresourceselectionalgorithms.

9

400

failure vs. trust strata size

trust stratifiedtrust stratified with costtrust (strict comparison)

random

350

300

250

200

150

100

50

0

0 5 10 15 20 25 30

Figure2:Failurerateforthestratifiedtrustandstratifiedtrustwithcostresourceselec-tionmethods.

7.1ComparingtheStratifiedTrustApproach

Figure2showsthefailurerateforthestratifiedtrustandstratifiedtrustwithcostre-sourceselectionmethodsforavaryingnumberofstrata.Theseresultsrepresenttheaverageof10runsina“mixed”Gridresourceenvironment,i.e.thereisamixofreli-ableandunreliableresources5.Figure2alsoshowsthefailurerateforthestricttrustandrandomselectionmethods.Thefailurerateforthecostbasedselectionmethodisnotshown,sinceitistoohigh(anaverageof987)toappearonthegraph.Itcanbeseenimmediatelythatthelowestfailurerateisachievedforthestricttrustmethodand,withtheexceptionofverylownumbersofstrata,therandomselectionmethodgivesthehighestfailurerate.Itcanalsobeseenthatprovidedatleast3truststrataareusedthenbothstrata-basedmethodsperformbetterthanarandomselection(andsignificantlybetterthanacost-basedapproach).Inbothstrata-basedapproacheslowerfailureratesareachievedasmorestrataareused.Thesimplestrata-basedapproachtendstoperformaswellasthestricttrustapproachfor10ormorestrata,whilethestrata-basedwithcostapproachisconsistentlyonlyaround10-15%worsethanstrict-trustfor20ormorestrata(thetraceforbothmethodscontinuestobeflatfor30-5000strata,butforclarityisomittedfromthegraph).

RecallfromSection5thatonesignificantdisadvantageofusingstricttrustforresourceselectionisthatanarrowsetofresourcestendstobeused.IntheexperimentsillustratedinFigure2,thestricttrustapproachledtoausergenerallyinteractingwithasingletrustedresource.Thestrata-basedapproachesledtoawiderrangeofresourcesbeingused,wherefewerstratagaveawidersetofresources(asinglestrataleadstoallresourcesbeingusedequally).Atthepointwherethefailurerateforthestrata-basedapproacheslevelsoff(around10stratawithoutcostand20withcost)then,asforstrict

25000

execution cost vs. trust strata size

trust stratifiedtrust stratified with costtrust (strict comparison)

costrandom

20000

15000

10000

5000

0

0 50 100 150 200 250 300 350 400 450 500

Figure3:Executioncostforthestratifiedtrustandstratifiedtrustwithcostresourceselectionmethods.

trust,thereisasingletrustedresourcebeingused.However,beforethispointthereisawidersetofusedresources,andsoahigherresiliencetochangeandareducedlikelihoodofnegligibledifferencesbeinginterpretedassignificant.

TheexecutioncostforthestratifiedtrustmethodsisshowninFigure3,alongwiththeexecutioncostforthecost-based,stricttrustandrandomselectionmethods.Itcanbeseenthatastratifiedtrustwithcostapproachgivestheleastcost,followedbyacost-basedapproach,andthentherandom,stricttrust,andstratifiedtrustmethodsrespectively.Thereasonthatstratifiedtrustwithcostgivesalowerexecutioncostthanapurecost-basedapproachisthattheexecutionistheactualexecutioncost,andthereliableresourcesthatarefavouredbythestratifiedtrustwithcostapproacharethosewhoseactualexecutioncostislikelytobeclosertotheadvertisedcost.

ItcanbeseenfromFigs.2and3thatingeneralthestratifiedtrustwithcostap-proachgivesbetterresultsintermsofexecutioncostthanthestricttrust,cost-basedandrandomapproaches.However,thestratifiedtrustapproachgivesalowerfailureratebutonlybyaround10-14%.

7.2ComparingtheWindowedTrustApproach

Figure4showsthefailurerateforthewindowedtrustandwindowedtrustwithcostselectionmethodsforvaryingtrustdistances.Again,resultsareaveragedover10runsin“mixed”resourceenvironment.Itcanbeseenthatthecost-basedapproachproducesthehighestfailureratewhileastricttrustapproachgivestheleast.Foratrustdistanceoflessthan0.35thewindowedtrustwithcostmethodgavealowerfailureratethanarandomapproach,whilewindowedtrustwasalwaysbetter.Thewindowedtrustapproachgavesignificantlyfewerfailuresthanwindowedtrustwithcost,andforbothapproacheslargertrustdistancesincreasedfailures.Withatrustdistanceof1,thewindowedtrustapproachisequivalenttorandomselection,andthewindowedtrust

11

1200

failure vs. trust distance

windowed trustwindowed trust with costtrust (strict comparison)

costrandom

1000

800

600

400

200

0

0 0.2 0.4 0.6 0.8 1

Figure4:Failurerateofthewindowedtrustandwindowedtrustwithcostresourceselectionmethods.

withcostapproachisequivalenttothecost-basedapproach.

Inasimilarmannertothestratifiedapproaches,alargertrustdistanceleadstomoreresourcesbeingused.Foratrustdistanceof1,thewindowedtrustapproachusesallresourcesandthewindowedtrustwithcostusesallcheapest-costresources.Asthetrustdistanceisreduced,soisthesetofusedresources,suchthataverysmalldistance(<0.001)isequivalenttousingstrict-trust.

TheexecutioncostforthewindowedtrustmethodsisshowninFigure5,alongwiththeexecutioncostforthecost-based,stricttrustandrandomselectionmethods.Itcanbeseenthatacost-basedapproachgivestheleastcost,followedbywindowedtrustwithcost,randomandstricttrust.Thewindowedtrustmethodisthehighestcostforatrustdistanceoflessthan0.25,whileforlargerwindowsizesittendstowardthecostoftherandomapproach.

FromFigs.4and5itcanbeseenthatfortrustdistanceoflessthan0.35bothwin-dowedtrustapproachesgivealowerfailureratethanarandomorcost-basedapproach.Thewindowedtrustwithcostmethodgivesalowerexecutioncostthanallalternativesexceptcost-based,whilewindowedtrustgivesalowerfailureratethanallexceptstricttrust.

7.3ResourceSetting

Theaboveresultsillustratethecharacteristicsofeachoftheresourceallocationmeth-ods.However,inordertoselectthemostappropriatemethodforagivensituationwemustconsiderboththenatureofthatsituation(intermsofGridresources)andthelevelofpenaltyimposedforfailure.TothisendweconsiderthreedistinctGriden-vironments,withdifferingresourcereliabilities.Supposethattherearesixlevelsofreliability,definedasfollows.

12

25000

execution cost vs. trust distance

windowed trustwindowed trust with costtrust (strict comparison)

costrandom

20000

15000

10000

5000

0

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8

Figure5:Executioncostofthewindowedtrustandwindowedtrustwithcostresourceselectionmethods.

reliability

highlyreliable(HR)

3%marginalunreliable(MU)

30%highlyunreliable(HU)

90%Usingthesedefinitionswedefinethefollowingthreesetsofresources,accordingtotheproportionsofreliableandunreliableresourcespresent.

reliable

20%

unreliable

10%R20%

20%

20%U4%

10%

15%VHU3%

failure rate for allocation methods (various resource sets)

700

reliable setmixed setunreliable set

600

500

400

300

200

100

0

S_10S_20S_25DC_0.01DC_0.02DC_0.05DC_0.15SC_10SC_20SC_25D_0.1S_5S_7DC_0.1SC_5SC_7D_0.01D_0.02D_0.05D_0.15Figure6:Failureratefordifferentallocationmethodsinvariousresourcesets(reliable,mixed,andunreliable).

Figure7showshowthetotalexecutioncostvariesaccordingtoresourceset6.Again,itcanbeseenthatthetotalcostissmallestwhereresourcesarereliable,risesinamixedsituation,andishighestwhenresourcesareunreliable.Thetotalcostisde-terminedbybothfailurerate(intermsofpenalties)andexecutioncost.Itcanbeseenthatthelowestcostisobtainedbythestratifiedtrustwithcostandwindowedtrustwithcostalgorithms,butonlyforcertainvaluesofnumberofstrataandtrustdistances.Inparticular,thebestresultsareobtainedfor10-20strataortrustdistancesof0.01-0.02.Overall,forthesevaluesofstrataandtrustdistancethereislittletochoosebetweenthetwoapproaches;stratifiedtrustwithcostismarginallybetterinareliableresourcecontextandwindowedtrustwithcostismarginallybetterinanunreliablecontext.

8Conclusions

InaGridenvironmentresourceselectionisfundamentaltominimisingthecostandfailureratethatuserincurs.Wehaveshownhowthenotionoftrustcanbeleveragedtoimplementasuitableresourceselectionmethodthatminimisesbothcostandrisk.Inthispaperwehavepresentedseveralresourceselectionalgorithmsbasedonalter-nativemethodsfortrustcomparisonnamely,strict,stratifiedandwindowedtrust.WehavedemonstratedtheuseofthesealgorithmsinaGridcontext.Ourresultsshowthattheuseoftrustsignificantlyreducesthefailurerateencounteredbyuserswhenutil-isingGridresources.Furthermore,wherecostisfactoredintoresourceselectiontheoverallcostofperformingataskisreduced.Wehaveshownthatthemosteffectiveapproachesarestratifiedtrustwithcostandwindowedtrustwithcostwithmoderate

120000

total cost for allocation methods (various resource sets)

reliable setmixed setunreliable set

110000

100000

90000

80000

70000

60000

50000

S_10S_20S_25DC_0.01DC_0.02DC_0.05DC_0.15SC_10SC_20SC_25D_0.1S_5S_7DC_0.1SC_5SC_7D_0.01D_0.02D_0.05D_0.15Figure7:Totalexecutioncostfordifferentallocationmethodsinvariousresourcesets(reliable,mixed,andunreliable).

stratanumbersandtrustdistances(around10-20and0.01-0.02respectively).Bothoftheseapproachesensurethatusersinteractwithamuchwidersetofresourcesthanwouldoccurwithastricttrustapproach,andsotheyaremoreresilienttoenvironmen-talchangeorincorrectinformation.Ourongoingworkisconcernedwithinvestigatingfurtherapproachestocombiningtrustandcostinformation,inparticularthroughtheuseoffuzzylogic,alongwithexplicitlyincludingthedesiretomaximisethenumberofresourcesused.FutureworkalsoincludestheinstantiationinarealGridenviron-mentofthemosteffectiveofourproposedmechanisms,namelystratifiedtrustwithcostandwindowedtrustwithcost,Finally,wealsointendtoapplythetrustframeworkandresourceselectionalgorithmstoapeer-to-peerscenario.

References

[1]A.Abdul-RahmanandS.Hailes.Supportingtrustinvirtualcommunities.InProceedingsoftheHawaiiInternationalConferenceonSystemSciences33,2000.[2]F.AzzedinandM.Maheswaran.IntegratingtrustintoGridresourcemanagementsystems.InProceedingsoftheInternationalConferenceonParallelProcessing,pages47–54,2002.[3]R.Buyya,D.Abramson,J.Giddy,andH.Stockinger.Economicmodelsforre-sourcemanagementandschedulinginGridcomputing.ConcurrencyandCompu-tation:PracticeandExperience,14:1507–1542,2002.[4]R.BuyyaandM.Murshed.GridSim:AtoolkitforthemodellingandsimulationofdistributedresourcemanagementandschedulingforGridcomputing.JournalofConcurrencyandComputation:PracticeandExperience,14(13–15):1–32,2002.

15

[5]C.CastelfranchiandR.Falcone.PrinciplesoftrustforMAS:Cognitiveanatomy,socialimportance,andquantification.InProceedingsoftheThirdInternationalConferenceonMulti-AgentSystems,pages72–79,Paris,France,1998.[6]J.R.D.Dyson,N.Griffiths,H.N.LimChoiJeung,S.A.Jarvis,andG.R.Nudd.TrustingagentsforGridcomputing.InProceedingsoftheIEEESMC2004Inter-nationalConferenceonSystems,ManandCybernetics,pages3187–3192,2004.[7]D.Gambetta.Canwetrusttrust?InD.Gambetta,editor,Trust:MakingandBreakingCooperativeRelations,pages213–237.BasilBlackwell,1988.[8]N.GriffithsandM.Luck.Coalitionformationthroughmotivationandtrust.InProceedingsoftheSecondInternationalConferenceonAutonomousAgentsandMulti-agentSystems,pages17–24,2003.[9]T.D.Huynh,N.R.Jennings,andS.Shadbolt.Developinganintegratedtrustandreputationmodelforopenmulti-agentsystems.InProceedingsofthe7thInterna-tionalWorkshoponTrustinAgentSocieties,pages65–74,2004.[10]S.HwangandC.Kesselman.AflexibleframeworkforfaulttoleranceintheGrid.JournalofGridComputing,1:251–272,2003.[11]S.Kirkpatrick,C.D.Gelatt,andM.P.Vecchi.Optimizationbysimulatedanneal-ing.Science,220(4598):671–680,1983.[12]S.Marsh.FormalisingTrustasaComputationalConcept.PhDthesis,UniversityofStirling,1994.[13]S.Marsh.Optimismandpessimismintrust.InProceedingsoftheIbero-AmericanConferenceonArtificialIntelligence,1994.[14]S.D.Ramchurn,C.Sierra,L.Godo,andN.R.Jennings.Acomputationaltrustmodelformulti-agentinteractionsbasedonconfidenceandreputation.InPro-ceedingsofthe6thInternationalWorkshopofDeception,FraudandTrustinAgentSocieties,pages69–75,2003.[15]O.F.RanaandL.Moreau.Issuesinbuildingagentbasedcomputationalgrids.InProceedingsofThirdWorkshopoftheUKSpecialInterestGrouponMulti-AgentSystems,2000.[16]K.Subramoniam,M.Maheswaran,andM.Toulouse.Amicro-economicmodelforresourceallocationinGridcomputingsystems.InIEEECanadianConferenceonElectricalandComputerEngineering,pages782–785,2002.

16