[viff-devel] VIFF and large scale programs -- is VIFF really asynchronous?

[Mikkel Krøigård]

Quoting T.Toft at cwi.nl:

>
> Hi all,
>
>
> A really unpleasant thought has occurred to me: Is VIFF really properly
> asynchronous? (Yes, this question is intended to provoke you into thinking
> about the issue below. Of course VIFF is asynchronous in the sense that
> there are no rounds.)
>
>
>
> If I understand/remember correctly, VIFF is 100% single threaded. This
> means that if we have a small program:
>
> x, y = runtime.shamir_share([1, 2], Zp, input)
> z = x*y
> for i in xrange(100):
>   z=z*z
>
> 1) We first share two values (returning immediately).
>
> 2) We start doing a lot of multiplications. However, as we don't have
> the actual shares yet, we just get deferreds.
>
> 3) Once the for-loop terminates, we return control to the
> surroundings. At this point we notice that the shares of x and y are
> there and start the actual multiplication protocols.
>
>
>
> Is my interpretation above correct? Because if it is, then this really
> explains the memory issues I've been seeing. And more importantly, it
> tells us how to actually use VIFF for large-scale computation: put in
> explicit "stops".
Yes, that is how it works. Martin tells me that putting in "stops" is  
indeed the way to handle it, and apparently Marcel has done this  
successfully.

However, I don't see how this makes VIFF less asynchronous. We are  
forcing it to synchronize to avoid some memory usage, but that in  
itself does not make it synchronous.

> The problem is that new python objects are created in each iteration of
> the loop, but the program does not try to get rid of any of the old ones
> by actually processing them. With 100 iterations, this is not a big deal,
> but if this is replaced by 10000 or 1000000 (which is not unreasonable),
> it really becomes a problem.
Indeed. I suppose that is the cost of handling it with deferreds,  
although I can imagine that other ways of implementing it would also  
run into problems if you carefully scheduled enough multiplications  
that depend on each other.