-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA512
Hi,
https://gitweb.torproject.org/torspec.git/tree/dir-spec.txt#n2028
a random sample from recent votes:
grep 37.59.38.117 -A 3 *|grep Measured w Bandwidth=6869 Measured=7570 w Bandwidth=6869 Measured=15500 w Bandwidth=6869 Measured=18100 w Bandwidth=6869 Measured=30500
Tor says the median value is 15500
2015-08-10-16-00-00-consensus: w Bandwidth=15500
but the median of these 4 values is actually: (18100+15500)/2 = 16800 no?
Has tor a different definition of 'median' and simply takes always the second ordered measurement vote out of 4 votes or is there a bug in the spec or implementation?
On Mon, Aug 10, 2015 at 1:11 PM, nusenu nusenu@openmailbox.org wrote:
There's one misplaced throwaway sentence in dir-spec.txt:
" All ties in computing medians are broken in favor of the smaller or earlier item. "
We should bring this, and probably other things, into a "definitions" section earlier in dir-spec.txt. Patches welcome. ;)
Is there some implementation-specific reason not to use the standard mathematical definition of "median"? If not, I propose changing the implementation to become it.
-V
On Tue, Aug 11, 2015 at 2:44 AM Nick Mathewson nickm@alum.mit.edu wrote:
I think you are confusing the median with the mean:
https://en.wikipedia.org/wiki/Median https://en.wikipedia.org/wiki/Mean
Taking the median instead of the mean can be beneficial in situations where you have larger outliers in your data, which typically affect the mean very much.
-j
Virgil Griffith:
I mean the median.
From Wikipedia...
For example, if *a* < *b* < *c*, then the median of the list {*a*, *b*, *c*} is *b*, and, if *a* < *b* < *c* < *d*, then the median of the list {*a*, *b* , *c*, *d*} is the mean of *b* and *c*; i.e., it is (*b* + *c*) / 2.
-V
On Tue, Aug 11, 2015 at 9:29 PM John oneofthem@riseup.net wrote:
Virgil's absolutely right. Median as the "middle" value in a _sorted_ set is: - for odd number of data points, it's the middle one: set[N/2] - for even number of data points, it's the average of two in the middle: (set[N/2] + set[(N+1)/2]) / 2
Best regards, Maciej
On Tue, Aug 11, 2015 at 3:44 PM, Virgil Griffith i@virgil.gr wrote:
On Tue, 11 Aug 2015 13:44:48 +0000, Virgil Griffith wrote:
In the preceding paragraph wikipedia isn't that strict: 'the median is then usually defined to be the mean of the two middle values', and tor is unusual. :-)
Andreas
I looked into this.
Apparently Tor often uses the "low median", in cases where it needs to be a middle value, but an inbetween value is not allowed. This is chiefly for voting.
On Tue, Aug 11, 2015 at 10:49 PM Andreas Krey a.krey@gmx.de wrote:
On Wed, Aug 12, 2015 at 5:34 PM, nusenu nusenu@openmailbox.org wrote:
The correct fix here is to update the code documentation to define the functions as returning the low-median, and to update dir-spec.txt to say so too. I'd accept documentation patches like that.
Changing the code to return the mean of the two center elements from even arrays would break all authority voting, and wouldn't actually be useful.
If the authorities supply different values in the consensus, voting breaks.
Authorities using the low-median would supply one value, and authorities using the mean-median would supply another value. (Authorities typically run different versions of tor, and don't upgrade all at once.)
Breaking changes like this are typically negotiated among the authorities using numbered consensus methods. Once enough authorities support a new consensus method, it is activated during voting.
Rather than creating a new consensus method to implement mean-median, it's much easier to patch the documentation to specify low-median. (And I see no significant gain in changing from low-median to mean-median.)
I'd rather see bandwidth measurements become more accurate, for more relays, more of the time, than change how their median is defined.
Tim
Tim Wilson-Brown (teor)
teor2345 at gmail dot com pgp ABFED1AC https://gist.github.com/teor2345/d033b8ce0a99adbc89c5
teor at blah dot im OTR D5BE4EC2 255D7585 F3874930 DB130265 7C9EBBC7
-
Andreas Krey -
John -
Maciej Soltysiak -
Nick Mathewson -
nusenu -
Sebastian Hahn -
teor -
Virgil Griffith