TCS Wiki - User contributions [en]

Randomized Algorithms (Spring 2010)/More on Chernoff bounds

2010-02-25T14:56:37Z

172.21.5.128: /* A two-phase randomized routing algorithm */

== 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.

=== Routing on a hypercube ===
A [http://en.wikipedia.org/wiki/Hypercube hypercube] (sometimes called a Boolean cube, a Hamming cube, or just cube) is defined over <math>N</math> nodes, for <math>N</math> a power of 2. We assume that <math>N=2^d</math>. A hypercube of <math>d</math> dimensions, or a <math>d</math>-cube, is an undirected graph with the vertex set <math>\{0,1\}^d</math>, such that for any <math>u,v\in\{0,1\}^d</math>, <math>u</math> and <math>v</math> are adjacent if and only if <math>h(u,v)=1</math>, where <math>h(u,v)</math> is the [http://en.wikipedia.org/wiki/Hamming_distance Hamming distance] between <math>u</math> and <math>v</math>.

A <math>d</math>-cube is a <math>d</math>-degree regular graph over <math>N=2^d</math> vertices. For any pair <math>(u,v)</math> of vertices, the distance between <math>u</math> and <math>v</math> is at most <math>d</math>. (How do we know this? Since it takes at most <math>d</math> steps to fix any binary string of length <math>d</math> bit-by-bit to any other.) This directly gives us the following very natural routing algorithm.

{|border="1"
|'''Bit-Fixing Routing Algorithm:'''
|-
|For each packet:
#Let <math>u, v\in\{0,1\}^d</math> be the origin and destination of the packet respectively.
#For <math>i=1</math> to <math>d</math>, do:
::if <math>u_i\neq v_i</math> then traverse the edge <math>(v_1,\ldots,v_{i-1},u_i,\ldots,u_d)\rightarrow (v_1,\ldots,v_{i-1},v_i,u_{i+1}\ldots,u_d)</math>.
|}

;Oblivious routing algorithms
:This algorithm is blessed with a desirable property: it depends only on the origin, the destination, and the current node. We call the algorithms with this property '''oblivious''' routing algorithms. Compared to the routing algorithms which are adaptive to the path that the packet traversed, oblivious routing is more simple thus can be implemented by smaller routing table (or simple devices called '''switches''').

;Queuing policies
:When routing <math>N</math> packets in parallel, it is possible that more than one packets want to use the same edge at the same time. We assume that a queue is associated to each edge, such that the packets to be delivered through an edge are put into the queue associated with the edge. With some '''queuing policy''' (e.g. FIFO, or furthest to do), the queued packets are delivered through the edge by at most one packet per each round.

For the bit-fixing routing algorithm defined above, regardless of the queuing policy, there always exists a bad permutation <math>\pi</math> which specifies the destinations, such that it takes <math>\Omega(\sqrt{N})</math> steps by the bit-fixing algorithm to route all <math>N</math> packets to their destinations. (You can prove this by yourself.)

This is pretty bad, because we expect that the routing time is comparable to the diameter of the network, which is only <math>d=\log N</math> for hypercube.

The lower bound actually applies generally for any deterministic oblivious routing algorithms:

{|border="1"
|'''Theorem [Kaklamanis, Krizanc, Tsantilas, 1991]'''
:In any <math>N</math>-node communication network with maximum degree <math>d</math>, any deterministic oblivious algorithm for routing an arbitrary permutation requires <math>\Omega(\sqrt{N}/d)</math> parallel communication steps in the worst case.
|}

The proof of the lower bound is rather technical and complicated. However, the intuition is quite clear: for any oblivious rule for routing, there always exists a permutation which causes a very high '''congestion''', such that many packets have to be delivered through the same edge, thus no matter what queuing policy is used, the maximum delay must be very high.

=== A two-phase randomized routing algorithm ===
It is somehow surprising that routing the packet first to some completely irrelevant "relay" actually improves the overall performance.

{|border="1"
|'''Two-Phase Routing Algorithm:'''
|-
|For each packet:
'''Phase I:''' Route the packet to a random destination using the bit-fixing algorithm.

'''Phase II:''' Route the packet from the random location to its final destination using the bit-fixing algorithm.
|}

== Johnson-Lindenstrauss Theorem ==

Randomized Algorithms (Spring 2010)/More on Chernoff bounds

2010-02-25T14:50:34Z

172.21.5.128: /* A two-phase randomized routing algorithm */

== 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.

=== Routing on a hypercube ===
A [http://en.wikipedia.org/wiki/Hypercube hypercube] (sometimes called a Boolean cube, a Hamming cube, or just cube) is defined over <math>N</math> nodes, for <math>N</math> a power of 2. We assume that <math>N=2^d</math>. A hypercube of <math>d</math> dimensions, or a <math>d</math>-cube, is an undirected graph with the vertex set <math>\{0,1\}^d</math>, such that for any <math>u,v\in\{0,1\}^d</math>, <math>u</math> and <math>v</math> are adjacent if and only if <math>h(u,v)=1</math>, where <math>h(u,v)</math> is the [http://en.wikipedia.org/wiki/Hamming_distance Hamming distance] between <math>u</math> and <math>v</math>.

A <math>d</math>-cube is a <math>d</math>-degree regular graph over <math>N=2^d</math> vertices. For any pair <math>(u,v)</math> of vertices, the distance between <math>u</math> and <math>v</math> is at most <math>d</math>. (How do we know this? Since it takes at most <math>d</math> steps to fix any binary string of length <math>d</math> bit-by-bit to any other.) This directly gives us the following very natural routing algorithm.

{|border="1"
|'''Bit-Fixing Routing Algorithm:'''
|-
|For each packet:
#Let <math>u, v\in\{0,1\}^d</math> be the origin and destination of the packet respectively.
#For <math>i=1</math> to <math>d</math>, do:
::if <math>u_i\neq v_i</math> then traverse the edge <math>(v_1,\ldots,v_{i-1},u_i,\ldots,u_d)\rightarrow (v_1,\ldots,v_{i-1},v_i,u_{i+1}\ldots,u_d)</math>.
|}

;Oblivious routing algorithms
:This algorithm is blessed with a desirable property: it depends only on the origin, the destination, and the current node. We call the algorithms with this property '''oblivious''' routing algorithms. Compared to the routing algorithms which are adaptive to the path that the packet traversed, oblivious routing is more simple thus can be implemented by smaller routing table (or simple devices called '''switches''').

;Queuing policies
:When routing <math>N</math> packets in parallel, it is possible that more than one packets want to use the same edge at the same time. We assume that a queue is associated to each edge, such that the packets to be delivered through an edge are put into the queue associated with the edge. With some '''queuing policy''' (e.g. FIFO, or furthest to do), the queued packets are delivered through the edge by at most one packet per each round.

For the bit-fixing routing algorithm defined above, regardless of the queuing policy, there always exists a bad permutation <math>\pi</math> which specifies the destinations, such that it takes <math>\Omega(\sqrt{N})</math> steps by the bit-fixing algorithm to route all <math>N</math> packets to their destinations. (You can prove this by yourself.)

This is pretty bad, because we expect that the routing time is comparable to the diameter of the network, which is only <math>d=\log N</math> for hypercube.

The lower bound actually applies generally for any deterministic oblivious routing algorithms:

{|border="1"
|'''Theorem [Kaklamanis, Krizanc, Tsantilas, 1991]'''
:In any <math>N</math>-node communication network with maximum degree <math>d</math>, any deterministic oblivious algorithm for routing an arbitrary permutation requires <math>\Omega(\sqrt{N}/d)</math> parallel communication steps in the worst case.
|}

The proof of the lower bound is rather technical and complicated. However, the intuition is quite clear: for any oblivious rule for routing, there always exists a permutation which causes a very high '''congestion''', such that many packets have to be delivered through the same edge, thus no matter what queuing policy is used, the maximum delay must be very high.

=== A two-phase randomized routing algorithm ===

{|border="1"
|'''Two-Phase Routing Algorithm:'''
|-
|For each packet:
'''Phase I:''' Route the packet to a random destination using the bit-fixing algorithm.

'''Phase II:''' Route the packet from the random location to its final destination using the bit-fixing algorithm.
|}

== Johnson-Lindenstrauss Theorem ==

Randomized Algorithms (Spring 2010)/More on Chernoff bounds

2010-02-25T14:48:06Z

172.21.5.128: /* A two-phase randomized routing algorithm */

== 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.

=== Routing on a hypercube ===
A [http://en.wikipedia.org/wiki/Hypercube hypercube] (sometimes called a Boolean cube, a Hamming cube, or just cube) is defined over <math>N</math> nodes, for <math>N</math> a power of 2. We assume that <math>N=2^d</math>. A hypercube of <math>d</math> dimensions, or a <math>d</math>-cube, is an undirected graph with the vertex set <math>\{0,1\}^d</math>, such that for any <math>u,v\in\{0,1\}^d</math>, <math>u</math> and <math>v</math> are adjacent if and only if <math>h(u,v)=1</math>, where <math>h(u,v)</math> is the [http://en.wikipedia.org/wiki/Hamming_distance Hamming distance] between <math>u</math> and <math>v</math>.

A <math>d</math>-cube is a <math>d</math>-degree regular graph over <math>N=2^d</math> vertices. For any pair <math>(u,v)</math> of vertices, the distance between <math>u</math> and <math>v</math> is at most <math>d</math>. (How do we know this? Since it takes at most <math>d</math> steps to fix any binary string of length <math>d</math> bit-by-bit to any other.) This directly gives us the following very natural routing algorithm.

{|border="1"
|'''Bit-Fixing Routing Algorithm:'''
|-
|For each packet:
#Let <math>u, v\in\{0,1\}^d</math> be the origin and destination of the packet respectively.
#For <math>i=1</math> to <math>d</math>, do:
::if <math>u_i\neq v_i</math> then traverse the edge <math>(v_1,\ldots,v_{i-1},u_i,\ldots,u_d)\rightarrow (v_1,\ldots,v_{i-1},v_i,u_{i+1}\ldots,u_d)</math>.
|}

;Oblivious routing algorithms
:This algorithm is blessed with a desirable property: it depends only on the origin, the destination, and the current node. We call the algorithms with this property '''oblivious''' routing algorithms. Compared to the routing algorithms which are adaptive to the path that the packet traversed, oblivious routing is more simple thus can be implemented by smaller routing table (or simple devices called '''switches''').

;Queuing policies
:When routing <math>N</math> packets in parallel, it is possible that more than one packets want to use the same edge at the same time. We assume that a queue is associated to each edge, such that the packets to be delivered through an edge are put into the queue associated with the edge. With some '''queuing policy''' (e.g. FIFO, or furthest to do), the queued packets are delivered through the edge by at most one packet per each round.

For the bit-fixing routing algorithm defined above, regardless of the queuing policy, there always exists a bad permutation <math>\pi</math> which specifies the destinations, such that it takes <math>\Omega(\sqrt{N})</math> steps by the bit-fixing algorithm to route all <math>N</math> packets to their destinations. (You can prove this by yourself.)

This is pretty bad, because we expect that the routing time is comparable to the diameter of the network, which is only <math>d=\log N</math> for hypercube.

The lower bound actually applies generally for any deterministic oblivious routing algorithms:

{|border="1"
|'''Theorem [Kaklamanis, Krizanc, Tsantilas, 1991]'''
:In any <math>N</math>-node communication network with maximum degree <math>d</math>, any deterministic oblivious algorithm for routing an arbitrary permutation requires <math>\Omega(\sqrt{N}/d)</math> parallel communication steps in the worst case.
|}

The proof of the lower bound is rather technical and complicated. However, the intuition is quite clear: for any oblivious rule for routing, there always exists a permutation which causes a very high '''congestion''', such that many packets have to be delivered through the same edge, thus no matter what queuing policy is used, the maximum delay must be very high.

=== A two-phase randomized routing algorithm ===

{|border="1"
|'''Two-Phase Routing Algorithm:'''
|-
|'''Phase I:''' Route the packet to a random destination using the bit-fixing algorithm.
'''Phase II:''' Route the packet from the random location to its final destination using the bit-fixing algorithm.
|}

== Johnson-Lindenstrauss Theorem ==

Randomized Algorithms (Spring 2010)/More on Chernoff bounds

2010-02-25T14:47:26Z

172.21.5.128: /* A two-phase randomized routing algorithm */

== 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.

=== Routing on a hypercube ===
A [http://en.wikipedia.org/wiki/Hypercube hypercube] (sometimes called a Boolean cube, a Hamming cube, or just cube) is defined over <math>N</math> nodes, for <math>N</math> a power of 2. We assume that <math>N=2^d</math>. A hypercube of <math>d</math> dimensions, or a <math>d</math>-cube, is an undirected graph with the vertex set <math>\{0,1\}^d</math>, such that for any <math>u,v\in\{0,1\}^d</math>, <math>u</math> and <math>v</math> are adjacent if and only if <math>h(u,v)=1</math>, where <math>h(u,v)</math> is the [http://en.wikipedia.org/wiki/Hamming_distance Hamming distance] between <math>u</math> and <math>v</math>.

A <math>d</math>-cube is a <math>d</math>-degree regular graph over <math>N=2^d</math> vertices. For any pair <math>(u,v)</math> of vertices, the distance between <math>u</math> and <math>v</math> is at most <math>d</math>. (How do we know this? Since it takes at most <math>d</math> steps to fix any binary string of length <math>d</math> bit-by-bit to any other.) This directly gives us the following very natural routing algorithm.

{|border="1"
|'''Bit-Fixing Routing Algorithm:'''
|-
|For each packet:
#Let <math>u, v\in\{0,1\}^d</math> be the origin and destination of the packet respectively.
#For <math>i=1</math> to <math>d</math>, do:
::if <math>u_i\neq v_i</math> then traverse the edge <math>(v_1,\ldots,v_{i-1},u_i,\ldots,u_d)\rightarrow (v_1,\ldots,v_{i-1},v_i,u_{i+1}\ldots,u_d)</math>.
|}

;Oblivious routing algorithms
:This algorithm is blessed with a desirable property: it depends only on the origin, the destination, and the current node. We call the algorithms with this property '''oblivious''' routing algorithms. Compared to the routing algorithms which are adaptive to the path that the packet traversed, oblivious routing is more simple thus can be implemented by smaller routing table (or simple devices called '''switches''').

;Queuing policies
:When routing <math>N</math> packets in parallel, it is possible that more than one packets want to use the same edge at the same time. We assume that a queue is associated to each edge, such that the packets to be delivered through an edge are put into the queue associated with the edge. With some '''queuing policy''' (e.g. FIFO, or furthest to do), the queued packets are delivered through the edge by at most one packet per each round.

For the bit-fixing routing algorithm defined above, regardless of the queuing policy, there always exists a bad permutation <math>\pi</math> which specifies the destinations, such that it takes <math>\Omega(\sqrt{N})</math> steps by the bit-fixing algorithm to route all <math>N</math> packets to their destinations. (You can prove this by yourself.)

This is pretty bad, because we expect that the routing time is comparable to the diameter of the network, which is only <math>d=\log N</math> for hypercube.

The lower bound actually applies generally for any deterministic oblivious routing algorithms:

{|border="1"
|'''Theorem [Kaklamanis, Krizanc, Tsantilas, 1991]'''
:In any <math>N</math>-node communication network with maximum degree <math>d</math>, any deterministic oblivious algorithm for routing an arbitrary permutation requires <math>\Omega(\sqrt{N}/d)</math> parallel communication steps in the worst case.
|}

The proof of the lower bound is rather technical and complicated. However, the intuition is quite clear: for any oblivious rule for routing, there always exists a permutation which causes a very high '''congestion''', such that many packets have to be delivered through the same edge, thus no matter what queuing policy is used, the maximum delay must be very high.

=== A two-phase randomized routing algorithm ===

{|border="1"
|'''Two-Phase Routing Algorithm:'''
|-
|'''Phase I:''' Route the packet to a uniformly random destination using the bit-fixing algorithm.
'''Phase II:''' Route the packet from the random location to its final destination using the bit-fixing algorithm.
|}

== Johnson-Lindenstrauss Theorem ==

Randomized Algorithms (Spring 2010)/More on Chernoff bounds

2010-02-25T14:40:12Z

172.21.5.128: /* Routing on a hypercube */

Randomized Algorithms (Spring 2010)/More on Chernoff bounds

2010-02-25T14:38:57Z

172.21.5.128: /* Routing on a hypercube */

Randomized Algorithms (Spring 2010)/More on Chernoff bounds

2010-02-25T14:32:38Z

172.21.5.128: /* 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.

=== Routing on a hypercube ===
A [http://en.wikipedia.org/wiki/Hypercube hypercube] (sometimes called a Boolean cube, a Hamming cube, or just cube) is defined over <math>N</math> nodes, for <math>N</math> a power of 2. We assume that <math>N=2^d</math>. A hypercube of <math>d</math> dimensions, or a <math>d</math>-cube, is an undirected graph with the vertex set <math>\{0,1\}^d</math>, such that for any <math>u,v\in\{0,1\}^d</math>, <math>u</math> and <math>v</math> are adjacent if and only if <math>h(u,v)=1</math>, where <math>h(u,v)</math> is the [http://en.wikipedia.org/wiki/Hamming_distance Hamming distance] between <math>u</math> and <math>v</math>.

A <math>d</math>-cube is a <math>d</math>-degree regular graph over <math>N=2^d</math> vertices. For any pair <math>(u,v)</math> of vertices, the distance between <math>u</math> and <math>v</math> is at most <math>d</math>. (How do we know this? Since it takes at most <math>d</math> steps to fix any binary string of length <math>d</math> bit-by-bit to any other.) This directly gives us the following very natural routing algorithm.

{|border="1"
|'''Bit-Fixing Routing Algorithm:'''
|-
|For each packet:
#Let <math>u, v\in\{0,1\}^d</math> be the origin and destination of the packet respectively.
#For <math>i=1</math> to <math>d</math>, do:
::if <math>u_i\neq v_i</math> then traverse the edge <math>(v_1,\ldots,v_{i-1},u_i,\ldots,u_d)\rightarrow (v_1,\ldots,v_{i-1},v_i,u_{i+1}\ldots,u_d)</math>.
|}

;Oblivious routing algorithms
:This algorithm is blessed with a desirable property: it depends only on the origin, the destination, and the current node. We call the algorithms with this property '''oblivious''' routing algorithms. Compared to the routing algorithms which are adaptive to the path that the packet traversed, oblivious routing is more simple thus can be implemented by smaller routing table (or simple devices called '''switches''').

;Queuing policies
:When routing <math>N</math> packets in parallel, it is possible that more than one packets want to use the same edge at the same time. We assume that a queue is associated to each edge, such that the packets to be delivered through an edge are put into the queue associated with the edge. With some '''queuing policy''' (e.g. FIFO, or furthest to do), the queued packets are delivered through the edge by at most one packet per each round.

For the bit-fixing routing algorithm defined above, regardless of the queuing policy, there always exists a bad permutation <math>\pi</math> which specifies the destinations, such that it takes <math>\Omega(\sqrt{N})</math> steps by the bit-fixing algorithm to route all <math>N</math> packets to their destinations. (You can prove this by yourself.)

The lower bound actually applies generally for any deterministic oblivious routing algorithms:

{|border="1"
|'''Theorem [Kaklamanis, Krizanc, Tsantilas, 1991]'''
:In any <math>N</math>-node communication network with maximum degree <math>d</math>, any deterministic oblivious algorithm for routing an arbitrary permutation requires <math>\Omega(\sqrt{N}/d)</math> parallel communication steps in the worst case.
|}

This is pretty bad, because we expect that the routing time is comparable to the diameter of the network, which is only <math>d=\log N</math> for hypercube.

== Johnson-Lindenstrauss Theorem ==