  We introduce a new class of distributed algorithms for the approximate
consensus problem in dynamic rooted networks, which we call amortized averaging
algorithms. They are deduced from ordinary averaging algorithms by adding a
value-gathering phase before each value update. This allows their decision time
to drop from being exponential in the number $n$ of processes to being linear
under the assumption that each process knows $n$. In particular, the amortized
midpoint algorithm, which achieves a linear decision time, works in completely
anonymous dynamic rooted networks where processes can exchange and store
continuous values, and under the assumption that the number of processes is
known to all processes. We then study the way amortized averaging algorithms
degrade when communication graphs are from time to time non rooted, or with a
wrong estimate of the number of processes. Finally, we analyze the amortized
midpoint algorithm under the additional constraint that processes can only
store and send quantized values, and get as a corollary that the 2-set
consensus problem is solvable in linear time in any rooted dynamic network
model when allowing all decision values to be in the range of initial values.
