Fast CASPaxos - leaderless distributed consensus without logs. It allows any proposer to commit an update to a shared register with a single round-trip while maintaining linearizability.
reubenbond.github.io/posts/fast-c...
Note to self (because I keep forgetting these numbers and having to figure them out again):
The original Fast Paxos paper suggests two extremes for cardinality-based quorums:
Classic-minimizing: classic = ⌊N/2⌋ + 1; fast = ⌈3N/4⌉
Fast-minimizing: classic = fast = ⌊2N/3⌋ + 1
I wrote a short summary of the proof of the FLP theorem (an impossibility result about consensus). shachaf.net/w/flp
Makes sense, though I wonder whether I should think of zero as a limit ordinal anyway?
It's funny, I never noticed that strong induction doesn't need an explicit base case.
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!
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!
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?
I was reminded of @jaffray.bsky.social's great exposition of the CVM cardinality-estimation algorithm: buttondown.com/jaffray/arch...
Behold cat.
