russell_sears

My grandfather used to work on telephone field network boxes (e.g., the big boxes full of messes of wires in residential areas).

One job was to look for outliers in the network, and they spent time studying areas with an unusually large number of issues and ones with an unusually low number of issues.

There was a part of the phone network that was decades overdue for an overhaul but had no issues, so they inspected it. (This was decades ago, so the replacements for this antique could be modern day museum pieces).

When they took a look, everything was corroded beyond reason, as expected. However, the connections were still low noise / low resistance.

The old boxes used some sort of post connector and a crimp. It had something like two or four points of contact for redundancy (all contact points would need to corrode before it failed).

In the boxes with no failures, the (long gone) technician simply stuck the end of the wire into the post crimp hole, then wrapped slack wire around it a dozen times.

This gave it 100’s of contact points, and (after reverse engineering the technique) it took something like 1/10th as long per connection.

Sadly, we’ll never know if the installer was a genius, lazy or both.

Anyway, the crimp connectors in fig 19-25 and 19-28 of the nasa article look like the same concept but turned inside out.

This looks like the sort of bug I'd write back when I used mutexes to write I/O routines. These days, I'd use a lock-free state machine to encode something like this:

   NOT_IN_CACHE -> READING -> IN_CACHE

(the real system would need states for cache eviction, and possibly page mutation).

Readers that encounter the READING state would insert a completion handler into a queue, and readers transitioning out of the READING state would wake up all the completion handlers in the queue.

I've been working on an open source library and simple (manual) proof system that makes it easy to verify that the queue manipulation and the state machine manipulation are atomic with respect to each other:

https://docs.rs/atomic-try-update/0.0.2/atomic_try_update/

The higher level invariants are fairly obvious once you show that the interlocks are correct, and showing the interlocks are correct is just a matter of a quick skim of the function bodies that implement the interlocks for a given data type.

I've been looking for good write ups of these techniques, but haven't found any.

You might also be interested in JOL/Overlog, which was the predecessor to Bloom:

https://github.com/tcondie/jol

We built quite a few prototypes on top of it. The language implementation is a research prototype, but it is impressively stable.

Overlog’s synatax is based on datalog, but it shares many core ideas with Bloom.

You can guarantee termination by limiting bit precision, but it is more interesting to limit the set of operators your program uses instead.

For instance, you might have an operator that translates from hostname to IPv4 address.

That function can return billions of different numbers, but if your program’s input only has 10 hostnames in it (and you don’t use string manipulation or other tricks to fabricate hostnames) then you can infer that the IP lookup function only adds 10 new symbols to the sets that your program maintains.

Searching for “herbrand universe” will produce formal writeups of these ideas.

We really need a global carbon credit system (with stiff tariffs for countries that do not participate). Cut net greenhouse emissions by a few percent a year until net emissions are negative and atmospheric CO2 and methane are back to pre-industrial levels. This will help renewables (and nuclear, for better or worse) in the short term. In the medium term, the invisible hand of the market will make carbon capture profitable, which means smart VCs will start dumping cash into it now.

I think this sounds more plausible than terraforming, but is really the same thing.

I still don't understand how you come to the conclusion that the attack won't work.

The bolded text in the blog post reads "the middle relay will pick a different exit relay", and should read "the client will pick a new circuit at random using the same bandwidth-proportional weights."

The security properties of the corrected description aren't very comforting: the attack is no longer guaranteed to work, just like there is no guarantee I will ever roll a one with a fair die.

I read this explanation a few times, and am afraid I still don't understand why Tor is not vulnerable to this attack. Let's say I'm an attacker that provides enough bandwidth to compromise N% of client circuts, and I can disrupt non-compromised circuits at will. Casuing clients to repeatedly renegotiate non-compromised circuits lets me compromise >>N% of circuits, right? For small N, the chance of getting a compromised circuit is roughly linear in the number of circuit disruptions, right?

Unless I'm missing something, this vulnerability provides a significant multiplier to existing Sybil attacks against Tor. A quick search suggests there have been Sybil attacks in the past.

Am I missing something obvious here?

There are two effects at play. If you're reading a multiple of a flash page at a time, then you can get random bandwidth to match sequential. Under the hood, decent SSDs actually round robin sequential reads across all of the underlying hardware, so they can run as fast as whatever their bottleneck resource is. The bottleneck could be error correction, the SATA link, or the channels (copper traces) between the NAND and the controller, for example. Random reads with enough parallelism give the SSD enough scheduling freedom to have the same throughput as sequential.

The second effect comes from the fact that application data is rarely exactly the same size as a flash page. If you group all the related data on one page, then you don't waste time transferring bits you won't look at. B-Trees sort of do this, but they leave holes in pages so they can support efficient inserts (a good SSD or database will compress the holes, but that doesn't help random reads much, since it's still going to transfer entire flash pages to the SSD controller).

LSM-Trees push things a bit further, since new data ends up being grouped on higher levels of the tree. When I was benchmarking bLSM's predecessor, I worked out the expected throughput on the back of an envelope while I was waiting for results. It did much better than expected, since the benchmark heavily favored recently created data! YMMV, of course.

Hi. First author of the bLSM (Yahoo) paper here. You've pretty much nailed it: The trick is getting latency and volume at the same time. If you're willing to wait an hour to look at event logs, then Hadoop is good enough, but where's the fun in that?

At the time, we were looking for the best of both worlds: Hadoop and log processing give high throughput writes, but latencies are much too high to act on user intent within a single session. We had a lot of applications in mind that needed low latency access to event log data, but didn't have a suitable storage engine to back them.

Existing LSM trees suffered from write stalls and excessive read amplification. We were targeting hard disks back then, and didn't want to pay for the extra seeks. We got random read access down to about one seek per read, and figured out how to eliminate write stalls. Surprisingly, we still ended up with good write throughput.

More importantly, from an application perspective, we provide efficient range scans, which lets you reason about groups of data with matching or contiguous keys. If you squint hard enough, this is all MapReduce really does, except it precomputes all the answers up front, and we do it in real time. On the one hand we have lower throughput, since we perform more random reads / sequential writes, and also do more thread synchronization. On the other, we only perform the computations for data that's actually being used for something, which means we do a lot less work for the right applications.

Thanks!