Quantcast

Use Zookeeper to generate Minimum Spanning tree

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Use Zookeeper to generate Minimum Spanning tree

mregmee
In a given graph (network), where each node represents a single client and each node initially knows the weight for each edge incident to that node along with the neighboring vertices. Can we generate the minimum spanning tree of this network using Zookeeper?
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Use Zookeeper to generate Minimum Spanning tree

dkatz
This should be possible.  Basically you need to treat Zookeeper as a broadcast medium in which you carry link state information (a ZK node per graph vertex).  It's a link state protocol using Zookeeper as the transport.

The most straightforward thing would be to create a ZK node per vertex in a flat space at one ZK parent node, and have everyone watch the parent node for changes.

The rest is a small matter of graph theory and distributed computation.  If you give up the idea of a truly minimum spanning tree (such as in the spanning tree protocol for LAN bridges) it's easier.

--Dave

On Oct 4, 2013, at 3:53 PM, mregmee <[hidden email]> wrote:

> In a given graph (network), where each node represents a single client and
> each node initially knows the weight for each edge incident to that node
> along with the neighboring vertices. Can we generate the minimum spanning
> tree of this network using Zookeeper?
>
>
>
> --
> View this message in context: http://zookeeper-user.578899.n2.nabble.com/Use-Zookeeper-to-generate-Minimum-Spanning-tree-tp7579155.html
> Sent from the zookeeper-user mailing list archive at Nabble.com.
>

Loading...