After we read a lot about Trinity, a graph analytics solution like Google Pregel and Apache Hama, another graphs research group of the Extreme Computing Group (XCG) within Microsoft Research gave an overview on Horton at the GDM 2011 workshop. Horton seems to be a more general transactional graph processing approach on top of the cloud programming infrastructure Orleans that targets hosting very large graphs having billions of vertices and edges.
Horton focuses on developing a resonable Graph Query Language for simplified but still powerful online queries on Property Graphs. Graph queries will be transformed into finite state machines (FSM) for faster execution, but at the moment it is not clear if these machines are turing-complete or not. In a distributed environment the FSM will be transfered to the graph partitions. So code moves to the data instead of data to a centralized execution host. Horton tries to optimize the query execution by several techniques like minimizing communication overhead, extensive graph statistics, reordering of predicates within a graph query, derived edges (persisted queries like a friendsfriends edge instead of two seperate friends edges) and fragment reuse which is a technique to cache parts of earlier queries.
They showed an example application called CodeBook, which is more or less a social network for people and source code ;).