[dsnp-interest] working on distribution tree maintenance

[Adrian Thurston]

To speed up the distribution of messages, a user's list of friends is 
organized into a tree. Each friend forwards broadcast messages on to 
other friends. This requires that there be agreement on the correct 
structure of the tree among a user's friends. Friends do not need to 
have a view of the complete tree, just their children.

Another way to view the issue of agreement is that all operations that 
modify the friend's view of the tree need to be atomic across all 
friends that are involved in the modification. A message that passes 
through the tree must either see all of a change or none of it. When 
adding a member to the tree this is easy, the new member is added as a 
leaf node and just one node (its parent) needs to be modified.

When removing a node from the distribution tree there is more than one 
modification that needs to be made among the friends. To ensure that 
these modifications are atomic, I am using a tree generation number. 
Each broadcast message carries with it the generation of the 
distribution tree that should be used to propagate the message. When the 
tree is modified, the generation number is incremented. Friend nodes 
that are modified keep the old tree generation data around during the 
modification process and continue to use it for any messages that arrive 
with the old generation number. When the changes are complete, new 
messages are sent with the new generation number, making the new tree 
effective.

While this gives us atomic operations, it has the unfortunate property 
that all nodes need to have their generation number updated even if they 
are not involved in an update to the tree. To get around this, friends 
do not look up the exact generation number of messages to find forward 
information, but rather the youngest generation that is less than or 
equal to the generation number of the message. This lets us avoid 
updating the generation number with every friend.

Adrian