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

[Tord Ingolf Reistad]

I have been thinking about the same things when I was doing my project. 
I do not know how VIFF works, but it would be interesting to know.

My thinking about this problem is that if you are going to have a very 
large MPC program using the same ideas as VIFF, then you need to:

1) Have at least two threads, one thread that creates the deferred 
elements and one that handles incoming messages (from other players). A 
third thread which is invisible to the program is the tread handling 
incoming messages and putting them in a buffer.

2)Have algorithms that create more elements if there is room in the 
stack. (This can be done by the thread creating the deferred elements, 
which has a counter of how many elements that are created, the tread 
pauses if it reaches a threshold when creating new deferred elements. 
The tread continues when the number of deferred elements is below the 
threshold again).

3)Have algorithms that destroy already used elements that are not needed 
any more. (This can be done by the tread handling incoming shares. Each 
share need a list of deferred elements that are connected to it and when 
a deferred element is computed it is deleted from the list, when the 
list is empty the element is deleted).

4)Have algorithms that delay incoming shares if these shares are not 
created yet.

5)Have algorithms checking that someone is not just clogging up the 
incoming shares stack with dummy messages.

2extra)When you delete messages because no new deferred elements need 
them then you can get situations in big programs that an element is 
deleted, but it is suddenly needed far from where it was first created.

Tord

T.Toft at cwi.nl wrote:
> 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".
> 
> 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.
> 
> 
> Regards,
>   Tomas
> 
> 
> 
> _______________________________________________
> viff-devel mailing list (http://viff.dk/)
> viff-devel at viff.dk
> http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
>