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.