Re: [Roll] do we need a dominating set?

[Philip Levis <pal at cs.stanford.edu>]

On Nov 18, 2009, at 12:07 AM, Pascal Thubert (pthubert) wrote:

> Hi Stephen:
>
> I've seen evidence that " trickle performs fine (well)" for  
> propagating network invariants.
> The state of a node being NOT a network invariant, I see strong  
> evidence that we are using a very good hammer for pulling screws.
> The sequenceNb being a network invariant in an instance, my proposal  
> seems to be using trickle for what it is good at.

"Propagating" is probably the wrong word here, as Trickle's events can  
be local (e.g. local repair).

Generally, Trickle's mechanisms each have advantages for a variety of  
uses:

  1) The exponential timer makes it efficiently maintaining eventual  
consistency
  2) The suppression constant makes it efficiently support broadcast  
operations.
  3) Its randomization helps it support broadcasts, and also evenly  
distributes load.

Etc.

There is always a tension between maintenance and discovery. You want  
to get more information from the active parents/routes/etc., yet do  
not want this to preclude getting information from other nodes who may  
happen to be better options.

It seems to me that the protocol specification allows this already. If  
some higher-level dominating set algorithm (which *clearly* should not  
be in the draft) can improve the protocol, then the fact that  
transmissions MAY increment C is the way to handle this. If a node  
that is a member of this hypothetical dominating set doesn't increment  
C when it hears messages, it isn't suppressed. So  I don't see why the  
specification needs to change.

Phil