1. A computer-implemented method for establishing one or more connections in a network, comprising: under the control of one or more computer systems configured with executable instructions, sending a discovery message to a plurality of neighboring nodes; in response to the discovery message, receiving from each node of the plurality of neighboring nodes a number of connections associated with each node, the number of connections specifying a number of nodes with which the node is capable of exchanging state information; stochastically selecting a set of nodes of the plurality of neighboring nodes for connection establishment, the selecting being performed based at least in part on the number of connections associated with the plurality of neighboring nodes and the selecting being positively biased to a first node of the plurality of neighboring nodes having a larger number of connections than a second node of the plurality of neighboring nodes; and establishing a connection with each node of the selected set of nodes, the connection enabling exchanging a state information update with each node of the selected set of nodes.