Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I am implementing a gossip based membership detection mechanism. Lets say we have a ring topology, i.e. node1 only knows about the 2 nodes (node4 and node2) around it.

                node1
             -        -
          -              -
      node4              node2
          -              -
            -         -
               node3

Now, gossiping says: Pick a node at random from the membership list. But, if we strictly follow the ring topology, then node1 should only try to gossip with node2 or node4. Other wise, only for communication the topology will become a clique rather than being a ring.

Background: According to the Amazon dyanmo paper:

Each node contacts a peer chosen at random every second and the two nodes efficiently reconcile their persisted membership change histories.

If, that is the case, then is dynamo's implementation not following a "true" ring topology and only using ring for consistent hashing (replication) and using a clique for membership detection?

share|improve this question
    
Sorry for my bad ascii art, learning! –  zengr Mar 20 '11 at 20:29
add comment

1 Answer

up vote 1 down vote accepted

In your example:

I don't think a node knows what his direct neighbors are. It just has 2 neighbors, it doesn't know which.

Node 4 wants to chat with node 3:

  • Node 4 sends the message to node 1 (just the ring direction).
  • Node 1 sees message is not for him so it passes it on to node 2.
  • Node 2 sees message is not for him so it passes it on to node 3.
  • Node 3 gets the message, sees it's for him and parses it.

"Gossiping" is where node 1 and 2 listens in on the conversation (which they help facilitate). By listening in they hear about a node 4 and a node 3, both can be added to their membership list.

Both node 1 and 2 can now ask node 4 and 3 what other members they know.

Say node 1 asks node 4 first. Node 2 and 3 will find out about node 1's existence by listening to the gossip.

Noone knows about node 2 at this point, but eventually it will also revealing it's presence by asking another node for it's membership list.

This doesn't break communication lines in any way.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.