Systems and techniques to access and/or configure information in graph store are provided. In some embodiments, a state table can be generated in addition to a main table, such as a distributed hash table embodying the graph store. The state table can include information indicative of a state of a relationship between a first node and a second node in the graph store. Availability of the state table can permit the control of termination of an update in scenarios of inconsistency and/or concurrent updates. As such, updates to a pair of nodes, each having one or more records, can leverage the state table to access the record(s) of the nodes and to modify an edge associated with the node. The state table also can permit controllably terminating an update and/or ensuring that consistency of the graph store is maintained after the update. Approaches to resolve error during updates to the graph store also are provided.