[net2-wg] Proposal for dissemination structure and interfaces

[Philip Levis]

On Dec 17, 2005, at 3:17 AM, Omprakash Gnawali wrote:

>
>> On Dec 16, 2005, at 6:52 PM, Omprakash Gnawali wrote:
>>
>>> The proposed dissemination interface requires that the key is
>>> determined at compile time. If I know that I need to disseminate
>>> exactly this particular key, this interface works great. What if  
>>> I do
>>> not know the number of keys I will need to disseminate ?
>>>
>>
>> Since you have to allocate the storage for each value in a key/value
>> pair, dynamic key creation would require dynamic allocation. What's a
>> situation where you would need dynamically generated keys?
>
>
> We would need this capability if we implement something like TinyDB
> where we think of each query as a key. We would not know the number of
> keys in advance but I would want my queries to be reliably delivered
> to each node in the network. Am I thinking about the wrong application
> for dissemination ?

The example application you give of dissemination is right on.

The one issue that comes up is the actual allocation. In TinyDB's  
case, it dynamically allocates space for a query on the node. The  
issue is that allocation failure is an event internal to a node. The  
only feedback a user gets is that the query doesn't start running.  
Moreover, depending on the temporal ordering and size of other memory  
objects, fragmentation might cause the query to be successfully  
allocated on some nodes and not on others. The end result is that  
dissemination becomes unreliable.

That being said, I think it's possible to layer a dynamic (and  
therefore possibly unreliable) approach on top of this static  
mechanism. The disseminated value could be a reasonably sized array  
of running query ids. When a user cancels a query, a query ID is  
removed, and when a user starts a new query, an ID is added. It's  
then up to a higher-level dissemination system --- with dynamic  
allocation, etc. --- to take care of the query propagation.

Gil and I talked a bit about disseminating variable-length objects:  
he was concerned with a very similar circumstance, queries for the  
Nucleus management system. Gil, do you want to talk about this a bit?

Phil

-------

"We shall not cease from exploration
And the end of all our exploring
Will be to arrive where we started
And know the place for the first time."

- T. S. Eliot,  'Little Gidding'