Method of aggregate statistic computation

1. A method of grouping nodes within a distributed network, comprising:

performing a leader node self determination operation, without interacting with other nodes within the distributed network, by which each node within the distributed network determines whether to become a leader node or a non-leader node, each leader node being the leader of a group including at least one node;

sending requests, from each leader node, requesting at least one non-leader node to join the group associated with the leader node, the at least one non-leader node initially being unassociated with the leader node sending the requests;

accepting, at each non-leader node, a request from a first requesting leader node, such that accepting non-leader nodes transition from a non-leader node to a dependent node dependent upon the requesting leader node;

sending requests, from each remaining non-leader node, requesting to join the group associated with at least one leader node;

determining, at each requested leader node, whether to accept the non-leader node into the group associated with the requested leader node; and

accepting, at each requested leader node, the non-leader node into the group associated with the requested leader node based on the determining step.

2. The method of claim 1 , wherein the leader node self determination operation comprises:

determining, at each of the nodes within the distributed network, whether to transition to a leader node such that each node within the distributed has a probability (1/log n) of becoming a leader node, where n is a total number of nodes within the distributed network; and

transitioning approximately (n/log n) of the n nodes into leader nodes.

3. The method of claim 1 , wherein the sending step performed at each leader node comprises:

selecting one of a plurality of nodes within the distributed network; and

sending a group join request requesting the selected node to join an associated group.

4. The method of claim 3 , wherein the sending step performed at each leader node further comprises:

repeating the selecting and sending a group join request steps until a number of iterations of the selecting and sending a group join request steps exceeds a threshold.

5. The method of claim 4 , wherein the leader node and the selected node exchange data if the selected node accepts the group join request.

6. The method of claim 3 , wherein the selecting step randomly selects one of the plurality of nodes.

7. The method of claim 1 , wherein transitioning from a non-leader node to a dependent node includes exchanging data between the dependent node and the associated leader node.

8. The method of claim 1 , wherein the accepting step performed at each non-leader node accepts the request from the first requesting leader node if the request is received within a time threshold.

9. The method of claim 8 , wherein the time threshold is a given number of rounds, each round being a synchronized interval within which leader nodes send a single request to join the group of the leader node.

10. The method of claim 1 , wherein sending step performed by each remaining non-leader node comprises:

selecting one of a plurality of nodes within the distributed network;

determining whether the selected node is a leader node;

sending a group join request to the selected node if the determining step indicates that the selected node is a leader node; and

receiving contact information for a leader node of the group associated with the selected node if the determining step indicates that the selected node is not a leader node.

11. The method of claim 10 , wherein sending step performed by each remaining non-leader node further comprises:

repeating the selecting, determining, sending a group join request and receiving steps until either (i) a leader node accepts the group join request or (ii) the number of iterations of the selecting, determining, sending a group join request and receiving steps exceeds a threshold.

12. The method of claim 10 , wherein sending step performed by each remaining non-leader node further comprises:

repeating the sending a group join request step for the leader node of the group associated with the selected node if the determining step indicates that the selected node is not a leader node.

13. The method of claim 1 , wherein the determining step determines to accept the non-leader node into the group associated with the requested leader node if (i) a number of nodes within the group associated with the requested leader node does not exceed a first threshold or (ii) a number of nodes joining the group associated with the requested leader node in response to requests sent by the remaining non-leader nodes does not exceed a second threshold.

14. The method of claim 1 , further comprising:

performing an aggregate statistic computation, the leader nodes configured to operate in accordance with a first set of protocols during the aggregate statistic computation and the dependent nodes configured to operate in accordance with a second set of protocols during the aggregate statistic computation.

15. The method of claim 14 , wherein the aggregate statistic computation is based upon local data of a given data type stored independently at each of the nodes within the distributed network.

16. The method of claim 15 , wherein the aggregate statistic computation is one of (i) calculating a maximum of the local data among all of the nodes within the distributed network, (ii) calculating a sum of the local data among all of the nodes within the distributed network, (iii) calculating an average of the local data among all of the nodes within the distributed network, (iv) calculating a group average of the local data among all of the groups within the distributed network, (v) calculating a rank of the local data among all of the nodes within the distributed network and (vi) calculating a minimum of the local data among all of the nodes within the distributed network.