1. At a node in an overlay network, the node including a processor and system memory, the overly network including the node and at least one other node, the node and each of the at least one other 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 storing data for the process, the process runtime and the queue co-located within the process; an act of altering the queue state for the queue in response to performing a queue related operation on the accessed data; and an act of replicating the altered queue state for the queue to the at least one other node 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 least one other nodes that is subsequently assigned responsibility for the process.