Count tracking in distributed environments is described, for example, as in data centers where many sites receive data and a coordinator node estimates a sum of the data received across the sites. Count tracking may be used in database applications, search engines, social networking applications and others. In various embodiments sites and a coordinator node work together to implement a process for summing data received at sites, where the sum takes into account both increments and decrements. In examples, a site decides whether to notify the coordinator node of a new data item according to a sampling probability that is related to an estimate of the current global sum of the data input across sites. In some examples a multi-mode algorithm is implemented which increases or decreases communication between the sites and the coordinator node according to behavior of the estimated global sum such that communications costs are optimized.