shachaf

Expectation Again We talked a couple issues ago about the application of Linearity of Expectation to building intuition about Copysets, and the ways that we're both...

This follow-up is fun and I hadn't encountered it before: buttondown.com/jaffray/arch...

It's funny that people say "register" to mean both an aspect of encoding an instruction graph and a physical place in the CPU where data is stored. These are really very different things!

Expectation and Copysets That expectation is linear is one of my favourite facts. I got a first taste of this when I was doing an internship at an unnamed trading firm. Some guy was...

@jaffray.bsky.social on linearity of expectation and copysets: buttondown.com/jaffray/arch...

This is interesting: dotat.at/@/2025-12-25...

In one shuffle algorithm, on step i, you have a sample (without replacement) of i elements. In the other algorithm, on step i, you have a permutation of the first i elements.

I've only ever thought of the sampling-based algorithm!

What's the simplest proof of false using type-in-type? I see examples that construct Russell's paradox by modeling set theory, but that seems a bit roundabout -- is there something more direct?

this is imo one of the most elegant results in distributed computing and this is a great presentation of it!

I wrote a short summary of the proof of the FLP theorem (an impossibility result about consensus). shachaf.net/w/flp

I knew about the trick for a queue with amortized-constant-time enqueue/dequeue/monoidal product, but I don't think I knew the deamortized version hirzels.com/martin/paper... . It's simpler than I expected (maybe because I haven't really seen deamortizations much).

What are the biggest new things in computer science since say 2010?

Vague thought: Could the kinds of heuristics used in branch predictors apply to SAT solvers for choosing a literal assignment on (frequent) restarts? "phase saving" (just use the last value) is a common strategy, but does it make sense to do something more sophisticated?

Vague thought: Could the kinds of heuristics used in branch predictors apply to SAT solvers for choosing a literal assignment on (frequent) restarts? "phase saving" (just use the last value) is a common strategy, but does it make sense to do something more sophisticated?

Exciting news: I'm moving to London at the end of this month!

Is there a rank-select bitmap algorithm that I should have in my mind as "canonical" (reasonably simple and practical)? I know there are a bunch of them but I don't really know how any of them work in detail, and I vaguely remember seeing some pretty complicated constructions.

This is a simplified form of the extended Euclidean algorithm, in that it works mod p instead of tracking a specific multiple of p. The full algorithm solves

1a + 0p = a
0a + 1p = p

Into the form

xa + yp = 1

Which gives you the specific value, not just a representative.

I recently learned this trick to compute the modular inverse x of a mod p: Write the two equations

ax = 1 (mod p)
px = 0 (mod 0)

And then solve by subtracting multiples of one from another until you get something of the form "1x = x (mod p)", in Euclidean-algorithm-style steps.

NULL BITMAP: How to Understand that Jepsen Report buttondown.com/jaffray/arch...

Apparently when machine learning people say "convolution" they usually mean "cross-correlation"? It was confusing trying to make sense of the expression I was seeing!

My First Distributed System I can show you a picture of the first distributed system I ever used: (Not entirely accurate, I had a Game Boy Color.) When I was a kid, we'd spend summers...

If you can talk to both participants, you can ask them what state they're in and recover. If you can't, you're in trouble, which is kind of unavoidable. I should have linked to the original post: buttondown.com/jaffray/arch...

I really liked this perspective on atomic commit from @jaffray.bsky.social!

6. Master Contract signatories shall not use automation or artificial intelligence or quantum computing for the performance of clerical functions.

What a clause in the new East coast dock worker union contract.

There are many concurrent systems that aren't non-blocking in a typical formal sense (e.g. obstruction-free), but are non-blocking in the sense that a thread never blocks waiting on a lock -- it can keep processing other work while it waits for things. Is there a name for that?

I'm thinking of something like a sharded system where you can send a message the thread that owns a shard, or a system where, if someone is holding a lock, you make a note for the unlocking thread to do your work when it's done.

There are many concurrent systems that aren't non-blocking in a typical formal sense (e.g. obstruction-free), but are non-blocking in the sense that a thread never blocks waiting on a lock -- it can keep processing other work while it waits for things. Is there a name for that?

The CVM Algorithm Everything you need to know about query planning can be understood from this query: SELECT * FROM xy WHERE y = 3 ORDER BY x Imagine we have two indexes, one...

I was reminded of @jaffray.bsky.social's great exposition of the CVM cardinality-estimation algorithm: buttondown.com/jaffray/arch...

Behold cat.

Greetings from London!

Thanks for the reference! I'll think about whether I can simplify my model this way, but I'm kind of skeptical -- one reason is that I probably want to model having both persistent and ephemeral state, and the mechanism for crash recovery, explicitly, since it's the source of a lot of complexity.

I've been meaning to try FizzBee for this, I might do that!

This seems like it would be a pretty standard setup, but most examples I see aren't doing things like that, and it seems awkward enough in practice that I'm wondering whether I'm doing it wrong.

If a node restarts, it loses in-memory state but keeps persistent state (and messages it didn't respond to will eventually be redelivered to it, unless the sending host also restarts).