VMs26uuu.info

USENIXAssociationProceedingsoftheThirdVirtualMachineResearchandTechnologySymposiumSanJose,CA,USAMay6–7,20042004byTheUSENIXAssociationAllRightsReservedFormoreinformationabouttheUSENIXAssociation:Phone:15105288649FAX:15105485738Email:office@usenix.
orgWWW:http://www.
usenix.
orgRightstoindividualpapersremainwiththeauthorortheauthor'semployer.
Permissionisgrantedfornoncommercialreproductionoftheworkforeducationalorresearchpurposes.
Thiscopyrightnoticemustbeincludedinthereproducedpaper.
USENIXacknowledgesalltrademarksherein.
Java,Peer-to-Peer,andAccountability:BuildingBlocksforDistributedCycleSharingAliRazaButt,XingFang,Y.
CharlieHu,andSamuelMidkiPurdueUniversityWestLafayette,IN47907{butta,xfang,ychu,smidki}@purdue.
eduAbstractTheincreasedpopularityofgridsystemsandcy-clesharingacrossorganizationsleadstotheneedforscalablesystemsthatprovidefacilitiestolo-cateresources,tobefairintheuseofthosere-sources,andtoallowuntrustedapplicationstobesafelyexecutedusingthoseresources.
Thispaperdescribesaprototypeofsuchasystem,whereapeer-to-peer(p2p)networkisusedtolocateandal-locateresources;aJavaVirtualMachineisusedtoallowapplicationstobesafelyhosted,andfortheirprogresstobemonitoredbythesubmitter;andanoveldistributedcreditsystemsupportsaccount-abilityamongprovidersandconsumersofresourcestousethesystemfairly.
Weprovideexperimen-taldatashowingthatcheatersarequicklyidentiedandpurgedfromthesystem,andthattheoverheadofmonitoringjobsiseectivelyzero.
1IntroductionThispaperdescribesaprototypeofacompletesys-temthatallowsthesharingofcyclesacrossnetworkconnectedmachines.
Foranysuchsystemtobesuc-cessful,certaincorefunctionalitymustbeprovidedtobothapplicationsandhosts:(i)theabilityforanapplicationtodiscoveramachine(orclusterofma-chines)capableofhostingit(resourcemanagementanddiscovery);(ii)theabilityforanapplicationtorunonawidevarietyofmachineswithoutchange(portability);(iii)theabilityofahostmachinetoacceptanapplicationfromanuntrustedsource,andexecuteitwithoutbeingdamaged(safety);and(iv)amechanismformaintaininginformationaboutresourcesprovidedandconsumed,andforensur-ingfairnessintheuseofresources(accountability).
Thesefourfunctionsmustbeaccomplishedinadis-tributed,scalablemannertoenablelargenetworksofmachinesandresources.
Resourcesthatareavailablebutthatarenoteas-ilydiscoveredareuseless.
Peer-to-peer(p2p)net-workshaveachievedwidespreaduseasacontentdiscoverymechanism.
Weproposeusingthesesamemechanismsforresourcediscoveryandjobassign-mentforourcyclesharingframework.
Moreover,becausep2pnetworksareself-organizing,itiseasyfornodestojoin,andleave,withoutthenecessityofacentraladministrativeorganizationandhumanintervention.
TheuseofJavaisextremelyconvenient,ifnotes-sential,forthesecondandthirdofthesefunctions(portabilityandsafety)anditmakestheaccount-ingsignicantlyeasier.
Becauseoverspecifyingahostmachine'scharacteristicsreducesthenumberofviableexecutiontargetsforanapplication,theportabilityacrossexecutionenvironmentsprovidedbyJavaisessential.
Moreover,Java'sbuilt-insand-boxingtechnology,andrichsecurityinfrastructure,allowapplicationsofvaryingdegreesoftrusttobehostedwithouteachhostprovidingadditionalse-curitymechanisms.
Bothoftheseattributessignif-icantlylowerthecostandriskforproducersandconsumersofcyclestojoinanetworkofsharedre-sources.
Andresearch[25,26]showsthattherearenoinherentreasonsfornotusingJavaforhighper-formancecomputing.
Finally,acommunityofpooledresourceswillsur-viveonlyaslongasmembersaretreatedwithahigh(butnotnecessarilyperfect)degreeoffairness.
Inthephysicalworld,moneyisusedasaconveyorofinformationaboutone'scontributiontotheecon-omy.
Creditreportsallowprovidersofservicestojudgethelikelihoodthattheywillbepaidforthoseservicesandtoholdconsumersaccountablefortheirdebts.
Incrementalpaymentschemesareusedinmanylargeactivitiestoboundtheamountofriskforbothprovidersandconsumersofresourcestothesizeoftheincrementalpayment.
Inthispaperweoutlinealow-overheadJavabasedmechanismtoallowuserstomonitortheprogressoftheirappli-cations,andtodetermineiftheyarecomfortablemakingpartialpaymentsfortheprogressofajob.
Ourcreditmechanismprovidesadistributed,scal-ablesystemformakingandacceptingthese(possi-blypartialandincremental)payments(credits,inthelanguageofthispaper.
)Moreover,oursystemsupportstwootherimportantfunctions:weallowbothusersandresourceproviderstodetermine,us-ingtheirowncriteria,thecreditworthinessofoth-ers;andweallowcreditsheldbyoneentity(user)tobetradedtoanother,andusedbythatotherentitytoacquireresourcesorreduceitsvolumeofoutstandingcredit.
Justasthelargereconomycanfunctionwellwithacertainamountoffraudandnoiseintransactionsandaccounting,soshouldeconomiesinvolvedinsharingofcomputationalre-sources.
Thusourgoalisnottoproduceperfectlysecuresystem,butinsteadsucientlygoodsystemstoenablewidescalesharingofcomputationalre-sources.
Thispapermakesthefollowingcontributions:AnovelmethodformonitoringtheprogressofaJavaapplicationwithlowoverheadthatlever-agesimportantfeaturesofJavaVirtualMa-chines(JVM);Anovelmethodforissuingcreditsthatisscal-ableandcheckablebyallparticipatingnodesinasystem;Asystemthatallowsthesharingofcomputa-tionalresourcesthatbuildsontheJavaproper-tiesofportabilityandsafety,thecreditsystemdescribedinthispaper,andscalablep2pnet-works;Experimentaldatashowingthepracticalityofthesetechniques.
Therestofpaperisorganizedasfollows.
Section2presentsourproposedschemeforenforcingfairnessinp2pcyclesharingsystems.
Section3discussesthedetailsofourprototypeimplementation,andSec-tion4measurestheoverheadandtheeectivenessofourproposedscheme.
Finally,Section5presentssomerelatedwork,andSection6providesconclud-ingremarks.
p2pNetworkSubmissionnodecreditgeneratorprogressprobesupportJVMwithmodifiedresourceinfo.
annoucementsExecutionnodenodeMatchmakingNeighborsetmaintenancejob/machinematchmakingremotejobprobingInstrumentedcoderesourceinfo.
resourceinfo.
Figure1:Overalldesignoftheproposedscheme.
Eachnodecanbeasubmissionnode,oranexecu-tionnodeforsubmittedjobs.
2SystemDesignThissectionrstgivesanoverviewofthesystemdesign,andthendescribesindetailhoweachofthebuildingblocksimplementsthepropertiesnecessaryforausablecyclesharingsystem.
2.
1OverviewInordertoobtainacyclesharingsystemthatpre-ventsdisproportionateconsumptionofresources,thesystemhastosimultaneouslyprovidethecon-sumerwithassurancesthatjobsaremakingprogressonremotemachines,andtheresourceproviderwithassurancesthatresourceusagewillbecompensated.
Figure1showsthedesignofoursystem.
Itusesap2psubstratefortwopurposes:toorganizealltheparticipatingnodes,andtolocateremotenodeswithavailablecomputecycles.
Inthefollowingweassumearemotenodewithfreecycleshasalreadybeenselectedforremoteexecution.
Everyparticipatingnodecanbearesourcecon-sumer(submissionnode)oraprovider(executionnode).
Anodecanllbothrolessimultaneouslyaswell,e.
g.
,itsjobscanberunningonsomeremotenodeswhilejobsfromotherremotenodesarerun-ningonit.
Asaconsumer,anodeimplementsthefollowingfunctions:(i)itimplementsaprobingsys-temthatallowsittoqueryareportingmodule(ajobthatlistensfor,andaccumulatesinformationsentbythebeaconswhichmonitorstheprogressofanapplication)forprogressreportsonremotejobs;(ii)ithasaccesstoaspecialcompilerthatprocessestheinformationsentbybeaconsandcheckitforvalid-ity.
Inourcurrentimplementationallinformationsentbybeaconsisconsideredvalid,andnoinfor-mationisextracted,butourdesignallowsformoresophisticatedreports(seeSection2.
4.
1fordetails);(iii)itimplementsanaccountingsystemtorecordthefactthatithasconsumedcyclesonothernodes,andtoissuedigitallysignedcreditstothehostingmachinewhennecessary.
Thesereportsarestoredinthep2pnetwork,andcanbeviewedbyallnodesinthenetwork.
Asaresourceprovider,theexecutionnodesupportsatrustedJVMwhosedynamiccompilerinsertsbea-consthatsendinformationabouttheprogressoftheapplicationtothereportingmodule,mentionedabove.
Thereportingmoduleissuesprogressreportsusingthisinformation.
Remotecyclesharingworksasfollows.
First,thesubmissionnodecreatesajobtoberunonremoteresources.
Thep2pnetworkisqueriedforapossi-blehostnode,thecreditinformationforthenodeischecked,andifacceptablethejobissubmittedtothenode.
TheVManditsdynamiccompileronthehostnodeinsertinstrumentationandbeaconsintotheprogram,whichbeginsexecution.
Thesub-mittingnodethenperiodicallyqueriesthereportingmodule(whichcanrunonanynodethatcancom-municatewiththejobonthehostnodeandwiththesubmittingnode).
Ifthesubmittingnodendsthejobtobemakingprogress,itissuesacredittotheexecutionnode.
Creditsarenotissuedifthejobisnotmakingsatisfactoryprogress.
Ifthesubmis-sionnodetriestocheatandnotissueacredittothehostnode,thehostnodecanevictthejob.
There-fore,selfinterestmotivatesthesubmittingnodetoissuecredits,andthehostnodetoruntheprogram.
2.
2Scalableresourcemanagementthroughp2pnetworksToenablefault-tolerant,load-balancedsharingofcomputecyclesamongtheparticipatingnodes,weuseastructuredp2poverlaynetworktoorganizetheparticipatingnodesandlocateavailablecom-putecyclesonremotenodesforremoteexecution.
2.
2.
1DistributedHashTablesWebrieyreviewcurrentp2poverlaynetworkswhichpreviouslyhavebeenusedforsupportingdata-centricapplications.
Structuredp2poverlaynetworkssuchasCAN[30],Chord[35],Pastry[32],andTapestry[40]eectivelyimplementscalableandfault-tolerantdistributedhashtables(DHTs).
EachnodeinthenetworkhasauniquenodeIdandeachdataitemstoredinthenetworkhasauniquekey.
ThenodeIdsandkeysliveinthesamenamespace,andeachkeyismappedtoauniquenodeinthenet-work.
ThusDHTsallowdatatobeinsertedwith-outknowingwhereitwillbestoredandrequestsfordatatoberoutedwithoutrequiringanyknowledgeofwherethecorrespondingdataitemsarestored.
Inthefollowing,wegiveabriefdescriptionofonecon-cretestructuredoverlaynetwork,Pastry,onwhichourprototypeisbuilt.
Detailedinformationcanbefoundin[32,7].
Pastryprovidesecientandfault-tolerantcontent-addressableroutinginaself-organizingoverlaynet-work.
EachnodeinthePastrynetworkhasauniquenodeId.
Whenpresentedwithamessagewithakey,PastrynodesecientlyroutethemessagetothenodewhosenodeIdisnumericallyclosesttothekey,amongallcurrentlylivePastrynodes.
BothnodeIdsandkeysarechosenfromalargeIdspacewithran-domuniformprobability.
TheassignmentofnodeIdcanbeapplicationspecic;typicallybyhashinganapplicationspeciedvalueusingSHA-1[14].
Themessagekeysarealsoapplicationspecic.
Forex-ample,wheninsertingthecreditofanodeintotheDHT(Section2.
4)themessagekeycouldbesomeidentierthatuniquelyidentiesthatnode.
ThePastryoverlaynetworkisself-organizing,andeachnodemaintainsonlyasmallroutingtableofO(logN)entries,whereNisthenumberofnodesintheoverlay.
EachentrymapsanodeIdtoanIPaddress.
Specically,aPastrynode'sroutingtableisorganizedintolog2bNrowswith(2b1)entrieseach.
Eachofthe(2b1)entriesatrownoftheroutingtablereferstoanodewhosenodeIdsharestherstndigitswiththepresentnode'snodeId,butwhose(n+1)thdigithasoneofthe(2b1)possiblevaluesotherthanthe(n+1)thdigitinthepresentnode'snodeId.
Eachnodealsomaintainsaleafset,whichkeepstrackofitslimmediateneighborsinthenodeIdspace.
Theleafsetcanbeusedtodealwithnewnodearrivals,nodefailures,andnodere-coveriesasexplainedbelow.
MessagesareroutedbyPastrytothedestinationnodeinO(logN)hopsintheoverlaynetwork.
2.
2.
2DiscoveringfreecyclesWhilep2poverlaynetworkshavebeenmainlyusedfordata-centricapplications,oursystemexploitsp2poverlaysforcomputecyclesharing.
Speci-cally,itorganizesalltheparticipatingnodesintoanoverlaynetwork,andusestheoverlaytodiscoveravailablecomputecyclesonremotenodes.
Todiscovernearbynodesthathavefreecycles,oursystemexploitsthelocality-awarenesspropertyofPastry[7]tomaintainandlocatenearbyavail-ableresourcestodispatchjobsforremoteexecu-tion.
ThispropertymeansthateachentryinaPastrynoden'sroutingtablescontainsthenodencthatisclosetonamongallthenodesinthesystemwhosenodeIdssharetheappropriateprexthatwouldplacetheminthatentryofn.
Periodically,eachnodepropagatesitsresourceavail-abilityandcharacteristicstoitsneighborsintheproximityspace.
Thisisachievedbypropagatingtheresourceinformationtothenodesnineachnoden'sPastryroutingtablerows.
Nodenalsofor-wardstheresourceinformationaccordingtoaTime-to-Live(TTL)valueassociatedwitheverymessage.
TheTTListhemaximumnumberofhopsintheoverlaybetweennandthenodesthatreceiveitsresourceinformation.
Hence,theresourceinforma-tionispropagatedtoneighboringnodeswithinTTLhopsintheoverlay.
SincePastryroutingtablescon-tainonlynearbynodes,this"controlledooding"willcauseresourceinformationtobespreadamongnearbynodesintheproximityspace.
Eachnodethatreceivessuchanannouncementcachesthein-formationintheannouncementforitslocalmatch-makingbetweenjobsandavailableresources.
Tolocatearemotenodeforjobexecution,anodequeriesnearbynodeswithavailableresourcesasac-cumulatedinitslocalknowledge,takingproximityandcredit-worthinessintoaccount.
Theactualre-moteexecutionoftheprogramandsubsequentI/Oactivitiesareperformedwiththeremotenodedi-rectly,anddonotgothroughtheoverlay.
Ourp2p-basedcyclesharingsystemtoleratesnode/networkfailuresasfollows.
Whenthenodeforremoteexecutionfails,thesubmittingnodedis-coversanalternativenodeforre-execution.
Thefaulthandlingcanbeimplementedintheruntimesystemandmadetransparenttotheuserprogram.
Thisisanimportantadvantageoverthetraditionalclient/servermodel,wherefailureofaserverim-pliesexplicitreselectionbytheclient.
Forreasonsoffailureresiliency(ormaliciousnodedetection)viacomparisonofresultsfrommultiplenodes,anodemaycreatemultipleidenticalcomputationsforre-moteexecution.
2.
3SafetyandportabilitythroughJavaVMsOneofthegoalsofthisprojectistoallowcycleshar-ingwithaminimumofhuman-basedadministrativeoverhead.
Thisrequiresthatjobsbeacceptedfromuserswhohavenotbeenvouchedforbysomeac-creditingorganization.
This,inturn,requiresthatsubmittedapplicationsnotbeabletodamagethehostingmachine.
Java'ssandboxingabilitiestinwellwiththismodel.
Ifsubmittershaveundergonesomeadditionalverication(i.
e.
theyareatrusteduser),digitalsignaturebasedsecuritymechanismscanbeusedtoallowpotentiallymoreharmfulcodetobeexecuted,forexamplecodethataccessesthehost'slesystem.
Javaportabilityacrossdierentsoftwareandhard-wareenvironmentssignicantlylowersthebarrierstomachinesjoiningthepoolofusersandresourcesavailableonthenetwork.
Java'sportabilityisinpartbecausebyte-codeiswelldened.
Anotherreasonforitsportabilityisthatmuchofthefunc-tionalitythatisprovidedbysystemlibraries,andisnotpartoflanguageslikeC++andFortran(e.
g.
threadlibrariesandsockets),isprovidedbywellspeciedstandardJavalibraries.
Asaconsequence,inpracticeJava'sinterfacestosystemservices,e.
g.
,sockets,appeartobemoreportablethanwithC++implementations.
Theseattributesallowsubmittingnodestohavealargernumberofpotentialhoststochoosefrom,andincreasestheprobabilitythataprogramwillexecutecorrectlyonaremotehost.
communciationsynchronouscommunciationasynchronousprogramprogressinformationexecutionnodereportingmoduletargetcode(beacons)submissionnodeprobequerystatusrequestreplyqueryprocessinginstrumentedFigure2:Compilerinstrumentationformonitoringjobprogress.
Thecommunicationbetweenthein-strumentedbeaconsandthereportingmoduleisasynchronous,whereasitissynchronousbetweenthequeryingnodeandreportingmodule.
2.
4AccountabilitythroughJava,p2pnetworks,andcredit-worthinessAccountabilityinoursystemisachievedthroughasystemofcredits.
Thestorageandretrievalofthesecreditsisaccomplishedthroughthep2pnet-work,andthemonitoringoflong-runningjobstodetermineifcreditsshouldbeissuedisdoneusingaJVM.
2.
4.
1Compilersupportforprogressmoni-toringThebasicideabehindthecompilerassistedmoni-toringoftheprogramexecutionisthatthecompilerwillinstrumenttheprogramwithbeaconswhichwillperiodicallyemitsomeindicationoftheprogram'sprogress.
BecauseJavaisadynamicallycompiledlanguage,commercialandresearchJVMstypicallymonitorthe"hotness"ofexecutingmethodsbyei-therinsertingsamplingcodethatisperiodicallyex-ecutedorexecutedonmethodentry,orbyobservingcurrentlyactivemethods.
Thesetechniquesdevelopanapproximationofthetimespentinamethod.
Oursystemexploitsthisinformationtomonitortheprogressoftheprogramandsendsthisinformationasynchronouslytoaseparateprogramcalledthere-portingmodule.
Thereportingmodulethenbuersthisinformationsothatitcanreplytoqueriesfromtheprogramowner.
Whenaprogramownerqueriesthereportingmod-ule,thereportingmodulecreatesaprogressreportfromthedataithassofarcollected,andrepliestotheprogramownerimmediately.
Theownercanthenprocessthisreportanddeterminewhetheritsprogramismakingprogress.
Figure2showsthissetup.
Theadvantageofhavingthereportingmod-uleistwo-fold:(i)theapplicationprogramdoesnothavetosuspenditselfwhilewaitingtobeprobedbythejobowner,insteadthedataisbueredinthere-portingmodule,and(ii)thedesignofthebeaconsisdecoupledfromthedesignofthequeries.
More-over,thereportingmodulecanrunontheexecu-tionnode,thesubmissionnode,oranyothernodethatcancommunicatewithboththeexecutionandthesubmissionnode.
Forthisreason,thereportingmoduleisimplementedasaseparateprocess.
Onatrulymalicious,asopposedtooverloadedorotherwisedefectivesystem,thissimplebeaconcanbespoofedbythemalicioussystemreplayingoldbeacons.
Intheworstcase,determiningthatapro-gramonaremotesystemhasruntocompletionandwithouttamperingisashardasactuallyrunningtheprogram.
Itisourassumptioninthisprojectthatwearenotexecutingontrulymaliciousma-chines,ratherwearerunningonmachinesthatmaybeovercommitted,orthatmaybe"fraudulently"sellingcyclesthatdon'texistinordertogaincreditstopurchaserealcycles.
Ourgoalistouncoverfraudandovercommittednodesbeforethesystemisex-ploited"tooheavily"byfraudulentorover-extendedmachines,nottopreventallfraud.
Thusoursystemdoesnotneedtodetectallfraudulentorovercom-mittedsystems,butrathermustallowfraudulentandovercommittedsystemstobedetected"soonenough".
Thisisanalogoustothegoalofcreditratingservicesin"realworld"commerce,whichisnottopreventanyextensionofcredittounworthyrecipients,butrathertoboundtheextenttowhichtheycanreceivecredittoanamountthatcanbeabsorbedbythesystem.
Westressthatsystemisgeneralenoughtosupporteitherdecentralizedorcentralizedcreditreportingmechanisms,dependingonanylegalrequirementsorrequirementsofthemembernodes.
Wearedevelopingauditmethodsforbetter,albeitstillnotperfect,creditreporting.
Figure3(a)showagraphicalrepresentationofaprogram–itcanbeeitheracontrolowgraphoracallinggraph.
Thisgraphcanbetreatedasatransducer1,orasanitestateautomata(FSA)thatacceptsthelan-guagedenedbythestringsemittedbythetrans-ducer.
Inthismodel,theexecutionofthepro-gramcorrespondstothetransducer,withthere-portingmoduleimplementingtherecognizingFSA.
Thecompilerwillinsertbeaconstoimplementthe1Atransducerisanitestateautomatathatemitsinfor-mationonstatetransitions.
DABCEΤ(β)Τ(χ)Τ(φ)Τ(γ)Τ(δ)Τ(α)χ,λDABCEγ,λφ,λα,λβ,λδ,λ(a)Aoworcallinggraphasatransducer(b)TheFSAcorrespondingtothistransducerFigure3:Aowgraphasatransducerandrecog-nizingFiniteStateMachine.
transducerwithintheexecutingapplicationandwillalsocreatetheassociatedFSA.
Outputemittedbythetransducercanbesimple,suchasmethodnames,ormorecomplicated,suchasmethodnames,rangesofinductionvariablesandthevaluesoftheinductionvariablesthemselves.
However,thissystemmaystillnotbesecuresinceeitheranotherprogramunderstandingtoolorahu-mancouldreverse-engineerthetransducerintheap-plicationprogramandusethatinformationtospoofthereportingmodule.
2.
4.
2Issuingcreditsandassessingcredit-worthinessToensurethecompensationofconsumedcyclesonnodeBbynodeA,weproposeadistributedcredit-basedmechanism.
Therearetwobuildingblocksofourapproach:(i)credit-reportswhichareenti-tiesthatcanbe"traded"inexchangeforresources,and(ii)adistributedfeedbacksystemwhichpro-videstheresourcecontributorswiththecapabilitytocheckthecredithistoryofanode,aswellastosubmitfeedbackaboutthebehaviorofanode.
Forsimplicity,weassumethatalljobsareequivalentintermsoftheamountofresourcestheyconsume.
ThedistributedfeedbackdatabaseisbuiltontopoftheDistributedHashTable(DHT)supportedbytheunderlyingstructuredp2poverlay.
Itmaintainsthefeedbackforeachnoderegardingitsbehaviortowardshonoringcredits.
Anynodeinthesystemcanaccessthisinformationanddecidewhethertoallowanexchangewitharequestingnode,orcon-NodeANodeBjobcreditNodeCNodeZDHT12345678Figure4:Variousstepstoensurepropercompensa-tionofacontributedresource.
sideritaroguenodeandavoidanydealingswithit.
Inthisway,anodecanindividuallydecidetopunishanodewhoseconsumptionofsharedresourceshasexceededitscontributiontoothernodesbysomethresholddeterminedbythedecidingnode.
Figure4showsthevariousstepsinvolvedinensur-ingthatBisadequatelycompensatedforitscon-tribution.
WhenArunsajobonB(1inFigure4),Awillissuea(digitallysigned)credittoB(2intheFigure)(ThiscreditissimilartotheclaiminSamsara[8];itcanbe"traded"withothernodesforexchangeofequivalentresources).
Awillgivethecreditauniquesequencenumber–uniqueinthatAwillissuenoothercreditswiththatnum-ber.
Bwilldigitallysignthecreditandhashitintoarepositoryinthep2pnetwork(3intheFigure).
ThecredithashisgeneratedbyhashingafunctionofAandthesequencenumber.
IfBgivesthecredittoC(4intheFigure),BwilldigitallysignthecreditbeforegivingittoC.
Cwilldigitallysignit,computethehashbasedon(A,uniquenumber)andstoreit(5intheFigure).
Thestoringnodewillreplacetheexistingcopyofthecreditwiththenewcopy.
Itknowsitcandothissincetheendofthesigningsequenceis"B,B,C",i.
e.
thelast-1andlast-2signaturesmatch,showingthatthelast-1signeristhepreviousownerandisallowedtotransferthecerticate.
IfthecerticategoestoZ(6and7intheFigure)andreturnstoA(8intheFigure),Adestroysit.
Sincetheendofthesigningsequenceis"Z,Z,A",thesystemknowsthatthetransfertoAisvalidandAistheowner,andthereforeAcanchoosetohavethecreditdestroyed.
Notethatthisalsoal-lowscreditstobedestroyedbyanyowner(i.
e.
Cabovecouldhaveaskedthatthecreditbedestroyed,notsaved)perhapsbecauseofmonetarypayments,lawsuits,bankruptcyoftherootsigner,etc.
Becauseacredithashestoaxedlocation,attemptstoforgecredits(forexampleinareplayattack)willleavemultiplecopiesofthecredit(identiedbyitsuniquesequencenumber)inthesameDHTloca-tion,andthesecondforgedcreditwillnotbesaved.
ThusifBtriestogivethesamecreditdtobothCandZ,onewouldberejected(sayZ's)andZcouldthenrefusetorunB'sjob.
Shouldamaliciousnodesavebothcredits,anodecheckingonthecreditwor-thinessoftheissuingnodecandeterminethattherearetwocreditswiththesamenumber,andeitherignoreorfactorthisintoitsevaluationofboththeissuingnodeandnodeB.
Thefeedbackinformationisusedtoenforcecontri-butionfromselshnodesasfollows.
InFigure4,beforenodeBexecutesajobonbehalfofnodeA,itretrievesallthefeedbackforAfromtheDHT,veri-esthesignaturestoensurevalidity,andcandecidetopunishAbyrefusingitsjobifA'snumberoffail-urestohonorcreditshasexceededsomethresholddeterminedbyB.
Wenotethatthissystemallowsindependentcreditratingservicestobedevelopedthatasubmittingnodecanrelyonforevaluatingthecredit-worthinessofahost.
2.
4.
3PotentialthreatsandvulnerabilitiesItisourassumptioninthisprojectthatwearenotexecutingontrulymaliciousmachines,ratherwearerunningonmachinesthatmaybeovercommitted,orthatmaybe"fraudulently"sellingcyclesthatdon'texistinordertogaincreditstopurchaserealcycles.
Thuswelimitoutdiscussionofpotentialthreatstobefromsuchmisbehavingnodesinthefollowing.
Therstscenariodealswiththetimingbetweentheissuingofcreditsandtherunningofsubmittedjobs.
Inparticular,arunningnodemayrefusetospendfurthercyclesuponreceivingcreditsfromjobsub-mittingnodes,andconversely,thesubmittingnodemayrefusetoissuecreditsuponhearingthecom-pletionofitsremotejobexecution.
Toprovidemu-tualassurance,weproposetheuseofincrementalcreditissuing.
ConsiderthecasewhenAissub-mittingajobtorunonB.
Undertheincrementalcreditissuingscheme,AgivesincrementalcreditswhenitseesprogressofitsjobonB.
Amightalsochoosetocheckpointitsjobwhenissuinganincre-mentalcredittoeliminatethechanceoflosingworkthathasbeenpaidfor.
Secondly,AcanalsoissueanegativefeedbackforBifitmisbehaves.
Thisisdoneasfollows.
AmonitorsitsjobonBatprede-nedintervals.
OneachintervalthatAndsitsjobstalled,itcalculatesaprobabilityq,whichincreasesexponentiallywithincreasingnumberofconsecutivefailuresofBtoallowthejobtoprogress.
AthenissuesanegativefeedbackforBwiththeprobabilityq.
ThisschemeallowsBtohavetransientfailures,butpunishesitforchronicallycheating.
Conversely,thecasewhereArefusestohonoritsissuedcreditisalreadyaddressedbythedistributedfeedbackmech-anism.
ThenextscenarioresultsfromthefactthatifeachfeedbackisinsertedintheDHTonlyonce,eventhoughDHTreplicatesthecreditamongnodesnearbyinthenodeIdspace,ifthenodestoringthemainreplicaactsmaliciously,thecreditinforma-tionmaynotberetrievedcorrectly.
Toovercomethis,wepurposeinsertingeachcreditintotheDHTmultipletimesbymakinguseofapredeterminedsequenceofsaltsknowntoalltheparticipants.
Foreachknownsalt,acredithashisgeneratedbyhash-ingtheconcatenatedfunctionoftheissuer'snodeId,thesequencenumber,andthesalt.
ThesignedcreditistheninsertedintotheDHT.
Inthisway,eachcreditwillbeavailableatmultiplemutually-unawarenodes.
Whenaparticipantintendstover-ifytheintegrityofanotherparticipant,itcanchoosetoretrievemultiplecopiesofthecreditinsteadofone.
Thenumberitattemptstoretrievecanvarybetweenoneandthemaximumcopiesthatareal-lowedtobeinsertedintothesystem.
Oncethesecopiesareretrieved,thenodecancomparethemfortrustworthiness.
Incaseofmismatch,ama-jorityvotecanbeadoptedandtheversionofthecreditthathasthehighestnumberofoccurrenceisassumedtobethetrustedone.
ThispotentiallyincreasestheamountofdatathatisinsertedandretrievedfromtheDHT.
However,thesizeofcreditisusuallysmall,andtheadditionalbenetsofhav-ingmultipleinsertionsoutweightheincreaseinthemessageoverhead.
Anotherproblemmayarisewherethecreditsarenever"traded"backtotheissuingnode.
Thisdoesnotindicatemisbehavior,butcanresultinalargenumberofun-utilizedcreditsaccumulatedinthesystem.
Therefore,wherepossible,anodetriesto"trade"aremotecredititholds,ratherthanissueitsowncredit.
Moreover,eachcredit-reporthasatimestamp,andnodescandeterminehowoldaModulenameFunctionalityannounceCCreatesresourceinformationannouncementsandsendsthemtotheneighboringnodes.
dbaseCManagesthelocalknowledgebaseonanode.
matchmakerCFindssuitablenodesforre-questedjobrunsfromavail-ableremotenodes.
execCSetsuptheexecutionen-vironmentforajobonamatchednodeandinitiatestheexecution.
Table1:Modulesintheprototypeimplementationandtheirfunctions.
creditis.
Incasetheageofacredit-reportorig-inatedfromAincreasesmorethanasystem-widethreshold,thecreditholdingnodewilltrytoex-changeitwithArst,beforetryingtolocatesomeotherresourcesinthenetwork.
Thiswillhelpinreducingthenumberofcredit-reportsinthesys-tem.
Intra-organizationalnetworkscanclearthesystemperiodicallyusinginternalbudgetingproce-dures.
WenotethattheloadimposedonthesystembylargeamountsofcirculatingcreditismuchlessthaninsystemslikeSamsara,wherecredittakestheformofphysicaldiskspaceheldhostage,andcon-sequentlyreducestheamountofsystemresourcesavailableforotherpurposes.
3ImplementationWehavebuiltaprototypeofourproposedschemeforp2pbasedresourcediscoveryandaccountabil-ityusingJava1.
4.
2APIspecication.
Weuti-lizethePastry[32]APIforp2pfunctionality,andPAST[31]forstoringthedistributedfeedbackinafault-tolerantanddistributedmanner.
Theim-plementationisdoneonnodeswithPentiumIV2GHzprocessors,512MBRAM,runningLinuxker-nel2.
4.
18,connectedvia100Mb/sEthernet.
Theprototypecanbedividedintovarioussoftwaremod-ulesaslistedinTable1.
Aninterestingobservationintheimplementationprocesswastheduplicatedreceptionofthesamenode'sresourceannouncementsatanodebecauseanodemaybeontheroutingtablesofmultiplere-motenodes.
Topreventduplicatemessagesfromoodingthesystem,eachnodeassignsa32-bitse-quencenumbertoitsannouncements.
Thenumberischosenatrandomatthestartofanode,andin-creasesmonotonicallyforthelifeofthenode.
Whenanannouncementisreceived,itssequenceisrstcomparedwiththesequencenumberofthelastmes-sagereceivedfromtheoriginator.
Asequencenum-berwithavalueequaltoorlessthanthelastseenmessageimpliesthatthemessageisaduplicateandcanbediscarded.
OurexecutionnodeusesanaugmentedversionoftheJikesRVM[1],runningonadaptivecongura-tion.
Intheadaptivesystem,thereexistsaninstru-mentationframeworkthatincrementsmethodinvo-cationcountersastheapplicationproceeds.
Thecountersarethenstoredinadatabasewhosecon-tentsareexaminedbythecontrollerthreadtohelpmakerecompilationdecisions.
Sincetheapplica-tionprogressreportsthatwerequirecanbeinferredfromthisdatabase,wedonothavetoaddinlinecodeintotheapplicationtodetermineit.
Instead,weaugmentthesystemwithaprogressmonitor-ingthread.
Inotherwords,thebeaconisimple-mentedasathreadthatperiodicallylooksintothedatabaseandsendsthemethodinvocationcountervaluestothereportingmodule,togetherwiththetimestamp.
Thisinformationservesasanindicatorforjobprogress.
Theintervalbetweensuccessivere-portsisaparameterthatisspeciedwhenremotejobsaresubmitted.
Wewillexaminetheeectofthisintervalontheexecutionoverheadinourex-perimentation.
Inourimplementationthereportingmoduleislo-catedonthesamehostastheexecutionnode.
Thisenablesthereportingmoduletorecordandreportthesystemloadinformationontheexecutionnodeaswell,whichprovidesfurthergroundsfortheprob-ingmoduleonthesubmissionnodetodeterminewhethertheremotehostischeating.
(Ifthehostisheavilyloaded,wemightassumethehostisnotcheatingeventhoughtheprogressisreasonablysmall).
Also,hostingthereportingmoduleonthesamenodeincursadditionaloverhead,andweareabletostudyitseectsthroughexperimentation.
Communicationsbetweentheexecutionnodeandthereportingmodule,andbetweenthereportingmoduleandtheprobingmodule,areimplementedthroughUDPpackets.
Wechoosetousesocket-basedcommunicationbecauseitenablesustomovethereportingmoduleotheexecutionnodeif!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
%%%%%%%%&&&&&&&&''''''''''''''''''000000000000000000111111111111222222222222333333333344444444445555555555666666666677777788888899999999@@@@@@@@AAAAAAABBBBBBBCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDDEEEEEEEFFFFFFFGGGGGGGGGGGGGGGGGHHHHHHHHHHHHHHHHHIIIIIIIIIIIIIIIIPPPPPPPPQQQQQRRRRRSSSSSSSSTTTTTTTTUUUVVVWWWWXXXXYYYYYYYY````aaabbbcccdddeeeeeeeeeeeeeeeeffffffffffffffffgghhiiipppqqqqqqrrrssstttuuuuvvvvwwwwwwxxxyyddddddddeeeeffffgggghhhhiiiiiiiijjjjkkkkllll0.
9811.
021.
041.
061.
081.
11.
121.
14_201_Compress_202_Jess_209_Db_213_Javac_222_Mepgaudio_227_Mtrt_228_JackAverageNormalizedExecutionTimeBenchmarks10ms20ms50ms100ms200ms500msNoBeaconFigure5:Overheadofbeaconswitharemotere-portingmodule.
needed,andUDPispreferredbecauseithasaloweroverhead.
Asweareonlyinterestedingettinganin-dicatorofapplicationprogress,losingsomepacketsoccasionallyisnotabigproblem.
4EvaluationThissectiongivesexperimentalresultsgatheredbyexecutingamodiedversionoftheJikesRVMonhardware,andbysimulationstudiesofap2poverlaynetwork.
4.
1InstrumentationoverheadInthissection,wedeterminetheeectofprogressmonitoringonapplicationperformancebystudyingtheoverheadsofthebeaconsandthereportingmod-ule.
Tostudytheoverheadofbeaconsalone,werstrunthereportingmoduleonadierentnodethantheexecutionnode.
Figure5showstheoverheadofaddingthebeaconthreadinthevirtualmachine.
ExperimentswererunwiththeSpecJvm98bench-marksuiteondatasizesof100.
Instrumentationre-sultswerereportedtotheremotereportingmoduleattimeintervalsof10,20,50,100,200and500mil-liseconds,respectively.
Weobservethatonaverage,whenthetimeintervalbetweensuccessivereportsis500ms,theperformanceimpactislessthan1%.
Foranactualsystem,reportingintervalswouldbeinminutesorseconds,sotheoverheadonthepro-gramperformancewouldbeeectivelyzero.
Noticethatthisistheoverheadofmonitoringtheprogramprogressonly.
ThecostofinstrumentationintheJikesRVMsystem,whichweareleveragingforourmmmnnnoooooooooooooooooooooooooooooooooooooooooooooooooooooooooopppppppppppppppppppppppppppppqqqqqqqqqqqqqqqqqqqrrrrrrrrrrrrrrrrrrrssssssssssssttttttttttttuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuvvvvvvvvvvvvvvvvvvvvvvvvvwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwxxxxxxxxxxxxxxxxyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz¤¤¤§§§§§§¨¨¨¨¨¨°°°°°°°°°°±±±±±±±±±±±±±±±±······********0123456_201_Compress_202_Jess_209_Db_213_Javac_222_Mepgaudio_227_Mtrt_228_JackAverageSlowdown(Percentage)Benchmarks10ms20ms50ms100ms200ms500msNoBeaconFigure6:Overheadofhostingthereportingmoduleontheexecutionnode.
technique,isabout6.
3%[3],andcanbeloweredwithlargerinstrumentationintervals.
Nextwedeterminetheoverheadofhostingthere-portingmoduleontheexecutionnode.
Wecom-paretheperformanceofthissetupwithonethatusesaremotereportingmodule(asintheprevi-ouscase).
Figure6showstheresults.
Therearethreesourcesfortheoverhead:networktractoandfromthereportingmodule,costofperiodicallycollectinghostsystemloadinformation,andover-headofmaintainingtheapplicationprogressandsystemloaddatabase.
ApplicationexecutiononthehostslowsdownasaresultofcompetitionforCPUcycles.
Therstandlastkindsoftheoverheadwillgrowlinearlywiththenumberofremotelyexecut-ingjobsandtheyalsogrowasinstrumentationandprobingfrequenciesincrease.
Thecostofsystemloadinformationisproportionaltotheintervalofloadprobing.
Inourexperimentweassumeonerun-ningVM,oneprobingnode,andaloadtestintervalof200ms.
WegettheoverheadforthejobrunningontheVM.
WedidnotdotestswithmultipleVMsonthesameexecutionnodebecauseinthatcasetheoverheadisdiculttoexpressintermsoftheslowdown,andmultipleworkingVMscompeteforCPUcyclesamongthemselves.
Thepresenceofthereportingmodule,withoutbeacons,causesaslow-downof1.
4%.
Increasedreportingdensityincursadditionalslowdowns,butagainwithrealisticre-portingfrequencies,wecanassumethatpartoftheoverheadtobezero.
4.
2SimulationresultsInthissection,weevaluatetheeectivenessofourp2pschemeondiscoveringappropriateresourcesforexecutionofjobsandonenforcingfairnessincycle05010015020025030035001002003004005006007008009001000NumberofdiscoveredresourcesNodesTTL5TTL4TTL3TTL2TTL1Figure7:ThenumberofresourcesavailableateachnodewithincreasingTTL.
Thenodesaresortedinincreasingorderofdiscoveredresources.
sharingbysimulatinganetworkof1000nodes.
WedevelopedasimulatorofourproposedsystemontopofPastryrunningwiththedirectcommunicationdriver,whichallowsthecreationofmultiplePastrynodesonasinglemachine.
Weusedthetransit-stubInternetmodel[39]togenerateanIPnetworkwith10stubdomainrouters,100transitdomainrouters,andattach1000nodesrandomlytothe100stubdomainrouters.
Intherstsetofsimulations,wemeasuretheeec-tivenessofourprotocolfordisseminatingresourceannouncements.
Weassumeeachnodehassomere-sourcetoannouncetothenetwork,andusesthede-nedprotocoltosendtheannouncements.
WerunthesimulationvetimeswithTTLvaryingfrom1to5.
Foreachsimulation,wemeasurethenum-berofremotenodeswhoseannouncementsreachanygivennode.
Figure7showshowthenumberof"discovered"nodesbyeachnodeincreaseswiththeTTLvalue.
IncreasingTTLresultsinmorere-sourcesbeingdiscovered,butitalsoimpliesthatresourcesmaybefarawayinthenetworkproximityspace.
Tomeasuretheeectivenessofourcredit-basedschemeforenforcingfairness,wesimulatecyclesharingamongthe1000nodes,with500nodesac-tivelysubmittingjobs,whiletherestofthenodesonlycontributecycles.
TheTTLisxedatthreeforthissetofobservations.
Eachofthe500submittingnodesisfedwitharandomlygeneratedsequenceof100jobsofequallength,eachrunningforninetimeunits.
Theinterarrivaltimebetweenthejobsfol-lowsauniformdistributionbetween1and17timeunits.
Wecomparethejobthroughputofthreesce-narios:(1)all500submittingnodesarehonest;(2)250submittingnodesarehonestand250submitting05000100001500020000250003000035000400004500050000020040060080010001200NumberofjobsTimeJobsissuedJobscompletedFigure8:Thenumberofjobsissued,andcompletedovertheperiodofourtrace.
Everynodecontributesresourcestothesystemandisfair.
050001000015000200002500030000350004000045000500000200400600800100012001400NumberofjobsTimeJobsissuedJobscompletedFigure9:Thenumberofjobsissued,andcompletedovertheperiodofourtraceforthenon-cheatingnodes.
Thefeedbacksystemisdisabled.
nodescheatbyonlysubmittingjobsandneverac-ceptingremotejobs,andthefairnessmechanismisnotturnedon;and(3)sameas(2)butwiththefair-nessmechanismturnedon.
Forcase(3),thethresh-oldfordetectingcheatingnodesissettothree,i.
e.
,acheatingnodecanrunuptothreejobswithoutcompensatingthesystem,butwhenitattemptstorunmorejobs,othernodesignoreitsrequestsforre-sources.
ThejobthroughputunderthesescenariosareshowninFigures8,9,and10,respectively.
Figure8showsthenumberofjobsissuedandthenumberofjobscompletedagainstoursimulatedtimewhenall500nodesarehonest.
Itisobservedthatthejobsdonothavetowaitiffreeresourcesareavailable.
Thenumberofcompletedjobscloselyfollowthenumberofissuedjobs.
Theslightin-creaseinthedierenceovertimeisduetothefactthemorejobswererequestedthantheavailablere-sources.
However,alljobscompletedataboutthe1150thtimeunit,only150timeunitsafterallthejobswereissued.
050001000015000200002500030000350004000045000500000200400600800100012001400NumberofjobsTimeJobsissuedJobscompletedFigure10:Thenumberofjobsissued,andcom-pletedovertheperiodofourtraceforthenon-cheatingnodes.
Thefeedbacksystemisenabled.
Figure9showswhen250submittingnodescheatandthecredit-basedmechanismisnotturnedon,thenon-cheatingnodesexperiencealargerdelayintheirjobcompletion.
Thereisadelayof345timeunitsforallthejobstocomplete.
Thisissigni-cantconsideringthatthejoblengthsareonly9timeunits.
Finally,Figure10showsthecredit-basedmech-anismeectivelyisolatesthecheatingnodesandthejobsfromthenon-cheatingnodesmademoreprogresscomparedtothecasewithoutthecredit-basedmechanism.
NotethatthejobdelayinthiscaseislessthanthatinFigure8,becausehere250non-cheatingnodesweresharingcyclesofatotalof750nodes,whereasinthelattercase500nodessharedcyclesof1000nodes.
Thissimulationshowsthatthecredit-basedmechanismquicklyprohibitscheatingnodesfromconsumingothernodes'cycles.
5RelatedworkWediscussrelatedworkoncyclesharingovertheInternet,oncompilerinstrumentations,andonfair-nessinp2pstoragesharingsystems.
CyclesharingovertheInternetTheideaofcyclesharingamongalargenumberofad-ministrativelyindependent,geographicallydis-persed,o-the-shelfdesktopsispopularizedbytheSETI@home[34]project.
SimilarapproachesforsolvinglargescalescienticproblemsarealsoadoptedinsystemssuchasDistributed.
NET[10],Entropia[12],Genome@home[18],andNile[28].
Thesesystemsimplementacentralmanagerthatisresponsibleforthedistributionoftheproblemset,andthecollectionandanalysisoftheresults.
Userstypicallydownloadtheclientprogramsman-uallyandthenexecutethemontheirresources.
Theclientprogramsarespeciallydevelopedapplicationsthattheresourceownershavetoexplicitlytrust[6].
Theclientsperiodicallycontactthecentralman-agerstoprovideresultsandtoreceivefurtherdataforprocessing.
Theclientsarepurevolunteersinnature,i.
e.
,theydonotreceiveanyresourcecontri-butionfortheirowntasks.
Theaimofourprojectistoprovideallnodesinthesystemwiththeca-pabilitytoutilizesharedresources.
Thisprovidesanincentiveformoreresourceownerstocontributeresourcestothesystem,henceincreasingtheinstan-taneouscomputecapacityofthesystem.
Variousgridplatformsalsosharethesamegoalofdistributedsharingresources.
Condor[24]providesamechanismforsharingresourcesinasinglead-ministrativedomainbyharnessingtheidle-cyclesondesktopmachines.
Globus[15]andLegion[20]al-lowuserstoshareresourcesacrossadministrativedomains.
However,theresourcemanagementishi-erarchical,andtheusershavetoobtainaccountsonalltheresourcesthattheyintendtouse[6].
PUNCH[23]decouplesthesharedresourceusersfromtheunderlyingoperatingsystemusersoneachresource,henceeliminatingtheneedforaccountsonallthesharedresources.
SunGridEngine[37]isanothersystemthatharnessesthecomputepowersofdistributedresourcestosolvelargescalescien-ticproblems.
However,allofthesesystemsrelyonsomeformsofcentralizedresourcemanagementandthereforearesusceptibletoperformancebottle-necks,single-pointoffailures,andunfairnessissuesthatoursystemavoidsbyusingp2pmechanisms.
Fairpeer-to-peerstoragesharingTheideaofenforcingfairnesshasbeenextensivelystudiedinpeer-to-peerstoragesystems,motivatedbytheus-agestudies[11,33]whichshowthatmanyuserscon-sumeresourcesbutdonotcompensatebycontribut-ing.
CFS[9]allowsonlyaspeciedstoragequotaforusebyothernodeswithoutanyconsiderationforthespacecontributedtothesystembytheconsumer.
PAST[31]employsaschemewhereatrustedthirdpartyholdsusagecerticatesthatcanbeusedinde-terminingquotasforremoteconsumers.
Thequotascanbeadjustedaccordingtothecontributionofanode.
Samsara[8]enforcesfairnessinp2pstoragewithoutrequiringtrustedthirdparties,symmetricstoragerelationships,monetarypayment,orcerti-edidentities.
Itutilizesanextensiveclaimmanage-mentwhichleveragesselshbehaviorofeachnodetoachieveanoverallfairsystem.
ThefairnessinourcyclesharingsystemwasmotivatedbySamsara.
However,fairnessincyclesharingismorecomplexthanindatasharingasonceacomputationiscom-pleted,theexecutionnodehasnodirectmeansofpunishingacheatingconsumer.
SHARP[17]pro-videsamechanismforresourcepeeringbasedontheexchangeofticketsandleases,whichcanbetradedamongpeeringnodesforresourcereservationandcommittedconsumption.
CreditsinoursystemaresimilartoticketsinSHARP.
However,oursystemusesthecreditreportstoenforcefairnessofsharing,andnotasameanforadvanceresourcereservations.
Therehavealsobeeneortstodesignageneralframeworkfortradingresourcesinp2psystems.
Datatrading[5]isproposedtoallowaconsumerandaresourceproviderexchangeanequalamountofdata,andcheaterscanbepunishedbywith-holdingthedata.
Theapproachrequiressymmet-ricrelationshipsanddonotapplywelltop2psys-temswherethereisverylittlesymmetryinresourcesharingrelationships.
Theuseofmicropaymentsasincentivesforfairsharingisproposedin[19].
Fileteller[22]suggeststheuseofsuchmicropay-mentstoaccountforresourceconsumptionandcon-tribution.
In[38],adistributedaccountingframe-workisdescribed,whereeachnodemaintainsasignedrecordofeverydataobjectitstoresdirectlyonitselforonothernodesonitsbehalf,andeachnodeperiodicallyauditsrandomothernodesbycomparingmultiplecopiesofthesamerecords.
Thesystemrequirescertiedentitiestopreventagainstmaliciousaccusations,andtheauditorhastoworkforothernodes,withoutanydirectbenet.
Oursystemimplementsadistributedaccountingsystemaswell,whereanodeveriescreditreportsofare-motenodeonlywhenithastodoanexchangewithit,whichisadirectbenet.
Compilerinstrumentationandproofcarry-ingcodeTheconceptofcompilergeneratedin-strumentationandmonitoringofprogramexecutionwithinaJVMisnotnew.
TheSunHotspot[29]compiler,compilersfortheIBMJDK[36],andcom-pilersfortheJikesRVM[1]alluseeithercompilergeneratedprograminstrumentationoranexamina-tionoftheactiveroutinesonthestacktodeter-minehotmethods.
Thisinturnissimilartoprol-ing[2,4,13]forcollectinginformationaboutwheretimeisspentduringaprogram'sexecution.
Theseeortsareorthogonaltoourwork,andcouldcom-plementourworkbyprovidingamechanismforcol-lectinginformationabouttotalprogramruntime.
Ournoveltyisinbootstrappingothealreadyexist-ingmonitoringofprogramexecutionssupportedbyJVMsaspartoftheiroptimizationstrategytoallowtheprogressofaprogramtoberemotelytracked.
Otherprojects(e.
g.
[21])haveusedinstrumenta-tiontocollectdataforperformancepurposes,andallowson-the-yinstrumentationofstaticallycom-piledprograms.
TheGRAMcomponentoftheGlobusproject[16]alsomonitorsprogramexecution,andusesthisin-formationtochangetheresourcerequirementsoftheapplicationtogivebetterqualityofservice.
Ourworkdiersinourmotivation–weareusingthemonitoringtodetermineifwearegettingare-sourceaspromised;andinourimplementation–themonitoringmeasuresprogramperformanceviaautomaticinstrumentationbyaJVMandnotbyexternalmeasuresorbyprogrammerinsertedcall-outsfromtheprogram.
Thisallowsustonotrequireindividualprogramstobeadaptedtooursysteminordertouseit.
Theultimategoalofourworkisrelatedtoproofcarryingcode[27].
Wedierfromthatworkinthattheultimategoalhereistohaveaprogramcertifytothesubmitter,ratherthanthehost,factsaboutitsexecution,withthesefactsboundtotheprogramformitself.
6ConclusionWehavedescribedthedesignofasystem,andourimplementedprototype,thatexploitsthesafety,portabilityandinternalprolingcapabilitiesofJavaandJavaVirtualMachines.
Thissystemallowsadecentralizedp2pnetworktobeusedtoadvertiseandallocateresources,andcontainsacreditsys-temthatallowsdecentralizedsharingofresourcesandevaluationofcredit-worthiness.
Ourexperi-mentalresultsshowthatourfairnessmechanismsworkwelltopunishcheatingnodes,andourmoni-toringofprogramprogresshaseectivelyzeroover-head.
Becauseofitsdecentralizednature,leadingtolowcostsforentryandexitfromthenetwork,oursystemisidealforconstructingad-hocintra-organizationalnetworksofpooledresources,andforconstructingpoolsofresourcesforsmallbusinessandeducationalpurposes.
AcknowledgmentWethanktheanonymousreviewersfortheirhelp-fulcomments.
ThisworkwassupportedinpartbyNSFCAREERawardgrantACI-0238379andNSFgrantsCCR-0313026andCCR-0313033.
References[1]B.
Alpernandal.
et.
TheJalapeoVirtualMa-chine.
IBMSystemJournal,39(1),February2000.
[2]J.
M.
Anderson,L.
M.
Berc,J.
Dean,S.
Ghe-mawat,M.
R.
Henzinger,S.
-T.
A.
Leung,R.
L.
Sites,M.
T.
Vandevoorde,C.
A.
Waldspurger,andW.
E.
Weihl.
Continuousproling:WherehaveallthecyclesgoneInProc.
SixteenthACMSymposiumonOperatingSystemsPrin-ciples(SOSP),pages1–14,1997.
[3]M.
Arnold.
OnlineProlingandFeedback-DirectedOptimizationofJava.
PhDthesis,Rutgers,TheStateUniversityofNewJersey,October2002.
[4]T.
BallandJ.
R.
Laurus.
Ecientpathprol-ing.
InProc.
29thAnnualIEEE/ACMInterna-tionalSymposiumonMicroarchitecture,pages46–57,1996.
[5]B.
F.
CooperandH.
Garcia-Molina.
Peer-to-peerresourcetradinginareliabledistributedsystem.
InProc.
FirstInternationalWorkshoponPeer-to-PeerSystems,Cambridge,MA,2002.
[6]A.
R.
Butt,S.
Adabala,N.
H.
Kapadia,R.
J.
Figueiredo,andJ.
A.
B.
Fortes.
Grid-computingportalsandsecurityissues.
JournalofParallelandDistributedComputing:SpecialissueonScalableWebServicesandArchitec-ture,63(10):1006–1014,October2003.
[7]M.
Castro,P.
Druschel,Y.
C.
Hu,andA.
Row-stron.
Exploitingnetworkproximityinpeer-to-peeroverlaynetworks.
Technicalreport,TechnicalreportMSR-TR-2002-82,2002,2002.
http://research.
microsoft.
com/antr/PAST/localtion.
ps(17Oct2003).
[8]L.
P.
CoxandB.
D.
Noble.
Samsara:Honoramongthievesinpeer-to-peerstorage.
InProc.
19thACMSymposiumonOperatingSystemsPrinciples,October2003.
[9]F.
Dabek,M.
F.
Kaashoek,D.
Karger,R.
Mor-ris,andI.
Stoica.
Wide-areacooperativestor-agewithCFS.
InProc.
SOSP,October2001.
[10]distributed.
net.
distributed.
netprojects(11April2003).
http://www.
distributed.
net/projects.
php(28September2003).
[11]E.
AdarandB.
A.
Huberman.
FreeridingonGnutella.
FirstMonday,5(10),October2000.
[12]Entropia,Inc.
Entropia:Pcgridcomputing(16June2003).
http://www.
entropia.
com/index.
asp(28September2003).
[13]J.
FenlasonandR.
Stallman.
GNUgprofmanual(Nov7,1998).
http://www.
gnu.
org/manual/gprof-2.
9.
1/gprof.
html(Oct14,2003).
[14]FIPS180-1.
SecureHashStandard.
Techni-calReportPublication180-1,FederalInforma-tionProcessingStandard(FIPS),NIST,USDepartmentofCommerce,WashingtonD.
C.
,April1995.
[15]I.
FosterandC.
Kesselmann.
Globus:AMetacomputingInfrastructureToolkit.
Inter-nationalJournalofSupercomputingApplica-tions,11(2):115–128,Jan.
1997.
[16]I.
Foster,A.
Roy,andV.
Sander.
Aqual-ityofservicearchitecturethatcombinesre-sourcereservationandapplicationadaptation.
InProc.
8thInternationalWorkshoponQual-ityofService,2000.
[17]Y.
Fu,J.
Chase,B.
Chun,S.
Schwab,andA.
Vahdat.
SHARP:Anarchitectureforsecureresourcepeering.
InProc.
19thACMSympo-siumonOperatingSystemsPrinciples,October2003.
[18]Genome@home.
Genomeathome(26September2003).
http://www.
stanford.
edu/group/pandegroup/genome/index.
html(29September2003).
[19]P.
Golle,K.
Leyton-Brown,andI.
Mironov.
In-centivesforsharinginpeer-to-peernetworks.
InProc.
ThirdACMConferenceonElectroniCommerce,Tampa,FL,2001.
[20]A.
S.
GrimshawandW.
A.
Wulf.
Legion–AViewfrom50,000feet.
InProc.
5thIEEEInter-nationalSymposiumonHighPerformanceDis-tributedComputing(HPDC'96),Syracuse,NY,1996.
[21]J.
K.
Hollingsworth,B.
P.
Miller,M.
J.
R.
Goncalves,O.
Naim,Z.
Xu,andL.
Zheng.
MDL:Alanguageandcompilerfordynamicprograminstrumentation.
InProc.
IEEEPACT,pages201–,1997.
[22]J.
Ioannidis,A.
Keromytis,andV.
Prevelakis.
Fileteller:Payingandgettingpaidforlestor-age.
InProc.
SixthAnnualConferenceonFi-nancialCryptography,Bermuda,2002.
[23]N.
H.
KapadiaandJ.
A.
B.
Fortes.
PUNCH:AnarchitectureforWeb-enabledwide-areanetwork-computing.
ClusterComputing:TheJournalofNetworks,SoftwareToolsandAp-plications,2(2):153–164,Sep.
1999.
[24]M.
J.
M.
J.
Litzkow,M.
Livny,andM.
W.
Mutka.
Condor-Ahunterofidleworksta-tions.
InProc.
8thInternationalConferenceonDistributedComputingSystems(ICDCS1988),pages104–111,SanJose,CA,1988.
[25]J.
Moreira,S.
Midki,M.
Gupta,P.
Arti-gas,P.
Wu,andG.
Almasi.
TheNINJAproject:MakingJavaworkforhighperfor-mancecomputing.
CommunicationsoftheACM,44(10):102–109,October2001.
[26]J.
E.
Moreira,S.
P.
Midki,andM.
Gupta.
Fromoptomegaops:Javafortechnicalcom-puting.
ACMTransactionsonProgrammingLanguagesandSystems,22(2):265–295,March2000.
IBMResearchReportRC21166.
[27]G.
Necula.
Proofcarryingcode.
1997.
[28]Nile.
Scalablesolutionfordistributedpro-cessingofindependantdata(18June1999).
http://www.
nile.
cornell.
edu/index.
html(29September2003).
[29]M.
Paleczny,C.
Click,andC.
Vick.
TheJavaHotSpotservercompiler.
InProc.
2001USENIXJavaVirtualMachineSymposium,2001.
[30]S.
Ratnasamy,P.
Francis,M.
Handley,R.
Karp,andS.
Schenker.
AScalableContent-AddressableNetwork.
InProc.
ACMSIGCOMM2001ConferenceonApplications,Technologies,Architectures,andProtocolsforComputerCommunication(SIGCOMM'01),pages161–172,SanDiego,CA,2001.
[31]A.
RowstronandP.
Druschel.
PAST:Alarge-scale,persistentpeer-to-peerstorageutility.
InProc.
18thACMSymposiumonOperatingSys-temsPrinciples,October2001.
[32]A.
RowstronandP.
Druschel.
Pastry:Scal-able,distributedobjectlocationandrout-ingforlarge-scalepeer-to-peersystems.
InProc.
IFIP/ACMInternationalConferenceonDistributedSystemsPlatforms(Middleware),pages329–350,November2001.
[33]S.
Saroiu,G.
Krishna,andS.
Gribble.
Amea-surementstudyofpeer-to-peerlesharingsys-tems.
InProc.
SPIEConferenceonMultime-diaComputingandNetworking,SanJose,CA,2002.
[34]SETI@home.
Searchforextraterrestrialintelligenceathome(29September2003).
http://setiathome.
ssl.
berkeley.
edu/index.
html(29September2003).
[35]I.
Stoica,R.
Morris,D.
Karger,M.
F.
Kaashoek,andH.
Balakrishnan.
Chord:AScalablePeer-to-peerLookupServiceforInter-netApplications.
InProc.
ACMSIGCOMM2001ConferenceonApplications,Technolo-gies,Architectures,andProtocolsforComputerCommunication(SIGCOMM'01),pages149–160,SanDiego,CA,2001.
[36]T.
Suganuma,T.
Yasue,M.
Kawahito,H.
Ko-matsu,andT.
Nakatani.
Adynamicoptimiza-tionframeworkforaJavajust-in-timecom-piler.
InProc.
ACMConferenceonObject-OrientedProgrammingSystems,Languages,andApplications(OOPSLA),pages180–195,2001.
[37]Sun(TM)Microsystems.
SunONEGridEngineSoftware(26June2003).
http://wwws.
sun.
com/software/gridware/sge.
html(29September2003).
[38]T-W.
J.
NganandD.
S.
WallachandP.
Dr-uschel.
Enforcingfairsharingofpeer-to-peerresources.
InProc.
SecondInternationalWork-shoponPeer-to-PeerSystems,Berkeley,CA,2003.
[39]E.
Zegura,K.
Calvert,andS.
Bhattacharjee.
HowtoModelanInternetwork.
InProc.
IEEEINFOCOM,March1996.
[40]B.
Y.
Zhao,J.
D.
Kubiatowicz,andA.
D.
Joseph.
Tapestry:AnInfrastructureforFault-ResilientWide-areaLocationandRouting.
TechnicalReportUCB//CSD-01-1141,U.
C.
Berkeley,April2001.