[viff-devel] [issue80] Broadcast

[Janus Dam Nielsen]

New submission from Janus Dam Nielsen :

I would like to see a broadcast method in the Runtime class. The 
purpose of the broadcast method should be to distribute a public value 
among all parties (or some subset of parties).

A case: All parties in a computation needs to read a value from 
standard in, and it is a different value for each party. We want to 
tell the value to everybody else.

An example use could be like the input method:
a,b,c = runtime.broadcast([1,2,3], value)

Similarly, broadcast can be used in a conditional if only some subset 
of parties wants to distribute a value.

--
assignedto: mg
messages: 310
nosy: jdn, mas, mg
status: chatting
title: Broadcast
type: wish


VIFF Issue Tracker 


___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

Re: [viff-devel] [issue80] Broadcast

[Ivan Bjerre Damgård]

It can definitely be useful to have a broadcast method, for instance  
to complete the implementation of the asynchronous maliciously secure  
protocol, we will need broadcast.


But one needs to be careful about what kind of security we want. There  
is a whole jungle of protocols, depending on whether it is  
unconditional or computational security, synchronous or asynchronous  
network, and what number of players you assume can be corrupt. I think  
a protocol of Bracha has in fact already been implemented in VIFF


regards, Ivan

Quoting Janus Dam Nielsen :



New submission from Janus Dam Nielsen :

I would like to see a broadcast method in the Runtime class. The
purpose of the broadcast method should be to distribute a public value
among all parties (or some subset of parties).

A case: All parties in a computation needs to read a value from
standard in, and it is a different value for each party. We want to
tell the value to everybody else.

An example use could be like the input method:
a,b,c = runtime.broadcast([1,2,3], value)

Similarly, broadcast can be used in a conditional if only some subset
of parties wants to distribute a value.

--
assignedto: mg
messages: 310
nosy: jdn, mas, mg
status: chatting
title: Broadcast
type: wish


VIFF Issue Tracker 


___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk



___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

Re: [viff-devel] [issue80] Broadcast

[Mikkel Krøigård]

Citat af Ivan Bjerre Damgård :

It can definitely be useful to have a broadcast method, for instance  
to complete the implementation of the asynchronous maliciously  
secure protocol, we will need broadcast.


But one needs to be careful about what kind of security we want.  
There is a whole jungle of protocols, depending on whether it is  
unconditional or computational security, synchronous or asynchronous  
network, and what number of players you assume can be corrupt. I  
think a protocol of Bracha has in fact already been implemented in  
VIFF


Indeed it has. It's located in the active runtime (active.py).
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

Re: [viff-devel] [issue80] Broadcast

[Janus Dam Nielsen]

In the simple case I want to shout out a number to everybody, even  
somebody who is eavesdropping.


--
Janus


Den 10/03/2009 kl. 12.23 skrev Ivan Bjerre Damgård:

It can definitely be useful to have a broadcast method, for  
instance to complete the implementation of the asynchronous  
maliciously secure protocol, we will need broadcast.


But one needs to be careful about what kind of security we want.  
There is a whole jungle of protocols, depending on whether it is  
unconditional or computational security, synchronous or  
asynchronous network, and what number of players you assume can be  
corrupt. I think a protocol of Bracha has in fact already been  
implemented in VIFF


regards, Ivan

Quoting Janus Dam Nielsen :



New submission from Janus Dam Nielsen :

I would like to see a broadcast method in the Runtime class. The
purpose of the broadcast method should be to distribute a public  
value

among all parties (or some subset of parties).

A case: All parties in a computation needs to read a value from
standard in, and it is a different value for each party. We want to
tell the value to everybody else.

An example use could be like the input method:
a,b,c = runtime.broadcast([1,2,3], value)

Similarly, broadcast can be used in a conditional if only some subset
of parties wants to distribute a value.

--
assignedto: mg
messages: 310
nosy: jdn, mas, mg
status: chatting
title: Broadcast
type: wish


VIFF Issue Tracker 


___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk



___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk


___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

Re: [viff-devel] [issue80] Broadcast

[Ivan Bjerre Damgård]

Quoting Janus Dam Nielsen :

In the simple case I want to shout out a number to everybody, even  
somebody who is eavesdropping.


But secrecy of what you shout is not the real problem. The problem is  
to make sure everyone agrees on what was said. This is not obvious in  
the case where people may not follow the protocol. For instance, if  
you want a solution that does not depend on computational assumptions,  
then if a third or more of the players are corrupt, then there is NO  
solution.


Think of 3 players A,B and C, where A wants to broadcast a message,  
say 0 or 1. One player may be corrupt. So A is supposed to send a bit  
b to both B and C. Say B hears 0 from A. He doesn't know if A said the  
same to C. He can ask C what he heard, but if C says "A said 1 to me",  
there is no way to tell if A or C is lying..


regards, Ivan




--
Janus


Den 10/03/2009 kl. 12.23 skrev Ivan Bjerre Damgård:

It can definitely be useful to have a broadcast method, for  
instance to complete the implementation of the asynchronous  
maliciously secure protocol, we will need broadcast.


But one needs to be careful about what kind of security we want.  
There is a whole jungle of protocols, depending on whether it is  
unconditional or computational security, synchronous or  
asynchronous network, and what number of players you assume can be  
corrupt. I think a protocol of Bracha has in fact already been  
implemented in VIFF


regards, Ivan

Quoting Janus Dam Nielsen :



New submission from Janus Dam Nielsen :

I would like to see a broadcast method in the Runtime class. The
purpose of the broadcast method should be to distribute a public value
among all parties (or some subset of parties).

A case: All parties in a computation needs to read a value from
standard in, and it is a different value for each party. We want to
tell the value to everybody else.

An example use could be like the input method:
a,b,c = runtime.broadcast([1,2,3], value)

Similarly, broadcast can be used in a conditional if only some subset
of parties wants to distribute a value.

--
assignedto: mg
messages: 310
nosy: jdn, mas, mg
status: chatting
title: Broadcast
type: wish


VIFF Issue Tracker 


___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk



___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk


___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk



___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

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

[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
waiting calls and will trigger our process_deferred_queue method.

And voilá -- no hacking of the Twisted source needed.

I'm not sure but LoopingCall._reschedule() looks more like it
schedules the calls at certain tick, not as soon as possible after the
interval is elapsed. This might not cost too much time but still
doesn't feel very elegant. Furthermore, setting the interval very low
leads to high CPU usage when waiting. Again, this is not too bad but
not elegant either. The same applies if using reactor.callLater()
directly.


A looping call is just a higher level wraper for doing

  def reschedule(func):
func()
reactor.callLater(interval, reschedule, func)

  reschedule(func)

It will execute the function when the (now + interval) time has been
reached and when the control flow returns to the reactor's event loop.
We probably wont need the extra logic in a looping call, so we can just
let the function reschedule itself like above.


That's what I meant with calling reactor.callLater() directly.


If we do this with an interval of 0, then the function will be called on
each iteration through the reactor's event loop -- just like your
loopCall I believe?


Not exactly because it also sets the timeout of the select call to 0
leading to 100% CPU usage while when we are waiting.


diff -r e2759515f57f viff/runtime.py
--- a/viff/runtime.py   Thu Mar 05 21:02:57 2009 +0100
+++ b/viff/runtime.py   Fri Mar 06 13:43:14 2009 +0100
@@ -306,6 +306,8 @@
 deferred = deq.popleft()
 if not deq:
 del self.incoming_data[key]
+# just queue
+self.factory.runtime.queue_deferred(deferred)

Why is this done?

At this time, we shouldn't call the callbacks because we might recurse
into selectreactor.doSelect(). However, we want to know which
deferreds are ready so we can call deferred.callback() later.


Uhh, this sounds a bit dangerous -- do we know exactly which Deferreds
we can invoke callback on and which we cannot? As I remember, we invoke
callback in a couple of other locations, is that safe?


Yes, it is safe because the callback is called only once. When the data 
arrives, the Deferreds are paused, appended to the queue, and the 
callback is called. The Deferres in the queue are unpaused and removed 
in process_deferred_queue(). As far as I know you can pause and unpause 
Deferreds as you like.



If that doesn't matter, then I think this would be faster:

  queue, self.deferred_queue = self.deferred_queue, []
  map(Deferred.unpause, queue)

My idea is that looping over the list with map is faster than
repeatedly popping items from the beginning (an O(n) operation).

But map() still would need O(n) time because that is the nature of
calling a function n times, isn't it? Maybe the function calls are
optimized but the code in the function still is called n times.


Each pop(0) call is an O(n) operation, so we get O(n^2) here -- it is an
expensive way to loop through a list. And now that I look at it, using
map will still unpause the Deferreds in the order as you added them.


OK, I wasn't aware that pop(0) is O(n), but I still think that the
complexities should be added resulting in running time O(n) again. Using 
a linked list would be more reasonable, of course.



The difference is then that anything added to the queue as a result of
the unpause calls will be processed the next time the code is called.


Yes, and the Deferreds in the queue previously would wait. I considered 
it to be more safe if the Deferreds are processed in the order they arrive.



A question springs to my mind: calling

  reactor.runUntilCurrent()
  reactor.doIteration(0)

is the same as calling

  reactor.iterate(0)

and the documentation for that method says:

  [...] This method is not re-entrant: you must not call it recursively;
  in particular, you must not call it while the reactor is running.

How does your code ensure that we only call myIteration when we're
not in a call made by the reactor? And could we simply call
reactor.iterate instead?

We actually call it recursively but it should be reentrant if it's not
called from doIteration(). doIteration() is a the same as
select.doSelect(), which certainly is not reentrant. We however call
it from the loop call (process_deferred_queue()) after doIterate().

Calling reactor.iterate() is not enough because it doesn't call
process_deferred_queue().


So if we call reactor.iterate and then runtime.process_deferred_queue as

  reactor.callLater(0, reactor.iterate)
  reactor.callLater(0, runtime.process_deferred_queue)

we should be fine? They would then both run one after another just as
soon as the event loop is rea

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

[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 judge the idea is to go ahead and do it.


Note that Alexandra is committed to using a non-trivial amount of  
resources on developing VIFF and related software. Although this may  
not mean that lots of man-hours are available just now, it might be  
possible that they could help you.
It may also be more efficient that one guy does it in the first  
iteration, I'll leave this up to you.


Note that myself, Martin and Jakob will not be at the meeting  
Thursday. Maybe we should postpone the meeting until next week?


regards, Ivan



___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

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

[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 the idea is to go ahead and do it.


OK, i will start doing it next Monday.

Note that Alexandra is committed to using a non-trivial amount of 
resources on developing VIFF and related software. Although this may not 
mean that lots of man-hours are available just now, it might be possible 
that they could help you.
It may also be more efficient that one guy does it in the first 
iteration, I'll leave this up to you.


Since it doesn't seem that complicated to me, I will try it on my own 
first. But I keep that in mind for the case that I'm wrong.


Note that myself, Martin and Jakob will not be at the meeting Thursday. 
Maybe we should postpone the meeting until next week?


Me neither, I'm on holidays until the weekend. Therefore, I would agree 
to postpone the meeting.


Best regards,
Marcel

___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk