viff

changeset 729:cade54734d47

Moved documentation of program counter attribute.
author Martin Geisler <mg@daimi.au.dk>
date Thu, 24 Apr 2008 14:40:09 +0200
parents fa33d8c71256
children 1e9b0d1ad897
files doc/runtime.txt viff/runtime.py
diffstat 2 files changed, 43 insertions(+), 40 deletions(-) [+]
line diff
     1.1 --- a/doc/runtime.txt	Thu Apr 24 13:21:09 2008 +0200
     1.2 +++ b/doc/runtime.txt	Thu Apr 24 14:40:09 2008 +0200
     1.3 @@ -21,6 +21,49 @@
     1.4     .. autoclass:: viff.runtime.BasicRuntime
     1.5        :members:
     1.6  
     1.7 +      .. attribute:: BasicRuntime.program_counter
     1.8 +
     1.9 +         Whenever a share is sent over the network, it must be
    1.10 +         uniquely identified so that the receiving player known what
    1.11 +         operation the share is a result of. This is done by
    1.12 +         associating a *program counter* with each operation.
    1.13 +
    1.14 +         Keeping the program counter synchronized between all players
    1.15 +         ought to be easy, but because of the asynchronous nature of
    1.16 +         network protocols, all players might not reach the same parts
    1.17 +         of the program at the same time.
    1.18 +
    1.19 +         Consider two players *A* and *B* who are both waiting on the
    1.20 +         variables *a* and *b*. Callbacks have been added to *a* and
    1.21 +         *b*, and the question is what program counter the callbacks
    1.22 +         should use when sending data out over the network.
    1.23 +
    1.24 +         Let *A* receive input for *a* and then for *b* a little
    1.25 +         later, and let *B* receive the inputs in reversed order so
    1.26 +         that the input for *b* arrives first. The goal is to keep the
    1.27 +         program counters synchronized so that program counter *x*
    1.28 +         refers to the same operation on all players. Because the
    1.29 +         inputs arrive in different order at different players,
    1.30 +         incrementing a simple global counter is not enough.
    1.31 +
    1.32 +         Instead, a *tree* is made, which follows the tree of
    1.33 +         execution. At the top level the program counter starts at
    1.34 +         ``[0]``. At the next operation it becomes ``[1]``, and so on.
    1.35 +         If a callback is scheduled (see :meth:`schedule_callback`) at
    1.36 +         program counter ``[x, y, z]``, any calls it makes will be
    1.37 +         numbered ``[x, y, z, 1]``, then ``[x, y, z, 2]``, and so on.
    1.38 +
    1.39 +         Maintaining such a tree of program counters ensures that
    1.40 +         different parts of the program execution never reuses the
    1.41 +         same program counter for different variables.
    1.42 +
    1.43 +         The :func:`increment_pc` decorator is responsible for
    1.44 +         dynamically building the tree as the execution unfolds and
    1.45 +         :meth:`schedule_callback` is responsible for scheduling
    1.46 +         callbacks with the correct program counter.
    1.47 +
    1.48 +         See :ref:`program-counters` for more background information.
    1.49 +
    1.50     .. autoclass:: viff.runtime.Runtime
    1.51        :members:
    1.52  
     2.1 --- a/viff/runtime.py	Thu Apr 24 13:21:09 2008 +0200
     2.2 +++ b/viff/runtime.py	Thu Apr 24 14:40:09 2008 +0200
     2.3 @@ -450,46 +450,6 @@
     2.4          self._needed_data = {}
     2.5  
     2.6          #: Current program counter.
     2.7 -        #:
     2.8 -        #: Whenever a share is sent over the network, it must be
     2.9 -        #: uniquely identified so that the receiving player known what
    2.10 -        #: operation the share is a result of. This is done by
    2.11 -        #: associating a :term:`program counter` with each operation.
    2.12 -        #:
    2.13 -        #: Keeping the program counter synchronized between all
    2.14 -        #: players ought to be easy, but because of the asynchronous
    2.15 -        #: nature of network protocols, all players might not reach
    2.16 -        #: the same parts of the program at the same time.
    2.17 -        #:
    2.18 -        #: Consider two players *A* and *B* who are both waiting on
    2.19 -        #: the variables *a* and *b*. Callbacks have been added to
    2.20 -        #: *a* and *b*, and the question is what program counter the
    2.21 -        #: callbacks should use when sending data out over the
    2.22 -        #: network.
    2.23 -        #:
    2.24 -        #: Let *A* receive input for *a* and then for *b* a little
    2.25 -        #: later, and let *B* receive the inputs in reversed order so
    2.26 -        #: that the input for *b* arrives first. The goal is to keep
    2.27 -        #: the program counters synchronized so that program counter
    2.28 -        #: *x* refers to the same operation on all players. Because
    2.29 -        #: the inputs arrive in different order at different players,
    2.30 -        #: incrementing a simple global counter is not enough.
    2.31 -        #:
    2.32 -        #: Instead, a *tree* is made, which follows the tree of
    2.33 -        #: execution. At the top level the program counter starts at
    2.34 -        #: ``[0]``. At the next operation it becomes ``[1]``, and so on.
    2.35 -        #: If a callback is scheduled (see :meth:`schedule_callback`) at
    2.36 -        #: program counter ``[x, y, z]``, any calls it makes will be
    2.37 -        #: numbered ``[x, y, z, 1]``, then ``[x, y, z, 2]``, and so on.
    2.38 -        #:
    2.39 -        #: Maintaining such a tree of program counters ensures that
    2.40 -        #: different parts of the program execution never reuses the
    2.41 -        #: same program counter for different variables.
    2.42 -        #:
    2.43 -        #: The :func:`increment_pc` decorator is responsible for
    2.44 -        #: dynamically building the tree as the execution unfolds and
    2.45 -        #: :meth:`schedule_callback` is responsible for scheduling
    2.46 -        #: callbacks with the correct program counter.
    2.47          self.program_counter = [0]
    2.48  
    2.49          #: Connections to the other players.