  Counters are an important abstraction in distributed computing, and play a
central role in large scale geo-replicated systems, counting events such as web
page impressions or social network "likes". Classic distributed counters,
strongly consistent, cannot be made both available and partition-tolerant, due
to the CAP Theorem, being unsuitable to large scale scenarios. This paper
defines Eventually Consistent Distributed Counters (ECDC) and presents an
implementation of the concept, Handoff Counters, that is scalable and works
over unreliable networks. By giving up the sequencer aspect of classic
distributed counters, ECDC implementations can be made AP in the CAP design
space, while retaining the essence of counting. Handoff Counters are the first
CRDT (Conflict-free Replicated Data Type) based mechanism that overcomes the
identity explosion problem in naive CRDTs, such as G-Counters (where state size
is linear in the number of independent actors that ever incremented the
counter), by managing identities towards avoiding global propagation and
garbage collecting temporary entries. The approach used in Handoff Counters is
not restricted to counters, being more generally applicable to other data types
with associative and commutative operations.

Distributed, Parallel, and Cluster Computing