graph_computing

Last updated: 2024-09-23 12:08:19.123243 File source: link on GitLab

Graph computing

Graph computing is a quickly developing new paradigm of computing which leverages network science and graph theory to represent data, programs and their interactions in distributed computing environments. It is a large set of technologies and a way of modelling the world in terms of entities (nodes) and their relations (semantic or analogous associations, causality, information, control flows, mapping between h hardware and software, etc.). The graph computing field is very diverse and evolves quickly by featuring new and augmented ways to computing on theoretical and practical levels.

Network topology as a graph

Graph computing concepts allow to express dynamic topology of the computation network in terms of links between actors. It also allows for implementation of location awareness of each actor in terms of access to global graph topology vial local traversals.

Actors can know the mail addresses of other actors, which makes them acquaintances, or neighbours and is a basis of the local network topology. Mail addresses can be contained in messages, which allows for a dynamic actor interconnection topology, where actors can connect directly to each other based on indirectly passed and received messages.

The actor system therefore is a dynamic network structure, where nodes are actors with links to their mutual acquaintances. Using these links, every actor can in principle reach every other actor and learn local or global network structure via distributed message-passing algorithms. Note, that first, such an actor system can be represented a graph form and using graph formalism. Second, in order for any actor to have partial (or, in the edge case, full) representation of the global state of the system, it has (1) to know all other actors and (2) to have a local representation of each actor’s state in its own memory.

Graph traversal

Graph traversal is a systematic method of exploring vertices and edges in a graph. Traversals are represented using special purpose graph traversal languages which formalize an abstract description of a legal path through a graph. Graph traversing is then a process of visiting (checking, updating or modifying) vertices and links of a graph, based on the imperatively defined constraints in this language by a user.

The concept is important for us because by expressing NuNet network / platform as a well formed graph structure and implementing interfaces exposing graph traversal logic, we allow each Actor in the NuNet platform (so each Node and Allocation) to execute Turing-complete programs on top of decentralized graph. This is essential for decentralized computing ecosystems in general and for implementing NuNet computing model in particular.

Consider the Web as an example. When a person, program or a mobile application "queries" the web for information, one does not have access to all information residing in all other nodes – servers, web pages, programs or mobile applications – at once. One does not even know, or need to know, how many other nodes exist in the network. Instead, one accesses the network via its local node and follows from link to node to another link selectively and iteratively until reaching the desired node or content. This is a primitive example of vertex-centric graph traversal where each traversal has to start from an existing node in the graph and traverse through its neighbouring links. This operation can be written formally in imperative graph traversal language.

In the full-fledged Graph traversal context, traversers can mutate a graph when walking it – i.e. change properties on links and vertexes, create new vertices (e.g. Nodes or Allocations) or connect them via new links.

High level system properties provided by graph computing

Fluid topology

Using graph computing concept in the decentralized computing context promises to altogether decouple content, data and executable code from any physical location, server or client implementation. Such a dynamic network of interacting processes is best conceived as a decentralized computing infrastructure in terms of interactive computation, actor model and an ecosystem of emergent computation graphs -- a fluid topology that changes and adapts to the computations performed in the network.

At NuNet such fluid topology is provided by integrating the message-passing framework of the actor model to graph computing. Based on our use-case based platform development model (see E. Platform Development Model).

Resources

Last updated