3
$\begingroup$

I have a proof that I need help with. Like the title says, the theorem is that every bit-reversal ring is $\frac{1}{2}$-symmetric. The theorem is for Leader Election algorithm in synchronous ring. The things I know follow:

Bit reversal ring is defined as follows: We assign to each process $i$ the integer from ${0,\ldots, n-1}$ whose $k$ bit representation is the reverse of the $k$ bit representation of $i$. $n$ is also a power of two, $n=2^{k}$.

Two segments $U$ and $V$ are order equivalent if they are the same length $k$, and for all $i$ and $j$ such that $1 \leq i,j \leq k$ we have that $u_{i} \leq u_{j}$ if and only if $v_{i} \leq v_{j}$.

Ring $R$ is $c$-symmetric if for every segment $S$ of $R$ there are at least $\lfloor \frac{cn}{l} \rfloor$ segments that are order equivalent to $S$, including $S$ itself, where $l$ is length of the segment, and this holds for every $\sqrt{n} \leq l \leq n$.

So after plugging all I know into formulas I get that $\lfloor \frac{2^{k-1}}{l} \rfloor$ is formula for number of segments and $l$ is such that $2^{\frac{k}{2}} \leq l \leq 2^{k}$.

Any hint or piece of information would be much appreciated! Thank you.

$\endgroup$

1 Answer 1

3
$\begingroup$

We will prove your formula for all $\ell$, with a bound of $\lceil \frac{n/2}{\ell} \rceil$. We can assume that $\ell < n/2$, since otherwise $\lceil \frac{n/2}{\ell} \rceil = 1$, and there is nothing to prove. Also, if $n = 1$ then the result is trivial, so we can assume that $n \geq 2$.

The relative order of elements in the interval of length $n/2$ starting at $i$ is the same as the relative order of elements in the ring of length $n/2$, when read from position $i$. For example, here are all intervals of length $4$ in the ring of length $8$, and the corresponding intervals in the ring of length $4$: \begin{align} &0,4,2,6 & 0,2,1,3 \\ &4,2,6,1 & 2,1,3,0 \\ &2,6,1,5 & 1,3,0,2 \\ &6,1,5,3 & 3,0,2,1 \\ &1,5,3,7 & 0,2,1,3 \\ &5,3,7,0 & 2,1,3,0 \\ &3,7,0,4 & 1,3,0,2 \\ &7,0,4,2 & 3,0,2,1 \end{align} To see this, note first that each interval on the left doesn't contain a pair of elements which differ only in their LSB. Therefore, we can ignore the LSB of all elements on the left. One way to do it is to divide all elements on the left by two. This results in the intervals on the right.

This property immediately implies a similar property for all intervals of length $\ell \leq n/2$: the relative order of elements in the interval of length $\ell$ starting at $i$ is the same as the relative order of elements in the interval of length $\ell$ starting at $i \bmod (n/2)$ in the ring of length $n/2$. This implies (by induction) that an interval of length $\ell \leq n/2$ has at least this many order-equivalent intervals: $2\lceil \frac{n/4}{\ell} \rceil \geq \lceil \frac{n/2}{\ell} \rceil$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.