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

[Mikkel Krøigård]

Quoting Ivan Bjerre Damgård <ivan at cs.au.dk>:

> Folks,
>
> I think your precious time is better spent on figuring out a brilliant
> solution to handling memory issues with VIFF, than on discussions about what
> "asynchronous" really means :-)
Well if you are calling it asynchronous, then it had better BE asynchronous :)

However, the focus is on handling the memory issue.

While you can save memory by splitting up the computation, I would  
much prefer it if you could write code like the stuff Tomas wrote  
without thinking about memory-saving tricks. Ideally, it should be  
completely straightforward and without tricks.

We just discussed if the Twisted reactor could somehow get control  
before we are done scheduling. In the case below, we would like to  
start getting some of the older stuff done before piling on new  
computations, and if the reactor could just send and receive once in a  
while, then maybe that could happen.

However, Twisted is apparently not the kind of scheduling system we  
would need for that. I guess my question for this list is if my  
understanding here is correct.

Martin told me that there may be a way to reduce the memory usage by  
minimizing the size of deferreds, and that this is already mentioned  
in the bug tracker. However, add an extra zero to the number of  
iterations and we're back to square one.

> regards, Ivan
>
> Quoting Marcel Keller <mkeller at cs.au.dk>:
>
>>> 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).
>>
>> There's a pitfall here: What do you mean with "share"? At this point, the
>> shares are only scheduled to be sent, the real communication doesn't occur
>> until step 3. The FAQ of Twisted says so:
>> http://twistedmatrix.com/trac/wiki/FrequentlyAskedQuestions#WhydoesittakealongtimefordataIsendwithtransport.writetoarriveattheothersideoftheconnection
>> Since I discussed this issue last week with Martin, I also looked at the
>> source of Twisted 8.1.0 to confirm it.
>>
>>> 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".
>>
>> As Mikkel wrote, I had the same issues and I solved them by calling parts of
>> my code (one AES round at a time) as a callback of some trigger shares.
>> _______________________________________________
>> viff-devel mailing list (http://viff.dk/)
>> viff-devel at viff.dk
>> http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
>>
>
> _______________________________________________
> viff-devel mailing list (http://viff.dk/)
> viff-devel at viff.dk
> http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
>