[freehaven-dev] Another multicast paper -- nice model + use of IDA

[dmolnar@belegost.mit.edu]

Hi, 

Found yet another multicast paper. 
"IDA-Based Protocols for Reliable Multicast"
http://www.cs.technion.ac.il/users/hadas/PUB/AS2.ps.gz

Considers "reliable multicast" over an ATM network, in which

* There is one root node which is connected to a bunch of leaf nodes.

* The leaf nodes can talk back to the root node, but the root node
  can't tell which leaf node is saying what.

* Leaf nodes have no idea who other leaf nodes are; no leaf-to-leaf 
  communication. 

* Delivery of packets is "best effort" -- and packets die a lot.

Then the idea is to break up the message using IDA and keep sending
parts of it along until every leaf has enough to reconstruct. That is,
the paper aims at increasing reliability with minimum communication
overhead. 

The claim is  O(log n) phases of communication, with O(log m) messages. 
n = # of receivers
m = # of shares required to reconstruct file.

I haven't looked at the protocol or proofs yet. 

It strikes me that this is somewhat similar to our mixnet model for
broadcasts. The broadcasting servnet node is connected to all other 
servnet nodes ("leaves"). It would be possible to include a reply block
in each message just for ACKs and so on for that message; this wouldn't
identify the broadcasting node. The leaves don't know each other. And 
packets die a lot. 

I don't think it's something we'll do soon, but it may be worth looking at
later in order to add some kind of reliability to our mixnet broadcasts.
Plus we could rip off the model when we're doing security and efficiency
analysis...

Thanks, 
-David