Distributed Graph Data Structure

Category: JavaSpaceIdioms

I've seen plenty of examples on the web and indeed on this site for simple distributed data structures like "array", "bag" or "channel". But what about more complex data structures - like "graph", for example. Or "tree".

Well based on the principles mentioned in SplitItUp? and chapter 3 of JavaSpacesPrinciplesPatternsAndPractice, I've come up with the following implementation of a distributed graph. It may be way off - I really don't know - but hopefully the refactoring environment encouraged by WikiWeb will improve it over time.

Here is Graph.java:

 public class Graph implements Entry
 {
   public String name;
   public List<Integer> nodeUIDs = new ArrayList<Integer>();
   public List<Integer> EdgeUIDs = new ArrayList<Integer>();

   public Graph()
   {
   }

   public Graph ( String name )
   {
     this.name = name;
   }
 }

The may or may not be named. A non-distributed graph would contain direct object references to its contained nodes and edges. But a distributed version should not - based on the principle in SplitItUp?. Instead we store "keys" to the individual nodes and edges - in this case the keys are UIDs. More on how the UIDs are generated later.

Here is Node.java:

 public class Node implements Entry
 {
   public Integer uid;
   public List<Integer> edgeUIDs = new ArrayList<Integer>();  

   public Node()
   {
   }

   public Node ( Integer uid )
   {
     this.uid = uid;
   }

   public void addEdgeUID ( Integer uid )
   {
      edgeUIDs.addElement ( uid );
   }
 }

Each Node has a UID. And it has to list of the UIDs of the Edges that it is involved with.

Here is Edge.java:

 public class Edge implements Entry
 {
   public Integer uid;
   public Integer nodeUID1;
   public Integer nodeUID2;

   public Edge()
   {
   }

   public Edge ( Integer uid, Integer n1, Integer n2 )
   {
     this.uid = uid;
     this.nodeUID1 = n1;
     this.nodeUID2 = n2;
   }
 }

Again, has a UID and the UIDs of the two Nodes it it involved with.

How are the UIDs generated? Well, use the Shared Var pattern outlined in JavaSpacesPrinciplesPatternsAndPractice - I won't go into it here.

So that's the data structure. Now what is the protocol to access it?

Create a Graph instance and write it to the java space. Create two nodes and write them to the space. Add the nodes' UIDs to graph.nodeUIDs. Create an Edge linking the two nodes (via UIDs). Add the Edge to the space. Update both nodes' edgeUIDs Vector with the UID of the new Edge. Now we have a simple graph.

To navigate, retrieve the Graph object from the space using a template. From the Graph object we can get the UIDs of each Node and Edge and retrieve them using a template.

So, we can implement a distributed graph using this approach. But it has a number of drawbacks. Its biggest problem is that it scales very badly as the number of objects grows.

Place your better ideas here. -- MikeHogan?

---

Hi I am new to java space so forgive my ignorance, with out using java space I am implementing a similar system what you described above. I am modeling SAN and NAS (storage network) configurations, in which servers, switches and storage units are connected in a big network. All these components have ports and are connected using connectors. I have unique ID generator inside my configuration that gives ID to what ever that goes into the configuration object. So think of my configuration as being your (java) space, and your graph being the network, and Entry being any component(switch,host etc) or subcomponent(like ports) that can be identified uniquely.So for the construction of the graph, I use something in the following way.

  class Relation extends Entry{
   Entry one;
   Entry two;
  }
  class PhysicalConnector? extends Relation{
  //has some more characteristics of distance ,type of connector etc etc
  }
  class Access extends Relation{
  //in SAN and NAS world a logical relation tells what components have access (which is completely different from physical connection) to what other components
  //its parameters
  }

The retrieval of any relation is in the same way, to get physically connected switches to a host, I would query the configuration for relations that have given Entry(host) and has a relation of type physical connection. Similarly I would ask the configuration for all the switches a host has access to. So this forms a uniform way of relating any two Entries if they don't fall under parent child relation.

-- SeshKumar

---

What would such a contraption be used for? UseCase?

---

JavaSpaceIdioms