Re: [viff-devel] Mystery of the quadratic running time solved?

2009-03-10 Thread Marcel Keller
Hi Ivan, I just wanted to say that I think it would be great if you would implement a version of your proposed two-threaded solution. I do not have a firm grasp of all the programming details, but it does seem that the overall idea is converging, and that some time soon the best way to judge

Re: [viff-devel] Mystery of the quadratic running time solved?

2009-03-10 Thread Ivan Bjerre Damgård
Marcel, I just wanted to say that I think it would be great if you would implement a version of your proposed two-threaded solution. I do not have a firm grasp of all the programming details, but it does seem that the overall idea is converging, and that some time soon the best way to jud

Re: [viff-devel] Mystery of the quadratic running time solved?

2009-03-10 Thread Marcel Keller
I think we would get the same result if we started a LoopingCall that executes process_deferred_queue with an interval of, say, 100 ms: http://twistedmatrix.com/documents/8.2.0/api/twisted.internet.task.LoopingCall.html This should work since the runUntilCurrent method runs through the waitin

Re: [viff-devel] Mystery of the quadratic running time solved?

2009-03-09 Thread Martin Geisler
Marcel Keller writes: >> You're talking about this two-threaded solution as if it is something >> that exists and will solve all our problems... > > No, for now, it's just an imagination in my mind, a proposal for the > next meeting, and a strong feeling that it's the right way to do it. Yeah, I

Re: [viff-devel] Mystery of the quadratic running time solved?

2009-03-08 Thread Marcel Keller
You're talking about this two-threaded solution as if it is something that exists and will solve all our problems... No, for now, it's just an imagination in my mind, a proposal for the next meeting, and a strong feeling that it's the right way to do it. But I still haven't seen it, and I wo

Re: [viff-devel] Mystery of the quadratic running time solved?

2009-03-08 Thread Martin Geisler
Marcel Keller writes: Indeed we did not know (well I didn't) back then that the data was not sent immediately by Twisted, and I was starting to think yesterday whether the hack would make a difference. Lucky for us, it apparently does :) >>> That is not the only problem. To fr

Re: [viff-devel] Mystery of the quadratic running time solved?

2009-03-08 Thread Marcel Keller
Indeed we did not know (well I didn't) back then that the data was not sent immediately by Twisted, and I was starting to think yesterday whether the hack would make a difference. Lucky for us, it apparently does :) That is not the only problem. To free the memory of the shares and to send out fu

Re: [viff-devel] Mystery of the quadratic running time solved?

2009-03-08 Thread Martin Geisler
Marcel Keller writes: >> I think we would get the same result if we started a LoopingCall that >> executes process_deferred_queue with an interval of, say, 100 ms: >> >> >> http://twistedmatrix.com/documents/8.2.0/api/twisted.internet.task.LoopingCall.html >> >> This should work since the runU

Re: [viff-devel] Mystery of the quadratic running time solved?

2009-03-08 Thread Marcel Keller
Wow, this is nice! I had sort of given up finding the cause of this :-( Thank you for looking at this, and just in time for my presentation at PKC in 10 days :-) You're welcome. :-) --- /usr/lib/python2.5/site-packages/twisted/internet/base.py 2008-07-29 22:13:54.0 +0200 +++ interne

Re: [viff-devel] Mystery of the quadratic running time solved?

2009-03-07 Thread Marcel Keller
That is not the only problem. To free the memory of the shares and to send out further shares, also the incoming shares must be processed as soon as possible. This is even trickier because incoming shares might trigger code that calls functions sending out data, which activates the Twisted reac

Re: [viff-devel] Mystery of the quadratic running time solved?

2009-03-07 Thread Martin Geisler
Marcel Keller writes: >> Indeed we did not know (well I didn't) back then that the data was >> not sent immediately by Twisted, and I was starting to think >> yesterday whether the hack would make a difference. Lucky for us, it >> apparently does :) > > That is not the only problem. To free the m

Re: [viff-devel] Mystery of the quadratic running time solved?

2009-03-07 Thread Martin Geisler
Marcel Keller writes: > Hello friends of VIFF, > > I've now run the benchmark of actively secure multiplications with > hyperinvertible matrices together with my hack. Here are my results > (column 1 and 2) compared to the results in the paper "Asynchronous > Multiparty Computation: Theory and Im

Re: [viff-devel] Mystery of the quadratic running time solved?

2009-03-06 Thread Mikkel Krøigård
Citat af Marcel Keller : Indeed we did not know (well I didn't) back then that the data was not sent immediately by Twisted, and I was starting to think yesterday whether the hack would make a difference. Lucky for us, it apparently does :) That is not the only problem. To free the memory

Re: [viff-devel] Mystery of the quadratic running time solved?

2009-03-06 Thread Marcel Keller
Indeed we did not know (well I didn't) back then that the data was not sent immediately by Twisted, and I was starting to think yesterday whether the hack would make a difference. Lucky for us, it apparently does :) That is not the only problem. To free the memory of the shares and to send ou

Re: [viff-devel] Mystery of the quadratic running time solved?

2009-03-06 Thread Mikkel Krøigård
Citat af Ivan Bjerre Damgård : Very interesting! So if things are as they seem here, the explanation for the strange behavior would be that the precomputing phase, being more involved than the online phase, is punished by Twisted (when unhacked). And this is of course not included in the

Re: [viff-devel] Mystery of the quadratic running time solved?

2009-03-06 Thread Ivan Bjerre Damgård
Very interesting! So if things are as they seem here, the explanation for the strange behavior would be that the precomputing phase, being more involved than the online phase, is punished by Twisted (when unhacked). And this is of course not included in the analysis in the paper. regards,

[viff-devel] Mystery of the quadratic running time solved?

2009-03-06 Thread Marcel Keller
Hello friends of VIFF, I've now run the benchmark of actively secure multiplications with hyperinvertible matrices together with my hack. Here are my results (column 1 and 2) compared to the results in the paper "Asynchronous Multiparty Computation: Theory and Implementation" (column 3 and 4):