pointer tracking in distributed environment

dufrp@oricom.ca dufrp@oricom.ca
Sun, 13 Jun 1999 15:03:55 +0500


Hi, I have been reading dmos.pointers.pdf paper called:
"Where has all pointers gone: a story of pointer tracking in
distributed environment". I don't have the URL near but it
should be easy to find on the TODO page of wiki, where Tril
suggest we make a summary of all papers on that site.

I don't fully understand it, but I think that I am able to give you
enough information to let you decide if you want to read this
9 pages paper.

This is based on 4 messages that you send to the home of an object
(as I understand it, their pointers contains the home node, but
that's the kind of detail I don't quite understand yet):
-Hey, I have send a pointer to object O to Node N! (s message)
-Hey, I (node N), received a pointer to object O!  (r message)
-Hey, I (node N) just created a new pointer to object O!  (+ message)
-Hey, I (node N) just destroyed a pointer to object O!    (- message)

 Note (an r message is a kind of + message, you just send a + message
if you make a copy of that pointer, when you get rid of the copy you
send a - message, and when you get rid of the original pointer (that
you acknowledge having received by sending a r message to the home
node of the corresponding object) you send a - message. Hope this
note make things clearer.

Now there is no need to hurry to send messages as soon as events
happend.  There is no problem if the home node of an object receive a
message that 'node B have received a pointer to object o' before
receiving a message of node A telling that it 'has send a pointer to o
to node B'.

The home node of an object o must keep track for each node N received
in a message, a set of kind of message received. The paper give some
'common sense' rules on what kind of message is legal in some state.
Example, at initialization, the set of messages is empty, and the
only legal thing that can happen is for the home node to create an
initial pointer to the object (+ message).

So suppose you want to know if other nodes will be affected if you
destroy the object homed here, you go to the list of nodes for the
object (other than here, the home node), and check that none of these
node have any pointer to it, that is check in the set of messages
kinds of that node if there is a r message with no matching -
message, and if there is a + message without matching - message.
This can be done with two counters, one called in transit counter,
that you increment when you receive a 's'end message and decrement
when you receive a 'r'eceive message, and an other reference counter
that you increment on 'r'eceive message and + message, and decrement
on any - message. (This is from 'memory', so I hope I am right).

Now the paper also give an algorithm to let you migrate an object to
an other home node. For this each node must have a list of relocated
objects (there is a way to know that everyone have updated their
pointers and that an object can be removed from this list). This list
simply associate the old pointer to the new one (one such entry for
each object in the process of migrating). Also, the home node must
have a list of nodes that have to update. I won't enter in details
because I don't understand well enough yet, but basically it is using
the 4 messages we talked. I invite people interested to read the
paper.

Security (like what happens if messages are not correctly transmitted
because let's say a virus destroyed the tables) issues are not
treated in this paper.

Net-Tamer V 1.11X - Registered