Distributed data propagator

A method for executing a message-passing parallel program, comprised of a plurality of concurrently-executable virtual nodes, each having one or more numbered step(s), with one or more associated executable instruction(s) and zero or more associated messaging task(s), the method comprising:

• maintaining a pool of available processing elements, wherein the number of processing elements in the pool may be smaller than the number of virtual nodes;
• assigning each of the virtual nodes to at least one processing element from the pool of available processing elements;
• and,
• executing the parallel program, starting with the lowest-numbered step, by:
• (a) executing all instruction(s) associated with said step;
• (b) completing all messaging task(s) associated with said step;
• and, then,
• (c) repeating (a)-(b) for the next lowest-numbered step until execution of the parallel program is completed.

A fault-tolerant method for executing a message-passing parallel program on a network of interruptible processors, the method comprising:

• (a) maintaining a plurality of concurrently-executable virtual nodes, each having associated state information;
• (b) cacheing the state information associated with each virtual node onto one or more network-accessible servers;
• (c) advancing execution of the parallel program by permitting instructions associated with one or more of the virtual nodes to be executed on one or more available processing elements, and permitting messages to be exchanged between the virtual nodes;
• (d) upon normal completion of (c), updating cached state information on the network-accessible servers and returning to (c) to continue execution, or, upon fault detection or timeout during (c), restoring the state of the virtual nodes using the cached state information and repeating (c).

A fault-tolerant, network-based computing system configured to execute a message-passing parallel program on a network of interruptible processors, the system comprising:

• (a) a plurality of concurrently-executable virtual nodes, each having associated state information;
• (b) one or more network-accessible servers that collectively maintain a cache of the state information associated with each virtual node;
• (c) at least one server that controls execution of the parallel program by permitting instructions associated with one or more of the virtual nodes to be executed on one or more available processing elements, and permits messages to be exchanged between the virtual nodes;
• (d) the server including means for updating cached state information and continuing execution, or, upon fault detection or timeout, restoring the state of the virtual nodes using cached state information and repeating execution of selected instructions.