Randomized Algorithms (Spring 2010)/More on Chernoff bounds: Difference between revisions
imported>WikiSysop (Created page with '== Permutation Routing == Now we introduce a more "serious" application of Chernoff bounds: the two-phase randomized algorithm for the permutation routing in a hypercube. == Jo…') |
|||
| Line 1: | Line 1: | ||
== Permutation Routing == | == Permutation Routing == | ||
The problem raises from parallel computing. Consider that we have <math>N</math> processors, connected by a communication network. The processors communicate with each other by sending and receiving '''packets''' through the network. We consider the following packet routing problem: | |||
* Every processor is sending a packet to a unique destination. Therefore for <math>[N]</math> the set of processors, the destinations are given by a '''permutation''' <math>\pi</math> of <math>[N]</math>, such that for every processor <math>i\in[N]</math>, the processor <math>i</math> is sending a packet to processor <math>\pi(i)</math>. | |||
* The communication is '''synchronized''', such that for each '''round''', every link (an edge of the graph) can forward at most one packet. | |||
With a complete graph as the network. For any permutation <math>\pi</math> of <math>[N]</math>, all packets can be routed to their destinations in parallel with one round of communication. However, such an ideal connectivity is usually not available in reality, either because they are too expensive, or because they are physically impossible. We are interested in the case the graph is '''sparse''', such that the number of edges is significantly smaller than the complete graph, yet the distance between any pair of vertices is small, so that the packets can be efficiently routed between pairs of vertices. | |||
The hypercube is one of the graphs with these desirable properties. | |||
=== Routing in a hypercube === | |||
== Johnson-Lindenstrauss Theorem == | == Johnson-Lindenstrauss Theorem == | ||
Revision as of 13:39, 24 February 2010
Permutation Routing
The problem raises from parallel computing. Consider that we have [math]\displaystyle{ N }[/math] processors, connected by a communication network. The processors communicate with each other by sending and receiving packets through the network. We consider the following packet routing problem:
- Every processor is sending a packet to a unique destination. Therefore for [math]\displaystyle{ [N] }[/math] the set of processors, the destinations are given by a permutation [math]\displaystyle{ \pi }[/math] of [math]\displaystyle{ [N] }[/math], such that for every processor [math]\displaystyle{ i\in[N] }[/math], the processor [math]\displaystyle{ i }[/math] is sending a packet to processor [math]\displaystyle{ \pi(i) }[/math].
- The communication is synchronized, such that for each round, every link (an edge of the graph) can forward at most one packet.
With a complete graph as the network. For any permutation [math]\displaystyle{ \pi }[/math] of [math]\displaystyle{ [N] }[/math], all packets can be routed to their destinations in parallel with one round of communication. However, such an ideal connectivity is usually not available in reality, either because they are too expensive, or because they are physically impossible. We are interested in the case the graph is sparse, such that the number of edges is significantly smaller than the complete graph, yet the distance between any pair of vertices is small, so that the packets can be efficiently routed between pairs of vertices.
The hypercube is one of the graphs with these desirable properties.