Internet protocol for distributed averaging

摘要

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.

主权项

1. A method of distributed averaging on a network having a plurality of nodes in excess of two, comprising:
generating a state message at a sending node of the network having a plurality of nodes in excess of two, said state message having a single sending node state value and sending the state message to a receiving node of the network, and only the receiving node; generating a modified value at the receiving node by multiplying the difference of the single sending node state value and a receiving node state value by a receiving node step-wise value; updating the receiving node state value using the modified value; and sending the modified value from the receiving node to the sending node, and only the sending node, in a reply message.