All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.

Information Report

Category:
## Documents

Published:

Views: 81 | Pages: 69

Extension: PDF | Download: 0

Share

Description

Networks Cannot Compute Their Diameter in Sublinear Time. Stephan Holzer. Silvio Frischknecht Roger Wattenhofer. ETH Zurich – Distributed Computing Group . Distributed network G raph G of n nodes. 2. 1. 5. 3. 4.

Transcript

Networks Cannot Compute Their Diameter in Sublinear TimeStephan HolzerSilvio Frischknecht Roger WattenhoferETH Zurich – Distributed Computing Group Distributed network Graph G of n nodes21534Distributed network Graph G of n nodes21534Distributed network Graph G of n nodes2Localinfor-mationonly11534Distributed network Graph G of n nodes2Localinfor-mationonly1532413Slide inspiredbyDanuponNanongkaiDistributed network Graph G of n nodes2Localinfor-mationonly1532?413Distributed network Graph G of n nodesLimitedbandwidth2log nLocalinfor-mationonlylog nlog n1log n5log n32log n?413Distributed network Graph G of n nodesLimitedbandwidth2SynchronizedInternal computationsnegligiblelog nLocalinfor-mationonlylog nlog n1log n5log n32log n41?Time complexity: number of communication rounds3Distributed algorithms:a simple exampleCount thenodes!Count thenodes!Compute BFS-TreeCount thenodes!Compute BFS-Tree0Count thenodes!Compute BFS-Tree11101Count thenodes!Runtime: ?2Compute BFS-Tree2. Count nodes insubtrees121221021DiameterDiameter of a networkDistancebetweentwonodes = Numberof hops ofshortestpath Diameter of a networkDistancebetweentwonodes = Numberof hops ofshortestpath Diameter of a networkDistance between two nodes = Number of hops of shortest path Diameter of network = Maximum distance, between any two nodes Diameter of a networkDistancebetweentwonodes = Number of hops of shortestpath Diameter of network = Maximum distance, betweenanytwonodes Diameter ofthisnetwork?Fundamental graph-problems Spanning Tree – Broadcasting, Aggregation, etc Minimum Spanning Tree – Efficient broadcasting, etc. Shortest path – Routing, etc. Steiner tree – Multicasting, etc. Many other graph problems. ThanksforslidetoDanuponNanongkaiFundamental graph-problems Spanning Tree – Broadcasting, Aggregation, etc Minimum Spanning Tree – Efficient broadcasting, etc. Shortest path – Routing, etc. Steiner tree – Multicasting, etc. Many other graph problems. Global problems:Ω( D ) Localinfor-mationonly2?13Fundamental graph-problems Maximal Independent Set Coloring Matching Fundamental graph-problems Maximal Independent Set Coloring Matching Local problems: runtime independent of / smaller than D e.g. O(log n)Fundamental problems Spanning Tree – Broadcasting, Aggregation, etc Minimum Spanning Tree – Efficient broadcasting, etc. Shortest path – Routing, etc. Steiner tree – Multicasting, etc. Many other graph problems. Diameter appears frequently in distributed computing Fundamental problems 1. Formal definition?Spanning Tree – Broadcasting, Aggregation, etc Minimum Spanning Tree – Efficient broadcasting, etc. Shortest path – Routing, etc. Steiner tree – Multicasting, etc. Many other graph problems. Diameter appears frequently in distributed computing Complexity of computing D? .Known: Ω (D)≈Ω(1)Even if D = 3This talk: Ω(n) Networks cannot compute their diameter in sublinear time!Diameter of a networkDiameter ofthisnetwork?Distance between two nodes = Number of hops of shortest path Diameter of network = Maximum distance, between any two nodes Networks cannot compute their diameter in sublinear time!Networks cannot compute their diameter in sublinear time!Networks cannot compute their diameter in sublinear time!Networks cannot compute their diameter in sublinear time!Networks cannot compute their diameter in sublinear time!Networks cannot compute their diameter in sublinear time!Base graphhas diameter 3 Networks cannot compute their diameter in sublinear time!has diameter 3 2?Networks cannot compute their diameter in sublinear time!Pair of nodes not connected on both sides?has diameter 3 2?Networks cannot compute their diameter in sublinear time!Pair of nodes not connected on both sides?has diameter 3 2?Networks cannot compute their diameter in sublinear time!Pair of nodes not connected on both sides?Now: slightly more formalNetworks cannot compute their diameter in sublinear time!Pair of nodes not connected on both sides?Label potential edgesNetworks cannot compute their diameter in sublinear time!Pair of nodes not connected on both sides?Label potential edges11Networks cannot compute their diameter in sublinear time!Pair of nodes not connected on both sides?Label potential edges1122Networks cannot compute their diameter in sublinear time!Pair of nodes not connected on both sides?Label potential edges113322Networks cannot compute their diameter in sublinear time!Pair of nodes not connected on both sides?Label potential edges11332244Networks cannot compute their diameter in sublinear time!Pair of nodes not connected on both sides?11332244Networks cannot compute their diameter in sublinear time!Pair of nodes not connected on both sides?Given graph11332244Networks cannot compute their diameter in sublinear time!Pair of nodes not connected on both sides?BA113332224444Θ(n) edgesNetworks cannot compute their diameter in sublinear time!Pair of nodes not connected on both sides?Same as “A and B not disjoint?”BA 112333222344444Θ(n) edgesNetworks cannot compute their diameter in sublinear time!Pair of nodes not connected on both sides?Same as “A and B not disjoint?”B ⊆ [n2]A ⊆ [n2]112333222344444Θ(n) edgesNetworks cannot compute their diameter in sublinear time! “A and B not disjoint?”B ⊆ [n2]A ⊆ [n2]2344Networks cannot compute their diameter in sublinear time!Pair of nodes not connected on both sides?Same as “A and B not disjoint?”Communication Complexity randomized: Ω(n 2) bitsB ⊆ [n2]A ⊆ [n2]23Ω(n) time44Θ(n) edgesDiameter Approximation3/2-εapproximating the diameter takes W(n1/2) Extend2 vs. 3D = 9 basegraph3/2-εapproximating the diameter takes W(n1/2) Extend2 vs. 3D = 9 basegraph3/2-εapproximating the diameter takes W(n1/2) Extend2 vs. 3D = 9 basegraph93/2-εapproximating the diameter takes W(n1/2) Extend2 vs. 3D = 9 basegraph3/2-εapproximating the diameter takes W(n1/2) Extend2 vs. 3D = 9 basegraph53/2-εapproximating the diameter takes W(n1/2) Extend2 vs. 3D = 9 basegraphD = 7 goodgraph-------------Factor: 3/2573/2-εapproximating the diameter takes W(n1/2) Extend2 vs. 3D = 9 basegraphD = 7 goodgraph-------------Factor: 3/2 -ε7Technique is generalTechnique is generalGTechnique is generalGTechnique is generalcutGTechnique is generalcutTechnique is generalcutf’(Ga,Gb)cutAlice Bobf’(Ga,Gb)cutAlice Bobf’(Ga,Gb)cutAlice Bobf’(Ga,Gb)cutAlice Bobf’(Ga,Gb)cut Time(g) Time(f) ≥ ----------- |cut|SummaryDiameter Ω(n)3/2-eps approximation takes Ω(n1/2)7cutgeneraltechniqueThanks!

Recommended

Related Search

We Need Your Support

Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks

SAVE OUR EARTH

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...Sign Now!

We are very appreciated for your Prompt Action!

x