Joining a broadcast channel
A technique for adding a participant to a network is provided. This technique allows for the simultaneous sharing of information among many participants in a network without the placement of a high overhead on the underlying communication network. To connect to the broadcast channel, a seeking computer first locates a computer that is fully connected to the broadcast channel. The seeking computer then establishes a connection with a number of the computers that are already connected to the broadcast channel. The technique for adding a participant to a network includes identifying a pair of participants that are connected to the network, disconnecting the participants of the identified pair from each other, and connecting each participant of the identified pair of participants to the added participant.
1. A computer-based, non-routing table based, non-switch based method for adding a participant to a network of participants, each participant being connected to three or more other participants, the method comprising:
identifying a pair of participants of the network that are connected wherein a seeking participant contacts a fully connected portal computer, which in turn sends an edge connection request to a number of randomly selected neighboring participants to which the seeking participant is to connect;
disconnecting the participants of the identified pair from each other; and
connecting each participant of the identified pair of participants to the seeking participant.
2. The method of claim 1 wherein each participant is connected to 4 participants.
3. The method of claim 1 wherein the identifying of a pair includes randomly selecting a pair of participants that are connected.
4. The method of claim 3 wherein the randomly selecting of a pair includes sending a message through the network on a randomly selected path.
5. The method of claim 4 wherein when a participant receives the message, the participant sends the message to a randomly selected participant to which it is connected.
6. The method of claim 4 wherein the randomly selected path is proportional to the diameter of the network.
7. The method of claim 1 wherein the participant to be added requests a portal computer to initiate the identifying of the pair of participants.
8. The method of claim 7 wherein the initiating of the identifying of the pair of participants includes the portal computer sending a message to a connected participant requesting an edge connection.
9. The method of claim 8 wherein the portal computer indicates that the message is to travel a distance proportional to the diameter of the network and wherein the participant that receives the message after the message has traveled that distance is one of the participants of the identified pair of participants.
10. The method of claim 9 wherein the certain distance is twice the diameter of the network.
11. The method of claim 1 wherein the participants are connected via the Internet.
12. The method of claim 1 wherein the participants are connected via TCP/IP connections.
13. The method of claim 1 wherein the participants are computer processes.
14. A computer-based, non-switch based method for adding nodes to a graph that is m-regular and m-connected to maintain the graph as m-regular, where m is four or greater, the method comprising:
identifying p pairs of nodes of the graph that are connected, where p is one half of m, wherein a seeking node contacts a fully connected portal node, which in turn sends an edge connection request to a number of randomly selected neighboring nodes to which the seeking node is to connect;
disconnecting the nodes of each identified pair from each other; and
connecting each node of the identified pairs of nodes to the seeking node.
15. The method of claim 14 wherein identifying of the p pairs of nodes includes randomly selecting a pair of connected nodes.
16. The method of claim 14 wherein the nodes are computers and the connections are point-to-point communications connections.
17. The method of claim 14 wherein m is even.