LOT: Fast, Efficient and Robust In-Network Computation
André Allavena, Srinivasan Keshav · 2006
algorithms, tree abstraction. Today, companies such as eBay, Amazon, Google, and IBM routinely operate clusters with more than 10,000 servers located in data centres around the world. Developing applications that efficiently use the resources of such a distributed cluster is challenging. This task is made eased by a middleware layer that provides application programmers with the illusion of dynamically updated "global state". Maintaining global state can be viewed as repeatedly computing an arbitrary function over a set of time-varying values, where the values are held at each node, and every node needs to know the resultant function. Many well-known problems in distributed systems, such as load balancing, leader election, barrier synchronisation, distributed file system maintenance, and coordinated intrusion detection can be cast in this form. We present and rigorously analyse an algorithm that uses a a tree of virtual nodes to compute nearly arbitrary functions of global state. Our scheme is fast: running time is Θ(lnn). It is efficient: nodes exchange O(n lnn) messages. Most of these messages are within a data centre and therefore are relatively cheap. It is accurate: the computed value does not have inherent errors either due to double-counting, as with standard gossip, or due to stochastic counting, as in the Flajolet-Martin approach. Finally, it is fault tolerant: The algorithm fails with probability