<p>Suppose your graph was a path.  I think then this problem becomes equivalent to sorting a random sequence of numbers in an array by swapping adjacent entries.  Even of all nodes are topology aware, you get a n^2 lower bound on the number of swaps (cannot do better than bubble sort which is n^2 even on a random input).</p>

CC BY-SA 2.5
2010-08-19T09:20:59.817Z
Yes, we need a minimum degree :(
Sylvain Peyronnet
CC BY-SA 2.5
2010-08-18T17:27:48.133Z
In the case of a path, the process of swapping with probability 1/2 mixes in $O(n^2)$, this has been proven by Benjamini, Berger and Hoffman (this was conjectured by Diaconis and Ram). So my LB is also a function of the degree I guess...
Sylvain Peyronnet
CC BY-SA 2.5
2010-08-18T17:37:05.063Z
This LB says you can't improve the algorithm even if you can choose your swaps.... but right, I guess the problem might get easier as the (average?) degree goes up.
Lev Reyzin
CC BY-SA 2.5
2010-08-18T17:38:33.843Z
I will schedule some simulations to see how thing goes when the degree is growing.
Sylvain Peyronnet
CC BY-SA 2.5
2010-08-18T17:39:57.710Z
Actually it looks like this LB (with some modification) will hold even if the two ends of the path have large cliques -- as in 2 cliques on n/4 connected by a path of n/2 nodes.  Now the average degree is O(n), yet you still can't beat n^2.

Perhaps we need to impose a minimum degree?
Lev Reyzin
CC BY-SA 2.5
2010-08-18T17:13:58.813Z
2010-08-18T17:13:58.813Z
Lev Reyzin
<p>I'd like to point out the relation between this problem and sorting networks. For example, if your graph is a path, then the trivial <a href="http://en.wikipedia.org/wiki/File%3aSix-wire-pyramid-sorting-network.svg" rel="noreferrer">linear-depth sorting network</a> also shows that you can obtain any permutation in linear number of rounds. Moreover, this is tight, as simply interchanging the elements at the endpoints of the path requires a linear number of rounds.</p>

<p>AKS sorting networks show that there are graphs in which you can obtain any permutation in logarithmic number of rounds. For the case of grid graphs, see e.g. <a href="http://dcg.ethz.ch/lectures/fs10/podc/lecture/sorting.pdf" rel="noreferrer">these lecture notes</a>.</p>

<p>(Of course sorting and shuffling are different problems, but many upper and lower bounds are related. E.g., pick random labels and sort by labels.)</p>

CC BY-SA 2.5
2010-08-18T20:26:03.200Z
Thanks for the pointer. I will dig in this direction, maybe it is not what I need here (I am not sure whether I have the good type of graph) but it certainly will be something I will use sooner or later !
Sylvain Peyronnet
CC BY-SA 2.5
2010-08-18T19:42:30.323Z
2010-08-18T19:42:30.323Z
Jukka Suomela
<p>Let $G= (V, E)$ be a non-regular connected graph whose degree is bounded. Suppose that each node contain a unique token.</p>

<p>I want to uniformly shuffle the tokens amongst the graph using only local swaps (i.e. exchange of the tokens between two adjacent nodes) ? Is there a lower bound known for this problem ?</p>

<p>The only idea I had is to use a random walk result, then to see how much swaps I need to "simulate" the effect of random walks transporting tokens on the graph.</p>

CC BY-SA 2.5
2010-08-18T11:39:54.677Z
What kind of lower bound you are looking for? Total number of swaps? Number of parallel rounds (i.e., in 1 step you can swap along all edges of a matching in $G$)? Lower bound as a function of $|V|$, $diam(G)$? Do all the nodes know the topology of $G$ (and can adapt their behaviour accordingly), or are you looking for a fixed strategy that you can apply in any graph?
Jukka Suomela
CC BY-SA 2.5
2010-08-18T12:54:25.137Z
I should have been more specific, sorry.

The goal is to design a data dissemination method for sensor networks that avoid problems of random walks based methods (essentially loss of information due to several tokens colliding at the same node). So I am interested in the total number of swaps (this will give the number of messages circulating in the network) and the number of rounds (to have a rough estimate of the convergence time).

a LB as a function of $V$ is fine and nodes are not topology aware (unfortunately).
Sylvain Peyronnet
<ds.algorithms><random-walks><dc.distributed-comp>
Shuffling of tokens on a graph using local swaps
Sylvain Peyronnet
# Shuffling of tokens on a graph using local swaps

(Asked by: username_0 on 2010-08-18)

Let $G= (V, E)$ be a non-regular connected graph whose degree is bounded. Suppose that each node contain a unique token.

I want to uniformly shuffle the tokens amongst the graph using only local swaps (i.e. exchange of the tokens between two adjacent nodes) ? Is there a lower bound known for this problem ?

The only idea I had is to use a random walk result, then to see how much swaps I need to "simulate" the effect of random walks transporting tokens on the graph.

**Tags:** ds.algorithms, random-walks, dc.distributed-comp

> **Comments:**
> **username_1**: What kind of lower bound you are looking for? Total number of swaps? Number of parallel rounds (i.e., in 1 step you can swap along all edges of a matching in $G$)? Lower bound as a function of $|V|$, $diam(G)$? Do all the nodes know the topology of $G$ (and can adapt their behaviour accordingly), or are you looking for a fixed strategy that you can apply in any graph?  
> **username_0**: I should have been more specific, sorry.  The goal is to design a data dissemination method for sensor networks that avoid problems of random walks based methods (essentially loss of information due to several tokens colliding at the same node). So I am interested in the total number of swaps (this will give the number of messages circulating in the network) and the number of rounds (to have a rough estimate of the convergence time).  a LB as a function of $V$ is fine and nodes are not topology aware (unfortunately).  

---

## 2 answers

### Answer by username_2 on 2010-08-18. Score: 5 | Accepted answer

Suppose your graph was a path. I think then this problem becomes equivalent to sorting a random sequence of numbers in an array by swapping adjacent entries. Even of all nodes are topology aware, you get a n^2 lower bound on the number of swaps (cannot do better than bubble sort which is n^2 even on a random input).

> **Comments:**
> **username_0**: In the case of a path, the process of swapping with probability 1/2 mixes in $O(n^2)$, this has been proven by Benjamini, Berger and Hoffman (this was conjectured by Diaconis and Ram). So my LB is also a function of the degree I guess...  
> **username_2**: This LB says you can't improve the algorithm even if you can choose your swaps.... but right, I guess the problem might get easier as the (average?) degree goes up.  
> **username_0**: I will schedule some simulations to see how thing goes when the degree is growing.  
> **username_2**: Actually it looks like this LB (with some modification) will hold even if the two ends of the path have large cliques -- as in 2 cliques on n/4 connected by a path of n/2 nodes.  Now the average degree is O(n), yet you still can't beat n^2.  Perhaps we need to impose a minimum degree?  
> **username_0**: Yes, we need a minimum degree :(  

---

### Answer by username_1 on 2010-08-18. Score: 5

I'd like to point out the relation between this problem and sorting networks. For example, if your graph is a path, then the trivial [linear-depth sorting network](http://en.wikipedia.org/wiki/File%3aSix-wire-pyramid-sorting-network.svg) also shows that you can obtain any permutation in linear number of rounds. Moreover, this is tight, as simply interchanging the elements at the endpoints of the path requires a linear number of rounds.

AKS sorting networks show that there are graphs in which you can obtain any permutation in logarithmic number of rounds. For the case of grid graphs, see e.g. [these lecture notes](http://dcg.ethz.ch/lectures/fs10/podc/lecture/sorting.pdf).

(Of course sorting and shuffling are different problems, but many upper and lower bounds are related. E.g., pick random labels and sort by labels.)

> **Comments:**
> **username_0**: Thanks for the pointer. I will dig in this direction, maybe it is not what I need here (I am not sure whether I have the good type of graph) but it certainly will be something I will use sooner or later !  

---

