  This paper shows for the first time that distributed computing can be both
reliable and efficient in an environment that is both highly dynamic and
hostile. More specifically, we show how to maintain clusters of size $O(\log
N)$, each containing more than two thirds of honest nodes with high
probability, within a system whose size can vary \textit{polynomially} with
respect to its initial size. Furthermore, the communication cost induced by
each node arrival or departure is polylogarithmic with respect to $N$, the
maximal size of the system. Our clustering can be achieved despite the presence
of a Byzantine adversary controlling a fraction $\bad \leq \{1}{3}-\epsilon$ of
the nodes, for some fixed constant $\epsilon > 0$, independent of $N$. So far,
such a clustering could only be performed for systems who size can vary
constantly and it was not clear whether that was at all possible for polynomial
variances.
