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.

Description:
[0001]     The present application claims the benefit of priority from pending U.S. Provisional Patent Application No. 60/605,236, entitled “Protocol For Distributed Averaging”, filed on Aug. 24, 2004, which is herein incorporated by reference in its entirety 
     
    
     BACKGROUND OF THE INVENTION  
       [0002]     1. Field of the Invention  
         [0003]     This invention relates to the field of an internet protocol for distributed averaging.  
         [0004]     2. Background Art  
         [0005]     Distributed averaging problems are problems in which several spatially separated processes (or agents) must reach some common output value (a classical example is the Byzantine generals problem). There have been attempts to calculate averages on asynchronous distributed networks. One technique is to flood the network with all values. This approach results in large messaging complexity. Another is to use structured message propagation over a known overlay network, which is not always available. Both approaches require a global exchange of information, adding to complexity.  
       SUMMARY OF THE INVENTION  
       [0006]     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.  
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0007]      FIG. 1  is a flow diagram illustrating the update procedure between two nodes on a network.  
         [0008]      FIG. 2  is a flow diagram illustrating pair wise messaging with blocking.  
         [0009]      FIG. 3  is a flow diagram illustrating an embodiment of the invention.  
         [0010]      FIG. 4  is an example network topology in an embodiment of the invention.  
         [0011]      FIG. 5  is an embedded view of the network topology of  FIG. 4 .  
         [0012]      FIG. 6  is a flow diagram illustrating the round robin scheme of an embodiment of the invention.  
     
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS  
       [0013]     A protocol for distributed averaging is described. In the following description, numerous specific details are set forth in order to provide a more detailed description of the invention. In other instances, well known features have not been described in detail so as not to obscure the invention. It is understood to one of skill in the art, that the invention may be practiced without these specific details.  
         [0014]     The prior art has considered averaging problems, for example Olfati-Saber and Murray in “Consensus Problems in Networks of Agents with Switching Topology and Time-Delays”,  IEEE Trans. on Automatic Control , VOL. 49, NO. 9, September 2004. This work focuses on a special matrix, the Laplacian matrix, associated with an undirected graph G. Note that the adjacency matrix A, associated with a graph, is a matrix with a 1 in the i,j entry if and only if the graph includes the edge ij, and is zero elsewhere. The Laplacian is defined in terms of the adjacency matrix as follows:  
               D   ii     =       ∑   j     ⁢     A   ij                     D   ii     =       0   ⁢           ⁢   if   ⁢           ⁢   i     ≠   j                 L   =     D   -   A               
 
         [0015]     This is known as the Laplacian matrix because it represents a discrete version of the classical Laplacian differential operator ∇ 2  arising in diffusion processes. The prior art of Olfati-Saber and Murray proposes the following differential equation as a mechanism for averaging: 
 
 x=−Lx   (1) 
 
         [0016]     First, note that this is a distributed “algorithm”, in the sense that each member of the network need only communicate with its neighbors. Second, note that Σ j L ij =0 for all i, and so for any “consensus vector” x c , i.e. a vector in which all components are equal, Lx c =0. It can in fact be shown that consensus is the only equilibrium of the above differential equation, provided the graph G is connected. Finally, note that by this same property, we have the following conservation property:  
         ⅆ     ⅆ   t       ⁢       ∑   i     ⁢       x   i     ⁢   0           
 
         [0017]     These facts suffice to explain the Laplacian algorithm (1); the differential equation must converge to a consensus, and the sum of the initial states is conserved, so each component (in equilibrium) must equal the average of the initial values.  
         [0018]     Other authors have also considered similar problems. Recently, L. Xiao and S. Boyd, “Fast Linear Interactions for Distributed Averaging”,  Proceedings of The Conference on Decision and Control,  2003 examined the possibility of topology optimization for maximizing the convergence rate of the algorithm. The work in A. Fax and R. M. Murray, “ Graph Laplacians and Stabilization of Vehicle Formations ”, The 15 th  IFAC World Congress 2002 considered a very similar algorithm for distributed center-of-mass estimation in control of vehicle formations.  
         [0019]     Unfortunately, all of these results share the drawback of not being directly implementable on a real network. Clearly, a differential equation is not implementable, but even the associated discrete-time system, 
 
 x ( t+ 1)= x ( t )−λ Lx ( t ) 
 
 (here γ is a stepsize parameter) is problematic. At least three problems exist: 
 
         [0020]     1) Synchronization: Any implementation must operate asynchronously, but asynchronous operation destroys the conservation property that enables the algorithm.  
         [0021]     2) Global Step-size: Each node must use exactly the same step-size to obtain the conservation property, which is impractical and undesirable for a true peer-to-peer implementation.  
         [0022]     3) Global Topology Dependence: The allowable step-size depends on the eigenvalues of L, which in turn depend on global properties of the network. Not only is this information not available locally, but the topology of a peer-to-peer network can change dramatically with time.  
         [0023]     All of these are serious networking concerns that cannot be avoided in any real-world implementation. The first concern, synchronization, is particularly important, since even fairly general asynchronous models do not provide a mechanism for preserving conservation properties in an asynchronous system. Some related work has been done in this area by the numerical analysis and dynamical systems communities, as in, but this work does not directly apply to this problem.  
         [0024]     Problem and Notation  
         [0025]     For purposes of this description, consider a connected network, modeled as a connected undirected graph G=(V, E). We refer to elements of V as nodes, and elements of E as links. The nodes are labeled i=1, 2, . . . , n, and a link between nodes i and j is denoted by ij.  
         [0026]     Each node has some associated numerical value, say z i , which we wish to average over the network. This could be, for example, a measure of process load, and the averaging calculation might be part of a load-balancing scheme. We will also refer to the vector z whose ith component is z i .  
         [0027]     Each node on the network maintains a local variable x i . When we wish to show the time dependence of these variables, we use the notation x i (t). Intuitively each node&#39;s local variable is its current estimate of the average value of the z; terms. We refer to this variable as the state of the node i, and we initialize the states at the values z i . We use the notation x to denote the vector whose components are the x i  terms.  
         [0028]     With this notation in hand, we remark that the Laplacian algorithm (1) can be viewed as a continuous-time gradient search for the following optimization problem:  
             min   ⁢           ⁢     1   2     ⁢     x   T     ⁢           ⁢   L   ⁢           ⁢   x               x   ∈   R                 s   .   t   .           ⁢       ∑   1     ⁢     x   i         =       ∑   1     ⁢     z   i                 
 
         [0029]     Expanding the cost function, we find it to be  
                 x   T     ⁢           ⁢   L   ⁢           ⁢   x     =       ∑     ij   ∈   E       ⁢       (       x   i     -     x   j       )     2               (   2   )             
 
 i.e. the sum of all the discrepancies across links squared. 
 
         [0030]     Overview of Message Passing  
         [0031]     The fundamental “unit” of communication in an embodiment of the invention is a pair-wise update. Consider two (distinguishable) types of messages, identified in a header. We refer to these two types as state messages and reply messages. The update procedure is illustrated in  FIG. 1  and occurs as follows:  
         [0032]     MPI: Node i produces a state message and places it on an outgoing link to some other node, say j (step  101 ).  
         [0033]     MP 2 : At some later time, node j receives this message (step  102 ).  
         [0034]     MP 3 : Node j then performs a local computation involving both its local state, and the message received from i (step  103 ).  
         [0035]     MP 4 : Node j produces a reply message and puts it on the return link from j to i (step  104 ).  
         [0036]     MP 5 : At some later time, node i receives j&#39;s reply (step  105 ).  
         [0037]     MP 6 : Node i then performs a local computation in response to j&#39;s reply message, and the procedure terminates (step  106 ).  
         [0038]     Note that this is distinct from typical models for asynchronous numerical computations. Specifically, the send-and-reply convention allows us to achieve a certain kind of virtual synchronization; although the updates are not synchronized in time, they are based on a common pair of numerical values, stored in the state and reply messages.  
         [0039]     We will also propose a certain additional behavior in message passing, which we call blocking. Generally speaking, this behavior ensures that each node is involved in at most one update at any particular time. This requires special handling of state messages that arrive at a node that itself is expecting a reply. This blocking behavior can be implemented in a number of ways. In one embodiment, we choose to have “blocking” nodes ignore any new state messages, and allow senders of state messages to timeout and retransmit if replies do not arrive.  
         [0040]      FIG. 2  is a flow diagram illustrating the pair-wise message passing with blocking in an embodiment of the invention. At step  201  node i prepares a message and sends it on a communication link to node j. At step  202  node i sets its blocking flags putting it into a blocking state while awaiting the reply message from node j. At step  203  node j receives the message. At step  204  node j performs a local computation involving its local state and the received message. At step  205  node j prepares a reply message and sends it on a communication link to node i.  
         [0041]     Steps  206 - 211  illustrate the operation of a sending node whenever it receives a message in the embodiment that uses blocking. At step  206  node i receives a message for attempted delivery from the network. At decision block  207  node i determines if its blocking flag is set. If not, then the message is accepted at step  210 . If the blocking flag is set, at decision block  208  node i determines if this is an expected reply message. If not, the message is blocked at step  209 . If the message is expected at decision block  208 , the message is accepted at step  210 . After receipt of the message, node i performs a local operation at step  211 .  
         [0042]     Algorithm A1  
         [0043]     At each node i there is a local step-size parameter γ i ,0&lt;γ i &lt;1 upon which the node s computation is based. These do not need to be coordinated, and convergence of the algorithm will be guaranteed solely by the interval bound. The step-size parameter may be chosen locally and its value does not need to be set or controlled or even known on a system wide basis.  
         [0044]     As noted above, the basic interaction in one embodiment is an update on a link. Such an update is initiated whenever a node sends out a state message containing the current value of its state. For the moment, we do not specify, the timing or triggering for this event; we merely make the following assumption:  
         [0045]     Eventual Update Assumption: for any link ij and any time t, there exists a later time t l &gt;t such that there is an update on link ij at time t l .  
         [0046]     Once an update has been initiated, the remainder of the pair-wise interaction is specified as follows and illustrated in  FIG. 3 :  
         [0047]     PW 1 : Node j receives a state message at step  301  from node i. If its blocking flag is on, it ignores the message.  
         [0048]     PW 2 : Otherwise, it uses the state value x i  from node i to generate a modified value γ j (x i −x i ) at step  302 . At step  303  it updates its own state value using the modified value by implementing x j ←x j +γ j (x i −x j ).  
         [0049]     PW 3 : Then, it generates a reply message containing the modified value γ j (x i −x j ), and at step  304  sends it to i.  
         [0050]     PW 4 : Node i has sent a state message at step  305 . At step  306  it receives the reply message that includes the modified value γ j (x i −x j ). At step  307  node i adjusts its own state value x i  by implementing x i ←x i −γ j (x i −x j ).  
         [0051]     Notice that node i does not need to know the actual value of γ j , all it needs to know is the modified value (representing how much change node j has made), which is contained in the reply message. Note also that in this embodiment, a receiving node adjusts its state value by adding the modified value and the original sending node adjusts its state value by subtracting the received modified value. It should be noted that other schemes may be implemented in other embodiments without departing from the scope and spirit of the invention.  
         [0052]     The send-and-reply mechanism of this embodiment provides conservation. Note that after an update, node i has compensated the action of node j. We thus have a certain special kind of conservation, as follows:  
         [0053]     Under the action of algorithm A1, the sum of all the node states, and any reply messages currently on the network is conserved and equal to Σ i z i .  
         [0054]     This in fact is independent of the blocking behaviour (blocking generates an additional property, which is useful for analysis).  
         [0055]     With blocking, although updates at i and j occur at different times, it is equivalent to a synchronous update and then an inactivity period for node i equal to the time it takes for a reply message to propagate from j to i.  
         [0056]     Thus, aside from the timing details of when updates are initiated, it is sufficient to consider synchronized updates, and we will do so for the purposes of the analysis to follow. It remains to be shown that any algorithm satisfying the Eventual Update Assumption and implementing the interaction (with blocking) described above must converge to a consensus.  
         [0057]     Convergence of Algorithm A1  
         [0058]     Our proof will make use of the following “potential” function:  
               P   ⁡     (   t   )       =       ∑     ∀     (     i   ,   j     )         ⁢              x   i     ⁡     (   t   )       -       x   j     ⁡     (   t   )                        (   3   )             
        where the sum is over all  
         n   ⁡     (     n   -   1     )       2       
 
 possible pairs (i,j). For instance, the potential function for the network in  FIG. 4  (an example network consisting of four nodes in a “star” topology) is 
 
|x 1 −x 2 |+|x 1 −x 3 |+|x 1 −x 4 |+|x 2 −x 3 |+|x 2 −x 4 |+|x 3 −x 4 |
       
 
         [0060]     Lemma 1: If nodes (i,j) update at time t while node i being the sender, then at the next time unit t+1 
 
 P ( t+ 1)≦ P ( t )−2 min{γ j ,1−γ j   }|x   i ( t )− x   j ( t )|  (4) 
 
         [0061]     Proof: In summary at time t+1 
 
 x   i ( t+ 1)=(1−γ j ) x   i ( t )+γ j   x   j ( t )  (5) 
 
 x   i ( t+ 1)=γ j   x   i ( t )+(1−γ j ) x   j ( t )  (6) 
 
 x   k ( t+ 1)= x   k ( t ), ∀k≠i,j  (7) 
 
         [0062]     Therefore besides the term |x i −x j |, n−2 terms of the form |x k −x i  and n−2 terms of the form |x i −x k |, k≠i,j in the potential function P(t), are affected by the update. First of all we have 
 
| x   i ( t+ 1)− x   j ( t+ 1)|=|(1−2γ j )∥ x   i ( t )− x   j ( t )  (8) 
 
         [0063]     Now consider the sum of two of the affected terms |x k (t)−x i (t)|+|x k (t)−x j (t)|. If we look at the relative positions of x i (t), x j (t), and x k (t) on the real line, then either x k  is on the same side of x i  and x j  or it is in between them. Therefore as long as 0&lt;γ i &lt;1, it is clear geometrically in both cases we have 
 
| x   k ( t+ 1)− x   i ( t+ 1),|+| x   k ( t+ 1)− x   j ( t+ 1)|≦| x   k ( t )− x   i ( t )|+| x   k ( t )− x   j ( t )|
 
         [0064]     Therefore  
         [0065]      P ( t+ 1)− P ( t )≦| x   i ( t+ 1)− x   j ( t+ 1)|−| x   i ( t )− x   j ( t )|≦−2 min{γ j ,1−γ j   }|x   i ( t )− x   j ( t )| 
         [0066]     The quantity min {γ j ,1−γ j } can be thought of as an effective step-size for node j since a step-size of 0.6, say, is equivalent to 0.4 in terms of reducing the relative difference in absolute value.  
         [0067]     Lemma 2: At any time t, there exists a later time t′&gt;t such that at time t′ there has been at least one update on every link since time t. Furthermore,  
               P   ⁡     (     t   ′     )       ≤       (     1   -       8   ⁢           ⁢     γ   *         n   2         )     ⁢           ⁢     P   ⁡     (   t   )                 (   9   )             
        where γ*=min i  min{γ i ,1−γ i }.        
 
         [0069]     Proof: Without loss of generality, suppose at time t we have x 1 (t)≦x 2 (t)≦ . . . ≦x n (t). We call the n−1 terms of the form |x i (t)−x i+1 (t)|, iε{1, 2, . . . , n−1}, segments of the network at time t. By expanding every term in the potential function as a sum of segments, we see that the potential function can be written as a linear combination of all the segments:  
               P   ⁡     (   t   )       =       ∑     i   =   1       n   -   1       ⁢       (     n   -   i     )     ⁢           ⁢   i   ⁢              x   i     ⁡     (   t   )       -       x     i   +   1       ⁡     (   t   )                          (   10   )             
 
         [0070]     We say that a segment |x i (t)−x i+1 (t)| at time t is claimed at time t′&gt;t, if there is an update on a link of nodes r and s such that the interval [x s (t′),x r (t′)] (on the real line) contains the interval [x i (t),x j (t)]. For instance, for the network in  FIG. 4 , the segments are |x 3 −x 2 |, |x 2 −x 1 , and |x 1 −x 4 |, as shown in  FIG. 5 .  FIG. 5  illustrates the four node network of  FIG. 4  embedded on the real line according to node value x i . The solid lines between the nodes represent segments or intervals on the real line separating two adjacent values. The dotted curves indicate the communication topology from  FIG. 4 . See that an update on the link between node  1  and node  3  will claim segments [x 3 ,x 2 ] and [x 2 ,x 1 ].  
         [0071]     By using the Eventual Update Assumption on each link, the existence of t′ is guaranteed. From Lemma 1 it is clear that whenever a segment is claimed, it contributes a reduction in the potential function proportional to its size (see (4)). Referring to  FIG. 5 , it can be seen that an update that does not claim a segment can only leave the segment unchanged or make it larger. Therefore no matter when a segment is claimed after time t, it will contribute at least 2γ*|x i=1 (t)−x i+1 (t)| reduction in the potential function.  
         [0072]     Now connectedness of the network implies that for each segment there is at least one link such that an update on that link will claim the segment. Therefore by time t′ all segments will be claimed. Thus the total reduction in the potential function between t and t′ is at least  
       2   ⁢           ⁢     γ   *     ⁢           ⁢       ∑     i   =   1       n   -   1       ⁢                x   i     ⁡     (   t   )       -       x     i   +   1       ⁡     (   t   )              .           
 
 It follows that  
               P   ⁡     (     t   ′     )       ≤       ⁢       P   ⁡     (   t   )       -     2   ⁢           ⁢     γ   *     ⁢           ⁢       ∑     i   =   1       n   -   1       ⁢              x   i     ⁡     (   t   )       -       x     i   +   1       ⁡     (   t   )                                =       ⁢       (     1   -         ∑     i   =   1       n   -   1       ⁢     2   ⁢           ⁢     γ   *     ⁢           ⁢              x   i     ⁡     (   t   )       -       x     i   +   1       ⁡     (   t   )                      ∑     i   =   1       n   -   1       ⁢       (     n   -   i     )     ⁢           ⁢   i   ⁢           ⁢              x   i     ⁡     (   t   )       -       x     i   +   1       ⁡     (   t   )                      )     ⁢           ⁢     P   ⁡     (   t   )                     ≤       ⁢       (     1   -       8   ⁢           ⁢     γ   *         n   2         )     ⁢           ⁢     P   ⁡     (   t   )                   
 
         [0073]     Where in the last inequality we use the fact that n(n−i)≦n 2 /4.  
         [0074]     With the above lemmas, we are ready to show convergence:  
         [0075]     Theorem 1:  
             lim     t   -&gt;   ∞       ⁢       x   i     ⁡     (   t   )         =       1   n     ⁢       ∑     i   =   1     n     ⁢       x   i     ⁡     (   t   )             ,       
 
 i.e. the consensus of initial conditions of the network, ∀iε{1, 2, . . . , n}. 
 
         [0076]     Proof Repeatedly applying Lemma 2, we see that  
                 lim     t   -&gt;   ∞       ⁢     P   ⁡     (   t   )         =   0           (   11   )             
 
         [0077]     Therefore  
                   lim     t   -&gt;   ∞       ⁢              x   i     ⁡     (   t   )       -       x   j     ⁡     (   t   )                =   0     ,     ∀   i     ,   j           (   12   )             
        now by the conservation property  
                   ∑     i   =   1     n     ⁢       x   i     ⁡     (   t   )         =       ∑     i   =   1     n     ⁢       z   i     ⁡     (   t   )           ,     ∀   t             (   113   )             
    we see that  
                 lim     t   -&gt;   ∞       ⁢       x   i     ⁡     (   t   )         =       1   n     ⁢       ∑     i   =   1     n     ⁢       z   i     ⁡     (   t   )                   (   14   )             
       
 
         [0080]     Implementation and Deadlock Avoidance  
         [0081]     Any implementation (protocol) that satisfies the Eventual Update Assumption is within the scope of the convergence proof. However we have not, as yet indicated a specific mechanism for the update triggering. Without a properly designed procedure for initiating communication, the system can drive itself into a deadlock due to the blocking condition.  
         [0082]     In an embodiment described below, we use a round-robin initiation pattern, which provably prevents deadlock and satisfies the updating assumption. This is for purposes of example only, and other schemes may be used without departing from the scope and spirit of the invention.  
         [0083]     Our implementation is based on some unique identifiers (UID), e.g. IP address. Based on these UIDs, we impose an additional directed graph H=(V, F), in which an edge points from i to j if and only if node j has a higher UID than node i. This graph has two important properties:  
         [0084]     H 1 : H has at least one root, i.e. a node with no inbound edges.  
         [0085]     H 2 : H is acyclic.  
         [0086]     This graph is illustrated for our four-node example network in  FIG. 4 .  
         [0087]     Our proposed initiation scheme is illustrated in  FIG. 6  and described as follows:  
         [0088]     RR 1 : A node will wait to observe updates from all of its inbound edges at step  601 . If not all edges have updated (step  602 ) the node continues to wait.  
         [0089]     RR 2 : After all edges have updated, the node will then sequentially initiate communication with each of its outbound edges, ordered by UID (step  603 ). If the node has not yet sent messages to all edges (step  604 ) it continues to send messages.  
         [0090]     RR 3 : Upon completion, it repeats (back to step  601 ), waiting for all of its inbound edges and so on.  
         [0091]     Lemma 3: The above procedure ensures that the Eventual Update Assumption is satisfied.  
         [0092]     Proof: We will prove this by contradiction. Suppose there is a a link ij and an interval [t,∞) during which this link does not update. Then, node i must be waiting for one of its inbound edges to be activated, implying the existence of a node k with a UID lower than that of i, which is also waiting for one of its inbound edges to be activated. Repeating this argument, and utilizing the fact that H is acyclic, we can find a path of inactive edges beginning at a root. However, a root has no inbound edges, and hence must initiate communication on all of its outbound edges at some point in [t,∞). This is a contradiction, and proves the desired result, avoiding deadlock.  
         [0093]     Joins/Leaves  
         [0094]     Peer-to-peer systems constantly deal with dynamic joining and leaving of nodes. Without modification to our averaging protocol, when node i leaves the network (either voluntarily or due to failure), the current value x i  is lost along with the node. As the remaining network continues to operate, the resulting average will be altered.  
         [0095]     It is desirable to be able to have the network calculate the average value of the new network (all nodes except for node i). This can be done with the following addition to our protocol:  
         [0096]     Suppose each neighbor of node i keeps an additional variable δ i j that keeps track of how much net flow (or flux) has taken place on this link since node i joined the network. This value is exactly the effect node i has had on its neighbor node j. When node i leaves the network, each of its neighbor node j can just subtract their δ i j from its state x i , therefore compensating the effect of node i. The averaging protocol will then result in the new average (excluding the contribution z i  of node i).  
         [0097]     Counting  
         [0098]     Due to decentralized design and dynamic joins/leaves, it is often very hard for a peer-to-peer system to estimate the size of the network N (i.e., the total number of active nodes.)  
         [0099]     With the help of our averaging protocol, one can obtain a dynamic estimate of N by setting one node state to 1 and the rest to 0. The protocol will drive all states to the average 1/N and therefore each node can figure out what N is by looking at the reciprocal of the average.  
         [0100]     One can allocate a special network node for counting purposes. It is also possible to use the bootstrapping nodes that peer-to-peer systems have for this.  
         [0101]     Algorithm A2  
         [0102]     The blocking behavior described for algorithm A1 may limit the rate at which interactions can occur. As an alternative, we consider algorithm A2. In A2, each node i makes use of the additional variables δ ij  as described above. If there is a link between nodes i and j, there will be variables δ ij  and δ ji  stored locally with node i and node j, respectively.  
         [0103]     We will denote the set of all neighbors of node i to be N i . The algorithm A2 is specified mathematically in terms of the x i &#39;s and the δ ij &#39;s as follows in the synchronous environment:  
             {               ⁢         X   i     ⁡     (     t   +   1     )       =         x   i     ⁡     (   t   )       +       γ   i     [         ∑     j   ∈     N   i         ⁢       δ   ij     ⁡     (   t   )         +     z   i     -       x   i     ⁡     (   t   )         ]                         ⁢         δ   ij     ⁡     (     t   +   1     )       =         δ   ij     ⁡     (   t   )       +       ϕ   ij     ⁡     [         x   j     ⁡     (   t   )       -       x   i     ⁡     (   t   )         ]                           (   15   )             
        where we introduce the additional parameters φ ij , which are local step-sizes similar to γ i .        
 
         [0105]     Algorithmically, the above update rules require additional specifications. First of all, each x i  is initialized to z i  as in algorithm A1, and each δ ij  is initialized to 0. If there is a link between i and j, the parameters φ ij  and φ ji  are set to be equal. (We will see that one can also just set all φ&#39;s on the network to some constant value.)  
         [0106]     Second, in order to guarantee convergence to the correct average, we require the following messaging rules. On each link ij, we impose a sender-receiver relationship on the variables φ ij  and φ ji . One can use UIDs to obtain this, as described above.  
         [0107]     MR 1 : Every node i sends to every neighbor a STATE message that contains its current state value x i  from time to time. Each node also, from time to time, executes the update rule (first equation in (15)) with the information it has about other state values.  
         [0108]     MR 2 : On link ij, if φ ij  is the sender, it executes the update rule (second equation in (15)) from time to time. Whenever φ ij  executes the update rule, it also sends to its receiver φ ji , a REPLY message that contains the value of the change it has made in the value of φ ij . φ ij  will not execute the update rule again until the TCP ACK of this REPLY message comes back.  
         [0109]     MR 3 : If φ ji  is the receiver on link id, it waits for REPLY messages from φ ij  and subtracts the value in the message from the value of φ ji . (Note that the REPLY message does not directly change the value of x j .)  
         [0110]     Notice that the second equation in (15) is general enough to cover the execution required in MR 3 . Also, since the φ ij  variables are employed, A2 is automatically equipped with the ability to handle dynamic topologies. All node i needs to do is to reset δ ij  to 0 if node j leaves the system.  
         [0111]     The invention has application in a number of areas. In one embodiment, it is used in ad-hoc sensor networks. Averaging is used to reduce variance in estimates derived from numerous measurements. Another embodiment is distributed load balancing. The system generates an estimate of the average workload in a network that is useful in designing distributed algorithms for task allocation. Another embodiment uses the system as a device for distributed polling. By averaging out the values of many binary “ballots” the members of the network can obtain a distributed estimate of the percentage voting one or zero. Other embodiments include peer-to-peer file sharing networks on the Internet (e.g. BitTorrent, Kazaa, etc.) that can compute application specific averages of interest.