[tor-dev] Detailed algorithm

[Ola Bini]

Hi,

Thanks for the review.

> Maybe we also need to exclude USED_GUARDS from these two lists?
Good point, we should definitely do that.

> Not sure if this is part of this algorithm, or it's actually another helper
> algorithm that is called when a consensus arrives. I feel it might be cleaner
> if we do it as a separate algo, but we can proceed like this as well since it's
> not too confusing.
We can probably do that. The reason I put it in here is because it
works on the same data structures that are used for the rest of the algorithm.

> >   - STATE_PRIMARY_GUARDS:
> >     - return each entry in PRIMARY_GUARDS in turn
> >       - mark each entry as "unreachable" if algorithm doesn't terminate
>
> So IIUC the "algorithm" referenced here is _not_ the algorithm that we are
> describing right now (let's call it ALGO_CHOOSE_GUARD). Instead the "algorithm"
> here is the _caller of ALGO_CHOOSE_GUARD_, which is the algorithm responsible
> for creating circuits, testing whether they work and reporting the results back
> to CHOOSE_GUARD_ALGO (let's call this other algorithm ALGO_BUILD_CIRCUIT).
We should probably clarify it. But yes, the algorithm referenced is
ALGO_CHOOSE_GUARD. ALGO_CHOOSE_GUARD will terminate if
ALGO_BUILD_CIRCUIT successfully builds a circuit.

> Also, do PRIMARY_GUARDS go into TRIED_GUARDS and count against our
> thresholds?
Yes, they probably should. Will change it.

> In general, I think we should make the context of this algorithm
> (ALGO_CHOOSE_GUARD) a bit clearer, so that we know when "Start of algorithm" is
> supposed to run, and when "End of algorithm" is supposed to run.
>
> Because for example one could think here that in an asynchronous setting, when
> we try a entry from USED_GUARDS and find out whether the circuit succeeded or
> not, we need to run the algorithm from the beginning including the "Start of
> algorithm" step. Whereas if I understand correctly you assume that we will just
> drop in and continue exactly from this point.
Yes, exactly. "Start of algorithm" sets up the data structures
etc. "Each iteration of algorithm" will be called repeatedly until we
get failure or a working guard, and at that point "End of algorithm"
will be run. I can make it clearer.

> I feel that this confusion is caused by the ALGO_CHOOSE_GUARD algorithm being
> pseudo-asynchronous. To address this I suggested additional states for when we
> are waiting for the results of a circuit construction, but I agree that this
> might complicate things too much.
I can do that - not sure if it would clarify things. That state is
entered every time the word "return" is used in "Each iteration of
algorithm". Once "Each iteration of algorithm" is called again, it
will continue at the same place. Not sure what you consider pseudo
asynchronous about that. =)

> Finally, what kind of statistics and measurements does the simulator conduct?
>
> For example, I can think of reachability related stats like:
>
>  * Time (or number of guards) till we manage to build first circuit
>  * Time till we manage to recover from flaky network
>
> and I can also think of security related stats like:
>
>  * Number of guards we tried before succeeding first circuit
>  * Number of guards we exposed ourselves to after time t
Haven't thought abou that yet - we currently only have the things that
were already in the simulator code, which primarily checks how many
failed vs successful guards we got. These other heuristics look
interesting to check as well.

Cheers
--
 Ola Bini (https://olabini.se)

 "Yields falsehood when quined" yields falsehood when quined.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 931 bytes
Desc: not available
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20160209/6a898ef6/attachment.sig>