資源描述：
《dynamic hypercube topology distributed computing group動(dòng)態(tài)超立方體拓?fù)涞姆植际接?jì)算組.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、DynamicHypercubeTopologyStefanSchmidURAW2005UpperRhineAlgorithmsWorkshopUniversityofTübingen,Germany1Staticvs.DynamicNetworks(1)NetworkgraphG=(V,E)V=setofvertices(“nodes”,machines,peers,…)E=setofedges(“connections”,wires,links,pointers,…)“Traditional”,sta
2、ticnetworksFixedsetofvertices,fixedsetofedgesE.g.,interconnectionnetworkofparallelcomputersFatTreeTopologyParallelComputer2StefanSchmid,ETHZurich@URAW2005Staticvs.DynamicNetworks(2)DynamicnetworksSetofnodesand/orsetofedgesisdynamicHere:nodesmayjoinandleav
3、eE.g.,peer-to-peer(P2P)systems(Napster,Gnutella,…)DynamicChordTopology3StefanSchmid,ETHZurich@URAW2005DynamicPeer-to-PeerSystemsPeer-to-PeerSystemscooperationofmanymachines(tosharefiles,CPUcycles,etc.)usuallydesktopcomputersundercontrolofindividualusersus
4、ermayturnmachineonandoffatanytime=>ChurnHowtomaintaindesirablepropertiessuchasconnectivity,networkdiameter,nodedegree,...?4StefanSchmid,ETHZurich@URAW2005TalkOverviewModelIngredients:basicalgorithmsonhypercubegraphAssemblingthecomponentsResultsforthehyper
5、cubeConclusion,generalizationandopenproblemsDiscussion5StefanSchmid,ETHZurich@URAW2005Model(1):NetworkModelTypicalP2PoverlaynetworkVerticesv2V:peers(dynamic:mayjoinandleave)Directededges(u,v)2E:uknowsIPaddressofv(static)Assumption:Overlaynetworkbuildsupon
6、completeInternetgraphSendingamessageoveranoverlayedge=>routingintheunderlyingInternetgraph6StefanSchmid,ETHZurich@URAW2005Model(2):Worst-Case(Adversarial)DynamicsModelworst-casefaultswithanadversaryADV(J,L,?)ADV(J,L,?)hascompletevisibilityoftheentirestate
7、ofthesystemMayaddatmostJandremoveatmostLpeersinanytimeperiodoflength?7StefanSchmid,ETHZurich@URAW2005Model(3):CommunicationRoundsOursystemissynchronous,i.e.,ouralgorithmsruninroundsOneround:receivemessages,localcomputation,sendmessagesHowever:Realdistribu
8、tedsystemsareasynchronous!But:Notionoftimenecessarytoboundtheadversary8StefanSchmid,ETHZurich@URAW2005OverviewofDynamicHypercubeSystemIdea:Arrangepeersintoasimulatedhypercubewhereeachnodeconsistsofseveral(logarithmi
