In a distributed hash table overlay network, messages directed to a message ID are relayed to one or more nodes that have published interest in that message ID. Messages are distributed, processed, and/or cached in accordance with relay policies, which enable a wide variety of different applications. Nodes specify relay policies on a per-node, per-message, and/or per-message ID basis. Relay policies can specify any behavior associated with messages, including: message caching, distribution, and processing as well as migration of relay policies when nodes join or leave the network. Intermediate nodes can perform any arbitrary processing of messages based on relay policies. Intermediate nodes can offload processing to other nodes, either by forwarding messages to a different message ID or by enlisting the help of nodes subscribed to the message ID. Messages can include one or more subfields specifying commands and/or data to be evaluated by the intermediate node.