# ICS 269, Spring 2005: Theory Seminar

## 3 June 2005:

Location: PSCB 230

Speaker: Jonathan Sun

This talk will be a presentation of
a paper titled
"How to spread adversarial nodes? rotate!"
by Christian Scheideler. It appeared in STOC 2005.

Abstract: This paper studies the following game played by a System and
an Adversary. System maintains a Ring of n white pebbles which is
fully accessible to Adversary. Adversary has limited amount (less than
n) of black pebbles. At each step, Adversary inserts or withdraws a
black pebble into/from the Ring, but System then somehow rearranges
the ring to distribute black pebbles as uniformly as possible.
Adversary's goal is to introduce a segment in Ring of length O(log n)
with more than half of the pebbles being black, in polynomial time.
System's goal is to, with high probability, prevent this from
happening with little work of rearrangement. The paper studies a
simple strategy of System and provides interesting results. It has
application in making robust peer-to-peer networks.

After Adversary inserts a black pebble to a position, System randomly
select another k positions (k-1 pebbles plus one new position) and
rotate the k pebbles within the k+1 positions. When k=2, Adversary
wins with only O(log n) black pebbles. When k=3, System wins even if
Adversary has n/3 black pebbles.