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.

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!

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

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?

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 was reminded of @jaffray.bsky.social's great exposition of the CVM cardinality-estimation algorithm: buttondown.com/jaffray/arch...

Behold cat.

Greetings from London!

I'm trying to model a distributed protocol in TLA+, and finding it kind of awkward. The basic setup seems straightforward: There are a few nodes, which have some persistent state and some in-memory state. They can't become unavailable but they might restart arbitrarily.

I wrote a somewhat meandering question about writing programs that do a lot of asynchronous operations without callbacks. I'm curious whether anyone has thoughts on this sort of thing! shachaf.net/tmp/asynchro...

Sea Magic, a puzzle game about moving to cast spells, is out now! epicpikaguy.itch.io/sea-magic

@haroldaptroot.bsky.social after @instlatx64.bsky.social pointed me to your blog post about histogramming I showed a coworker. He was so impressed, (as was I) that he wrote his own blog post about it. github.com/JoernEngel/j...

It's funny that a "circuit" in computer science is explicitly defined to be an acyclic graph.

Clay codes are a newish erasure coding scheme with some nice properties: They make for a systematic MDS erasure code, like Reed-Solomon, that can recover the loss of one chunk of data with much less bandwidth and disk I/O than the worst case you get with typical MDS codes.

Clay codes are a newish erasure coding scheme with some nice properties: They make for a systematic MDS erasure code, like Reed-Solomon, that can recover the loss of one chunk of data with much less bandwidth and disk I/O than the worst case you get with typical MDS codes.

Is there ever a reason not to use a primitive polynomial as the generator of your finite field?

Regular expressions can be convenient, but there are some cases where they've very verbose compared to writing an NFA directly. Is there an alternative syntax people use that doesn't have that property?

My sister sent me this puzzle. It's so good!

And the explanation: tavianator.com/2025/shlxpla...

What are some systems that combine write-ahead log, consensus log, transaction log, etc. into a single log? I often see these being separate, which is kind of natural if you think of these as being different components, but presumably you want one log if you can manage it.

If you define "while(x);" to mean "if (!x) break;", and have your only looping primitive be infinite loops, you get something that seems nicer than C: "while (x) { ... }" turns into "loop { while(x); ... }", and "do { ... } while (x);" turns into "loop { ... while(x); }"

What are some practical uses of Fast Paxos? Are there any systems that actually use it?

this week on NULL BITMAP, intuition for snapshot isolation: it’s like git buttondown.com/jaffray/arch...

We were implementing something like a semaphore, but where there are k (small k, say 64) slots and you get specific slots when you decrement. I guess it's just a sort of allocator+queue, but is there a standard name for that?

Donald Knuth will be giving his annual Christmas tree lecture Thursday next week. It'll be about strong and weak components in directed graphs and Tarjan's algorithm for computing them. I'm planning to go! It looks like it'll also be streamed online. www-cs-faculty.stanford.edu/~knuth/musin...

NULL BITMAP: Fine! I'll Play With Skiplists buttondown.com/jaffray/arch...

Alpha-beta pruning in one sentence: If you want to compute max(8, min(5, ...), ...), you don't need to compute the rest of the arguments to min, because they won't affect the value of the max.