We will need the following lemma on the minimum distance from the mobile relays to the destination at any time slot. Fix a bit b that enters into the system at time slot t ₀ ( b). At each time slot t ? t ₀( b), recall that r _b( t) is the number of mobile relays holding the bit b at the beginning of the time slot. Among these r _b( t) mobile relays, there is one mobile relay whose distance to the destination of bit b is the smallest. Let denote this minimum distance, and let

It is easy to verify that

Lemma A.1

Under the i.i.d. mobility model, if n ? 3, then

Proof: Let I _A be the indicator function on the set A. By the definition of L _b( t), we have,

Since the nodes move on a unit square, . Hence,

Hence,

Let ? _b be the distance from any one mobile node to the destination of the bit b. Then, due to the i.i.d. mobility model, we have,

and,

Therefore,

when n ? 3. Finally, since r _b( t) is _{t -1}-measurable, we have

Q.E.D.

Proof of Proposition 2.1 : Let

Then for all t ? t ₀( b), V _t is also _t-measurable and . By Lemma...