dynamic hypercube topology distributed computing group动态超立方体拓扑的分布式计算组.ppt

《dynamic hypercube topology distributed computing group动态超立方体拓扑的分布式计算组.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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