Back to results
US 10,951,697 B2Granted
Holochain—A framework for distributed applications
AssigneeHolo, Inc.
InventorsArthur C Brock, David Braden, Jamison M. Day
Life of this patent
Estimating the term…
Abstract
This disclosure describes a system including nodes communicating according to a relaxed, agent-centric distributed hash table. The system includes a requesting node requesting a value from a target node. The requesting node is associated with a store radius and a query radius based on an agent location of the requesting node. The store radius indicates one or more peer nodes wherein the requesting node has knowledge about the storage content of these peer nodes. The query radius indicates one or more peer nodes wherein the requesting node has connection with these peer nodes.
Claims20
A system for coordinating distributed computation, the system comprising:
- a plurality of nodes, each node including a processing element, a network interface, and a memory, the plurality of nodes communicatively coupled together via a network;
- a keyspace defined across the plurality of nodes, the keyspace having a simple closed shape with a number of dimensions;
- wherein each node of the plurality of nodes has a location in the keyspace as defined by a hash function mapping inputs to points in the keyspace, and a location in the network;
- wherein a first node has a first store radius, the first store radius describing a closed shape in the keyspace associated with the location of the node in the keyspace, the first store radius having one fewer dimension than the number of dimensions in the keyspace, and wherein the memory in the first node stores information at memory locations associated with keyspace locations within the first store radius;
- wherein first node has a first query radius, the first query radius describing a closed shape in the keyspace associated with the location of the node in the keyspace, the first query radius having one fewer dimensions than the number of dimensions in the keyspace, wherein the first query radius is larger than the first store radius;
- wherein a first subset of the nodes from the plurality of nodes have keyspace locations within the first query radius, and the first node stores the network location of the first subset of the nodes, each of the nodes in the first subset of the nodes having a secondary store radius and a secondary query radius;
- wherein the processing element of each node is operable to respond to a request for information stored at an arbitrary location in the keyspace by:
- when the requested information has a keyspace location within the store radius, returning the value of the information from the first node;
- when the requested information has a keyspace location outside the store radius but inside the query radius, querying, via the network, a second node from the first subset of the nodes within the query radius and returning the value of the information returned from the second node with a secondary store radius encompassing the requested keyspace location;
- and
- returning a network location referral to a third node, wherein the keyspace location of the third node has a lower distance from the keyspace location of the requested information than the keyspace location of the first node.
8 more elements
A method for coordinating distributed computation, the method comprising:
- communicatively coupling a plurality of nodes via a network, each node including a processing element, a network interface, a network location, and a memory;
- defining a keyspace across the plurality of nodes, the keyspace having a simple closed shape with a number of dimensions;
- assigning each node of the plurality of nodes a keyspace location, a store radius, and a query radius;
- each keyspace location being defined by a hash function mapping inputs to points in the keyspace;
- each store radius describing a closed shape in the keyspace having one fewer dimension than the number of dimensions in the keyspace;
- each query radius describing a closed shape in the keyspace having one fewer dimension than the number of dimensions in the keyspace, where the query radius is greater than the store radius;
- receiving a request at a first node, the request being associated with a keyspace location;
- when the requested information has a keyspace location within the store radius of the first node, responding from the first node;
- when the requested information has a keyspace location outside the store radius of the first node but inside the query radius of the first node, querying, via the network, a second node from the first subset of the nodes within the query radius and returning the response received from the second node;
- and
- returning a network location referral to a third node, wherein the distance from the keyspace location of the third node to the keyspace location associated with the request is less than the distance from the keyspace location of the first node to the keyspace location associated with the request.
8 more elements
A node in a distributed processing system, the node comprising:
- a processing element, a network interface, a network location, a first keyspace location, and a memory, wherein the processing element is operable to:
- compute a requested location within a multidimensional keyspace corresponding to a distributed hash table;
- store and retrieve information corresponding to a first closed area within the keyspace in the memory;
- store and retrieve information corresponding to a second closed area within the keyspace in the memory;
- receive a request via the network interface, the request being associated with a keyspace location;
- when the request keyspace location is within the first closed area within the keyspace, responding to the request using the information retrieved from the memory corresponding to the request keyspace location;
- when the request keyspace location is within the second closed area within the keyspace, forwarding the request to a network location retrieved from the memory corresponding to the request keyspace location;
- and
- returning a network location referral, wherein the network location referral target is closer to the request keyspace location than first keyspace location.
6 more elements
Dependencies are inferred from the claim text.