Directly programmable networks

Claim 1

A method for establishing a scalable spanning tree for an arbitrary subset of nodes and links in a network in which the total resources at each node are independent of the size of the network, and for propagating data over the spanning tree, the method comprising the steps of selecting a set of states for each node and each link in the network, the states being independent of the topology of the network, of the size of the network, and of the node itself, selecting a set of messages exchanged between neighboring nodes over the links, the messages being independent of the topology of the network, of the size of the network, and of the node itself, determining a set of state transition rules for the state of each node and of each link to coordinate the sending and receiving of the messages to the neighboring nodes for setting up the spanning tree, the state transition rules being independent of the topology of the network, of the size of the network, and of the node itself, determining a completion rule in order that at least one node detects the formation of the spanning tree, this node being designated the root node, the rule being independent of the topology of the network, of the size of the network, and of the node itself, back-propagating node data from each node in a subset of nodes to the root node over the spanning tree to form composite data, and forward-propagating at least part of the composite data as said data from the root node to another subset of the nodes.

Claim 2

A method for establishing a scalable spanning tree for an arbitrary subset of nodes and links in a network in which the total resources at each node are independent of the size of the network, and for propagating data over the spanning tree, the method comprising the steps of selecting a set of states for each node and each link in the network, the states being independent of the topology of the network, of the size of the network, and of the node itself, selecting a set of messages exchanged between neighboring nodes over the links, the messages being independent of the topology of the network, of the size of the network, and of the node itself, determining a set of state transition rules for the state of each node and of each link to coordinate the sending and receiving of the messages to the neighboring nodes for setting up the spanning tree, the state transition rules being independent of the topology of the network, of the size of the network, and of the node itself, determining a completion rule in order that at least one node detects the formation of the spanning tree, this node being designated the root node, the rule being independent of the topology of the network, of the size of the network, and of the node itself, back-propagating node data from each node in a subset of nodes to the root node over the spanning tree to form composite data, and forward-propagating at least part of the composite data as said data from the root node to another subset of the nodes.

Claim 4

A method for establishing a scalable spanning tree for an arbitrary subset of nodes and links in a network in which the total resources at each node are independent of the size of the network, and for propagating data over the spanning tree, the method comprising the steps of processing a set of states for each node and each link in the network, the states being independent of the topology of the network, of the size of the network, and of the node itself, processing a set of messages exchanged between neighboring nodes over the links, the messages being independent of the topology of the network, of the size of the network, and of the node itself, processing a set of state transition rules for the state of each node and of each link to coordinate the sending and receiving of the messages to the neighboring nodes for setting up the spanning tree, the state transition rules being independent of the topology of the network, of the size of the network, and of the node itself, processing a completion rule in order that at least one node detects the formation of the spanning tree, this node being designated the root node, the rule being independent of the topology of the network, of the size of the network, and of the node itself, back-propagating node data from each node in a subset of nodes to the root node over the spanning tree to form composite data, and forward-propagating at least part of the composite data as said data from the root node to another subset of the nodes.

Claim 5

A method for establishing a scalable spanning tree for an arbitrary subset of nodes and links in a network in which the total resources at each node are independent of the size of the network, and for propagating data over the spanning tree, the method comprising the steps of processing a set of states for each node and each link in the network, the states being independent of the topology of the network, of the size of the network, and of the node itself, processing a set of messages exchanged between neighboring nodes over the links, the messages being independent of the topology of the network, of the size of the network, and of the node itself, processing a set of state transition rules for the state of each node and of each link to coordinate the sending and receiving of the messages to the neighboring nodes for setting up the spanning tree, the state transition rules being independent of the topology of the network, of the size of the network, and of the node itself, processing a completion rule in order that at least one node detects the formation of the spanning tree, this node being designated the root node, the rule being independent of the topology of the network, of the size of the network, and of the node itself, back-propagating node data from each node in a subset of nodes to the root node over the spanning tree to form composite data, and forward-propagating at least part of the composite data as said data from the root node to another subset of the nodes.

Claim 7

A method for coordinating programs executing in the nodes of a spanning tree covering a network composed of the nodes and links interconnecting the nodes, and for propagating data over the spanning tree, the method comprising the steps of determining the states of each node for which data may be collected and sent to the root of the spanning tree, determining the states of each node for which data may be distributed away from the root of the spanning tree, wherein the states are independent of the topology of the network, of the size of the network, and of each node itself, and selecting messages to indicate the completion of a cycle involving the collection of data at the root and the distribution of data to each node from the root, the messages being independent of the topology of the network, of the size of the network, and of each node itself.

Claim 8

A method for coordinating programs executing in the nodes of a spanning tree covering a network composed of the nodes and links interconnecting the nodes, and for propagating data over the spanning tree, the method comprising the steps of determining the states of each node for which data may be collected and sent to the root of the spanning tree, determining the states of each node for which data may be distributed away from the root of the spanning tree, wherein the states are independent of the topology of the network, of the size of the network, and of each node itself, and selecting messages to indicate the completion of a cycle involving the collection of data at the root and the distribution of data to each node from the root, the messages being independent of the topology of the network, of the size of the network, and of each node itself.

Claim 9

A method for coordinating programs executing in the nodes of a spanning tree covering a network composed of the nodes and links interconnecting the nodes, and for propagating data over the spanning tree, the method comprising the steps of processing the states of each node for which data may be collected and sent to the root of the spanning tree, processing the states of each node for which data may be distributed away from the root of the spanning tree, wherein the states are independent of the topology of the network, of the size of the network, and of each node itself, and processing messages to indicate the completion of a cycle involving the collection of data at the root and the distribution of data to each node from the root, the messages being independent of the topology of the network, of the size of the network, and of each node itself.

Claim 10

A method for coordinating programs executing in the nodes of a spanning tree covering a network composed of the nodes and links interconnecting the nodes, and for propagating data over the spanning tree, the method comprising the steps of processing the states of each node for which data may be collected and sent to the root of the spanning tree, processing the states of each node for which data may be distributed away from the root of the spanning tree, wherein the states are independent of the topology of the network, of the size of the network, and of each node itself, and processing messages to indicate the completion of a cycle involving the collection of data at the root and the distribution of data to each node from the root, the messages being independent of the topology of the network, of the size of the network, and of each node itself.

Claim 11

A method for propagating data in a network composed of nodes interconnected by links in which the total resources at each node are independent of the topology of the network, of the size of the network, and of the node itself, the method comprising the steps of determining a scalable spanning tree over the nodes of the network, the step of determining including the steps of processing a set of states for each node and each link, the states being independent of the topology of the network, of the size of the network, and of the node itself, processing a set of messages exchanged between neighboring nodes over the links, the messages being independent of the topology of the network, of the size of the network, and of the node itself, processing a set of state transition rules for the state of each node and of each link to coordinate the sending and receiving of the messages to the neighboring nodes for setting up the spanning tree, the state transition rules being independent of the topology of the network, of the size of the network, and of the node itself, and processing a completion rule in order that at least one node detects the formation of the spanning tree, this node being designated the root node, the rule being independent of the topology of the network, of the size of the network, and of the node itself, back-propagating node data from each node in a subset of the nodes to the root node over the spanning tree to form composite data, and forward-propagating at least part of the composite data from the root node to another subset of the nodes.

Claim 12

A method for propagating data in a network composed of nodes interconnected by links in which the total resources at each node are independent of the topology of the network, of the size of the network, and of the node itself, the method comprising the steps of determining a scalable spanning tree over the nodes of the network, the step of determining including the steps of processing a set of states for each node and each link, the states being independent of the topology of the network, of the size of the network, and of the node itself, processing a set of messages exchanged between neighboring nodes over the links, the messages being independent of the topology of the network, of the size of the network, and of the node itself, processing a set of state transition rules for the state of each node and of each link to coordinate the sending and receiving of the messages to the neighboring nodes for setting up the spanning tree, the state transition rules being independent of the topology of the network, of the size of the network, and of the node itself, and processing a completion rule in order that at least one node detects the formation of the spanning tree, this node being designated the root node, the rule being independent of the topology of the network, of the size of the network, and of the node itself, back-propagating node data from each node in a subset of the nodes to the root node over the spanning tree to form composite data, and forward-propagating at least part of the composite data from the root node to another subset of the nodes.

Claim 13

A method for establishing a scalable spanning tree for an arbitrary subset of nodes and links in a network in which the total resources at each node is independent of the size of the network, the spanning tree being used to propagate data originated by the nodes over the network, the method comprising the steps of selecting a set of node states for each node, the node states being independent of the topology of the network, of the size of the network, and of the node itself, selecting a set of link states for each link, the link states being independent of the topology of the network, of the size of the network, and of the node itself, selecting a set of self messages originated in each of the nodes for self-communication, the self messages being independent of the topology of the network, of the size of the network, and of the node itself, selecting a set of synchronization messages originated in one or more of the subset of nodes to control the exchange of the data over the links, the synchronization messages being independent of the topology of the network, of the size of the network, and of the node itself, selecting a set of system messages originated in the subset of nodes, the system messages being independent of the topology of the network, of the size of the network, and of the node itself, and wherein each of the system messages may include a subset of the data, transmitting the system messages to neighboring nodes over the links, executing the messages in each node in the order: self messages; synchronization messages; and system messages, determining a set of state transition rules for the state of each node and the state of each link to coordinate the sending and receiving of the system messages to the neighboring nodes for setting up the spanning tree, the state transition rules being independent of the topology of the network, of the size of the network, and of the node itself, and determining a completion rule in order that at least one node detects the formation of the spanning tree, the rule being independent of the topology of the network, of the size of the network, and of the node itself.

Claim 14

A method for establishing a scalable spanning tree for an arbitrary subset of nodes and links in a network in which the total resources at each node is independent of the size of the network, the spanning tree being used to propagate data originated by the nodes over the network, the method comprising the steps of selecting a set of node states for each node, the node states being independent of the topology of the network, of the size of the network, and of the node itself, selecting a set of link states for each link, the link states being independent of the topology of the network, of the size of the network, and of the node itself, selecting a set of self messages originated in each of the nodes for self-communication, the self messages being independent of the topology of the network, of the size of the network, and of the node itself, selecting a set of synchronization messages originated in one or more of the subset of nodes to control the exchange of the data over the links, the synchronization messages being independent of the topology of the network, of the size of the network, and of the node itself, selecting a set of system messages originated in the subset of nodes, the system messages being independent of the topology of the network, of the size of the network, and of the node itself, and wherein each of the system messages may include a subset of the data, transmitting the system messages to neighboring nodes over the links, executing the messages in each node in the order: self messages; synchronization messages; and system messages, determining a set of state transition rules for the state of each node and the state of each link to coordinate the sending and receiving of the system messages to the neighboring nodes for setting up the spanning tree, the state transition rules being independent of the topology of the network, of the size of the network, and of the node itself, and determining a completion rule in order that at least one node detects the formation of the spanning tree, the rule being independent of the topology of the network, of the size of the network, and of the node itself.