On Mon, Aug 4, 2008 at 5:26 PM, John Hendrie <[EMAIL PROTECTED]> wrote:
> Thanks for the explanation.
>
> I have another question about sequence numbers. What happens when the
> sequence number overflows? I can't see anything in the code that deals with
> wrapping. Does Drip assume that the sequence number will never wrap?
>
> Thanks,
> John
>
>
> On Mon, Aug 4, 2008 at 9:16 AM, Philip Levis <[EMAIL PROTECTED]> wrote:
>
>>
>> On Jul 25, 2008, at 11:28 AM, John Hendrie wrote:
>>
>> Hi,
>>>
>>> Is Drip designed so one node changes the variable and the rest listen or
>>> is it designed so that every node in the network can change the shared
>>> variable?
>>>
>>> I ask because of the way the sequence number is generated in
>>> DisseminatorP.nc:
>>>
>>> /* Increment the counter and append the local node ID. */
>>> seqno = seqno >> 16;
>>> seqno++;
>>> if ( seqno == DISSEMINATION_SEQNO_UNKNOWN ) { seqno++; }
>>> seqno = seqno << 16;
>>> seqno += TOS_NODE_ID;
>>>
>>> Doesn't this mean that a node with the highest TOS_NODE_ID will force
>>> other nodes in the network to ignore valid changes made by nodes with
>>> smaller IDs because it will always have the largest seqno?
>>>
>>
>>
>> You have the significant bits reversed. Dissemination needs to have
>> eventual consistency, such that in a connected network all nodes converge on
>> the same value. There's a race condition, where two nodes that have version
>> V both decide to update the value to version V+1. This could lead to a
>> problem where all nodes think they have the same version but some have one
>> value and others have a second value.
>>
>> Drip and DIP solve this problem by making version numbers 32 bits, where
>> the least significant 16 bits are the node ID. That way, if two nodes A and
>> B both increment to version V+1, then in reality the versions are
>>
>> (((V + 1) << 16) + A) and
>> (((V + 1) << 16) + B)
>>
>> Whichever (A or B) has a larger node ID will win the tie, and the network
>> will converge on a consistent value. However, as the node ID is the least
>> significant 16 bits, then if the node with a lower ID increments the version
>> number to V + 2, it will win over any V + 1.
>>
>> Phil
>>
>
>
_______________________________________________
Tinyos-help mailing list
[email protected]
https://www.millennium.berkeley.edu/cgi-bin/mailman/listinfo/tinyos-help
