A graph comprising nodes and edges is stored by a distributed system as a collection of nodes and half-edges stored with their respective nodes. A message processor is associated with a node as needed to process messages passed between nodes, such that a given node has zero or one message processor assigned to it at a given time. Queries of the graph are resolved by processing a first portion of the query at a first node, and forwarding the results with the remaining portions of the query to a node linked by an edge to the present node.