1. At a node in an overlay network, the node including a processor and system memory, the overly network including a plurality nodes, each node in the plurality of nodes being assigned responsibility for a range of identifiers on the overlay network, a method for replicating queue state within the overlay network, the method comprising: an act of accessing data for a process at the node, the node including a process runtime for running the process and a queue for queuing data for the process, the process runtime and the queue co-located within the process at the node; an act of performing a queue related operation on the accessed data, the queue related operation selected from among: queueing the accessed data in the queue and dequeueing the accessed data from the queue; an act of altering the queue state for the queue in response to the queue related operation; and an act of replicating the altered queue state for the queue to a plurality of other nodes on the overlay network, replicating the altered queue state increasing the availability of the altered queue state such that the altered queue state is available at any of the plurality of other nodes that is subsequently assigned responsibility for the process.