frankmcsherry

I suspect you did not understand correctly? I just read their section 6, and they neither "just call it a limitation" (the section is three pages long, with several recommendations) nor invite anyone to sample the user base (this generally just focuses the privacy loss on the sampled people).

Which text were you reading that lead you to this conclusion?

While I like this work, the title may be misleading to people who think of "privacy loss" as something distinct from "differential privacy".

What they show is that as you use Apple's implementation, the differential privacy parameter grows (providing weaker guarantees as time passes). They don't show that they can bypass the mechanism and it's guarantees, just that Apple has rigged the implementation to decay the guarantees as you continue to use it (note: decay stops if you stop using Apple stuffs).

> The more changes get made, the more privacy the user has.

This is a minor, pedantic point, but what you really mean to say is "the closer the changes get to 50%, the more privacy the user has". If you change all results, then it is easy to flip them all back.

This distinction trips up several folks, where the research world initially believed (and some in official stats still believe[1]) that a part of privacy is literally not publishing the true answer (e.g. above: literally flip every output).

What you actually want is

    Pr[output | input] ~= Pr[output | input']

which may mean that you should leave things alone, which feels weird but is important.

[1]: Noise addition is a common way to obscure real-valued data, and some official stats bureaus have the ridiculous rule that "you always add noise, and you never add less than X in absolute value", leading to releases where you can be 100% confident that the true value is not in a range around the published number.

The coin flipping approach is called "Randomized Response" and dates back to the 60s.

https://en.wikipedia.org/wiki/Randomized_response

> On the other hand, hypercomputation has no physical basis. So what's the point of using it to model anything real? It's next to useless.

Plenty of mathematics does not "model anything real", but you may still want to understand it. The paper starts with an analogy to non-Euclidean geometry, which once "had no physical basis", until we learned more about the universe and found that it did.

Mathematics isn't a pitch deck.

> You could even implement a linear bounded Turing machine as an FSM it would just take an ungodly number of states.

To be clear, these things have formal definitions, and this statement is not correct.

1. A linear bounded automaton[0] is a Turing machine that can only overwrite symbols presented on its input tape as input. However, the definition of the automaton is still required to be finite, but it is required to operate on unboundedly large input tapes.

2. A finite state machine[1] is a model of computation where the sequence of input symbols are observed once and the machine is at all times in one of a finite number of states. It is equivalent to a TM that can only move right (and consequently cannot read anything it writes to the tape).

They are different, formally[2]. There are languages that a LBA can accept that a FSM cannot accept (famously, the strings of balanced parentheses cannot be recognized by a FSM).

[0]: https://en.wikipedia.org/wiki/Linear_bounded_automaton

[1]: https://en.wikipedia.org/wiki/Finite-state_machine

[2]: https://en.wikipedia.org/wiki/Pumping_lemma_for_regular_lang...

(from a cursory read) You can buy votes, but they become increasingly costly. Also, the payments are redistributed out among the population, so if you spend 1B to buy 31.6K votes, that 1B gets handed to the population at large who, if larger in number, can more efficiently re-spend it voting you down.

What I imagine QV does is find the point at which participants who don't care so much would rather pocket the funds and walk away, rather than spend it on voting.

If the ballot measure is "Eat Vinnl", you might want to spend a lot to vote it down, but it might not take much to convince the others not to spend it back at you (and you all eat berries instead). If the ballot measure is "Vinnl eats everyone else", you won't be able to spend enough that everyone else can't just spend it back at you, more efficiently.

Edit: one important difference here is that unless the GP is actually going to pony up real money, something of value to those they inconvenience with their (imo silly) opinion, it doesn't make much sense.

IANAPLRESEARCHER, but to my understanding, it actually unifies the semantics. The return value is always the result of the last expression, and its type may either be something non-trivial, or `()` which is what `expr;` returns.

This makes it easier to write and use generic code for which you don't know the return type (could be `String`, could be `()`), without insisting on special cases for "returns a thing" and "doesn't".

Example: I hold a thing of type `T` and want to let you call a function on it. I can write this generically as

    pub trait WithMut<T> {
      fn with_mut<R, F: Fn(&mut T)->R>(&mut self, func: F) -> R;
    }

and now with one implementation I can deal both with functions that return meaningful values, and "computations" that do some work but return nothing (other than `()`).

Maybe a different way to frame it is: Rust provides a stability guarantee for `rustc`, but you could just as easily prioritize stability for the Rust ecosystem. If Rust gets some neat new features that break crates, the experience of stability for users is still missing.

Feel free to factor in that approximately five people use crates that I write, and most of them have bigger problems than Rust breakage. :)

That Rust binaries and Rust shared libraries use different allocators on stable, making FFI .. awkward.

One of the PITA aspects of this type of break is when library writers need to change (via hard break) their external APIs because Rust has made a "minor break that can be easily fixed".

For example, one of the timely traits had `min` and `max` methods, as it corresponded to a type with upper and lower bounds. Rust added `min` and `max` convenience methods to all implementors of `Ord` (which this type was), which now means that anyone who wants to use the type needs to use UFCS. Or, I issue a major break so that their lives don't suck (now `minimum` and `maximum`).

The Rust change was classified as fixing a "papercut", so that folks wouldn't have to `use std::cmp::{min, max};`, but it's a pain in the arse when it's done so casually.

As someone familiar with differential privacy, and (somewhat less) with privacy generally, here are some suggestions for Mozilla:

1. Run an opt-out SHIELD study to answer the question: "how many people can find an 'opt-out' button?". That's all. You launch this at people with as much notice as you would plan on doing for RAPPOR, and see if you get a 100% response rate. If you do not, then 100% - whatever you get are going to be collateral damage should you launch DP as opt-out, and you need to own up to saying "well !@#$ them".

2. Implement RAPPOR and then do it OPT-IN. Run three levels of telemetry: (i) default: none, (ii) opt-in: RAPPOR, (iii) opt-in: full reports. Make people want to contribute, rather than trying to yank what they (quite clearly) feel is theirs to keep. Explain how their contribution helps, and that opting-in could be a great non-financial way to contribute. If you give a shit about privacy, work the carrot rather than the stick.

3. Name some technical experts you have consulted. Like, on anything about DP. The tweet stream your intern sent out had several historical and technical errors, and it would scare the shit out of me if they were the one doing this.

4. Name the lifetime epsilon you are considering. If it is 0.1, put in plain language that failing to opt out could disadvantage anyone by 10% on any future transaction in their life.

I think the better experiment that is going on here is the trial run of "we would like to take advantage of privacy tech, but we don't know how". I think there are a lot of people who might like to help you on that (not me), and I hope you have learned about how to do it better.

> Toofr’s lifetime revenue now is over $550,000. Those two nights at the St. Regis, plus meals and drinks were about $1,100. That’s a 5,000% return on investment!

Would be better if the title wasn't off by 10x. =/ Maybe not.

It depends a bit on how much sugar you'd like, but it isn't too hard to get Rust to spin things around for you. Here are two implementations, depending on what you need (resp, for serialization, vs traversal). YMMV.

  https://github.com/frankmcsherry/columnar
  https://github.com/antiguru/columnar-rs

FLP says that any deterministic algorithm satisfying agreement and validity must have non-terminating executions. If you are allowed to pick the distribution over the sequence of events in the system I'm sure that the probability of non-termination is quickly zero. If FLP are allowed to pick the distribution, the probability of non-termination can be one.

Getting into a quantitative evaluation of the likelihood of consensus is beyond my ken, but different people have different beliefs about what constitute "in real systems", and different interpretations of "practically doesn't matter". For example, the fact that you are talking about data centers rather than satellites suggests (to me) that your beliefs about the scarcity and transience of partitions may not generalize.

We can afford to be clear about what is true and what isn't, especially when trying to build reliable distributed systems.

Note: Ben-Or's consensus algorithm uses randomization to drive the probability of termination to zero, but still has non-zero probability associated with any length of execution.

> FLP says it's always possible to not achieve consensus, but it says nothing about the probability of it.

It says that the probability is not zero. That is a very important distinction for some people.

> You are much more likely to run into other problems that affect your availability, like code bugs or failed isolation between some components.

All the more reason not to claim that your system provides the guarantee.

I'm pretty sure the article claimed no such thing. In fact, the article repeatedly says that it will take no position on whether EO is at all like AB, but that AB is not something you can guarantee (modulo new model assumptions), and probably not something that the Kafka folks should be saying they can do.

If you want to rip in to Apple or Google or Uber for claiming they should have a pass for using privacy tech, feel free. Understand that this is distinct from most research on differential privacy.

The US Census collects demographic data about as much of the population as they can manage, and releases summary data in a large part to support enforcement of the Civil Rights Act. They have a privacy mandate, but also the obligation to provide information in support of the rights of subpopulations (e.g. Equal Protection). So what's your answer here? A large fraction of the population gets disenfranchised if you go with "avoid sharing the datasets".

You end up with similar issues in preventative medicine, epidemiology, public health, where there is a real social benefit to analyzing data, and where withholding data has a cost that hasn't shown up yet in your analysis. Understanding the trade-off is important, and one can come to different conclusions when the subjects are civil rights versus cell phone statistics. But you are wrong to be upset that math allows the trade-off to exist.

Interesting. Do you have similar concerns about cryptography?

Edit: to more strongly bind 'similar': would you also say of cryptography that it is "cynical academic malpractice"?

> You can't fight information theory.

I totally agree with this statement, but I think you are confused about differential privacy. Its guarantees are information theoretic (specifically, a bound on the relative Bayes factors of any conclusion, with and without any individual record).

You are obviously welcome to be skeptical, but much of what you've posted so far is not correct.

In the event that anyone isn't clear on the relative quality of discussions across various websites, please click the reddit link and observe someone asking a sincere question and getting specific and helpful responses, with no attempt to score points by misrepresenting the position of the others.

If the name were Milquetoast it would be awesome, because that was the cockroach from Bloom County. Or, was that the joke and I'm only just getting it late? ;)

https://en.wikipedia.org/wiki/Minor_characters_in_Bloom_Coun...

Google uses it.[0] I think it mostly needs interested parties; folks who care enough to commit to doing something more interesting with it than just counting things. I've certainly built several tools while at MSFT, they just .. languished.

[0]: https://github.com/google/rappor

I'm not sure I want to open this can of worm here, but this is one of the appealing properties of differential privacy: there is a quantitative bound you can invoke ("we will mine at most eps-dp from your emails, in exchange for this tasty cookie") and then you don't have to have a complicated discussion about which types of PII they ripped from your email, metadata vs non-, and other increasingly meaningless distinctions.

Differential privacy also has the nice property that it works like a fungible currency: it is additive, so even if you hand out x, y, and z units to different folks, they collectively can't spend more than x + y + z units, no matter how clever they are. In principle this could help folks determine a value for their sensitive data, and perhaps set up decent standards for people to value their own privacy (e.g. "selling 0.1 units of differential privacy from your email could shift your health insurance premiums by 10%").

Can I convince you to downgrade to being subjectively convinced?

Storing hashes or probes wasn't faster for the use cases I evaluated. I can see reasons why you might like it, for your uses and perhaps "generally", but not in my case at least (small keys where storage bloat was worse than `fnv` recompute, and values which had invalid states which can be used to represent empties)

Edit: I'm re-reading my first response and it reads like "you never need/want the probe length", and I totally retract that position; it wasn't intended.

> 1) The linearly-probed robin hood variant is just a sorted array. That's it. It's just a sorted array. I haven't seen an article explain it so succinctly though.

It's not. Importantly, it leaves spaces so that you avoid what would be ~sqrt(n) probe lengths had you tightly packed everything. Also, it is a bit out of order as you wrap around the limits of the array (less of a big deal).

The sortedness property is really useful, btw. A RHH lets you get the perf of a good hash map for random access, and the throughput of a sorted list for merges / bulk processing.

> 3) There's a simple 40 year old bitwise trick by Knuth which allows one to combine the probe distance and the hash into a single value. This saves up to 4 bytes per table entry, but I haven't seen anyone use it.

When the values are sorted (modulo empties and wrapping) you don't need to store the probe length. You just maintain the invariant that things are sorted. Maybe I'm missing some detail of your implementation, but mine sure don't bother storing it.

There seems to be a lot of angst in the responses about how deep nets et al "are too elegant; are too interpretable!".

It's important to remember that the intended product of science is not tools, it is understanding. Deep nets may produce very elegant and interpretable tools, from a very elegant and interpretable theory, but that is not what the scientists are looking for. They are generally creating and assessing theories in their subject domains, which are then evaluated by the tools they have built.

Deep learning does do a great job of providing a baseline ("your theory must be this accurate to matter"), but it seems to do a much less great job at extracting new understanding.

No. At least, not in the case of graph computation. This was the conventional wisdom with some people, but circa a year or so ago when we did some measurements, no.

https://github.com/frankmcsherry/blog/blob/master/posts/2015...

https://github.com/frankmcsherry/blog/blob/master/posts/2015...

If you don't want to read everything (but you should, before trusting the conclusions), the relevant measurements are here:

https://github.com/frankmcsherry/blog/blob/master/posts/2015...

Edit: Reading the paper, they cite these measurements and present their work as "only [..] 8.8× slower than a distributed in-memory" system (GraM, a different system than timely dataflow). The quote is on the first page.

I think in this case it doesn't, because the `HashMap` implementation just stores everything behind an untyped pointer.

https://github.com/rust-lang/rust/blob/master/src/libstd/col...

It would be cool to see if the "we'll manage our own pointers, thanks" approach makes less sense with this optimization in place. It would be nice; the source is pretty inscrutable, mostly in the interest of performance, I think.

Edit: Or, maybe more importantly: in the untyped memory they store hashes and (K,V) pairs separately, so I think the only opportunity is to swap (K,V) for (V,K).