Internet protocol for distributed averaging

Abstract

The scheme of the invention addresses practical concerns that arise in actual implementations on packet-switched communication networks such as the Internet. The system includes several implementable algorithms that are robust to asynchronism and dynamic topology changes. The algorithms are distributed and do not require any global coordination. In addition, they can be proven to converge under very general asynchronous timing assumptions. The system of the invention provides a distributed protocol for averaging the values of several real numbers associated with members of a peer-to-peer network. The system implements a pair-wise communication protocol between nodes with each node having a state value that is incrementally driven to the average of the distributed values. At each node, received state values from neighboring nodes, along with local step-wise values, are used to update the local state value. Embodiments include schemes to allow ordered processing in an asynchronous environment and to prevent message deadlock.

Dependencies are inferred from the claim text.