  Motivated by the need for robust and fast distributed computation in highly
dynamic Peer-to-Peer (P2P) networks, we study algorithms for the fundamental
distributed agreement problem. P2P networks are highly dynamic networks that
experience heavy node {\em churn}. Our goal is to design fast algorithms
(running in a small number of rounds) that guarantee, despite high node churn
rate, that almost all nodes reach a stable agreement. Our main contributions
are randomized distributed algorithms that guarantee {\em stable
almost-everywhere agreement} with high probability even under high adversarial
churn in a polylogarithmic number of rounds:
  1. An $O(\log^2 n)$-round ($n$ is the stable network size) randomized
algorithm that achieves almost-everywhere agreement with high probability under
up to {\em linear} churn {\em per round} (i.e., $\epsilon n$, for some small
constant $\epsilon > 0$), assuming that the churn is controlled by an oblivious
adversary (that has complete knowledge and control of what nodes join and leave
and at what time and has unlimited computational power, but is oblivious to the
random choices made by the algorithm). Our algorithm requires only
polylogarithmic in $n$ bits to be processed and sent (per round) by each node.
  2. An $O(\log m\log^3 n)$-round randomized algorithm that achieves
almost-everywhere agreement with high probability under up to $\epsilon
\sqrt{n}$ churn per round (for some small $\epsilon > 0$), where $m$ is the
size of the input value domain, that works even under an adaptive adversary
(that also knows the past random choices made by the algorithm). This algorithm
requires up to polynomial in $n$ bits (and up to $O(\log m)$ bits) to be
processed and sent (per round) by each node.
