changeset 873:7837ad6fc492

Motivation for VIFF.
author Martin Geisler <>
date Sun, 03 Aug 2008 22:25:12 +0200
parents 5a18ce0b0ef0
children 6d1e5727cfb6
files doc/history.txt
diffstat 1 files changed, 63 insertions(+), 0 deletions(-) [+]
line diff
     1.1 --- a/doc/history.txt	Sun Aug 03 20:40:18 2008 +0200
     1.2 +++ b/doc/history.txt	Sun Aug 03 22:25:12 2008 +0200
     1.3 @@ -42,3 +42,66 @@
     1.4  might still refer to it as the "SCET comparison" on the mailing list.
     1.6  .. _SCET:
     1.7 +
     1.8 +
     1.9 +Problems and solutions
    1.10 +----------------------
    1.11 +
    1.12 +While the foundation for the sugar beet auction was being programmed
    1.13 +in Java in the SIMAP project, Martin began experimenting with a new
    1.14 +architecture in Python. The Java implementation was big with about
    1.15 +8,500 lines of code for some 130 classes and interfaces and while
    1.16 +implementing the comparison protocol it had become clear that there
    1.17 +were a number of problems with its design.
    1.18 +
    1.19 +Problems
    1.20 +""""""""
    1.21 +
    1.22 +We knew from the beginning that it was important to run things in
    1.23 +parallel to use the bandwidth in the most efficient way. So a concept
    1.24 +of "batch jobs" was introduced for grouping parallel operations
    1.25 +together. The problem was that one had to write code for dealing with
    1.26 +combinations of different batch jobs so when implementing a new
    1.27 +operation (such as a comparison protocol) one had to define how a
    1.28 +batch job would look like for the new operation and how the batch job
    1.29 +would be combined with all other types of batch jobs. This severely
    1.30 +limited the modularity since every new piece of code needed to know
    1.31 +about every old piece.
    1.32 +
    1.33 +Another problem was that although the high lever interface manipulated
    1.34 +secret shared values as first class objects, the runtime system did
    1.35 +not. Instead the values were kept in a ``HashMap`` and referenced
    1.36 +using integers by the internal runtime code. So extending the runtime
    1.37 +system could not be extended in terms of itself, akin to how the
    1.38 +earliest compilers had to be written in assembler instead of a higher
    1.39 +level language.
    1.40 +
    1.41 +
    1.42 +Solutions
    1.43 +"""""""""
    1.44 +
    1.45 +The `Twisted network framework`_ turned out to be a both simple and
    1.46 +elegant solution to the first problem. The key is the
    1.47 +:class:`Deferred` class which allows the code to treat all operations
    1.48 +equal: they all take deferred inputs and return a deferred output. All
    1.49 +time is spend either working on local data or waiting for more inputs
    1.50 +to arrive over the network. When data arrives the associated callbacks
    1.51 +are immediately executed without regard to what kind of operation they
    1.52 +are. This uniform interface means that as many operations as possible
    1.53 +are executed in parallel. Extending the runtime with new operations is
    1.54 +also much simpler since the framework will take care of running things
    1.55 +in parallel -- new operations work the same as old "primitive"
    1.56 +operations.
    1.57 +
    1.58 +It is interesting to note that this design relies heavily on the use
    1.59 +of function pointers, something which Java lacks. Python also supports
    1.60 +anonymous functions (lambda expressions) which are very convenient
    1.61 +with this programming style. It might be possible to design a similar
    1.62 +system in Java by using objects to represent the callbacks, but it
    1.63 +would probably be much more cumbersome.
    1.64 +
    1.65 +The problem with representing secret shared values by integers
    1.66 +internally instead of objects could of course have been solved equally
    1.67 +well in Java.
    1.68 +
    1.69 +.. _Twisted network framework: