[skybrian]

One problem might be with latencies right at the boundary between two buckets. A bit of jitter would let you know you're near the edge with enough sampling. And if you can add a little latency then you can move the boundary where you like.

It seems like the only way to avoid that is with one bucket (constant time).

[stagas]

Even if it's one bucket, isn't it still vulnerable to the same attack you describe? If you push the latency to the edge, you'd know how much is yours and how much the bucket's. Even if it was randomized you could still figure out the window of the added noise with enough sampling and you're back to where you started. I don't see a way out, other than if someone really wants to avoid these types of attacks, then using a VPN is the best bet here.