Sign in

shachaf

@shachaf.net
127 followers 142 following 80 posts
PostsRepliesMedia
shachaf @shachaf.net · 03/09/2026
_Different Kinds of Darkness_ by David Langford: www.lightspeedmagazine.com/fiction/diff...
lightspeedmagazine.com
Different Kinds of Darkness - Lightspeed Magazine
It was always dark outside the windows. Parents and teachers sometimes said vaguely that this was all because of Deep Green terrorists, but Jonathan thought there was more to the story. The other memb...
010
shachaf @shachaf.net · 16/08/2026
It's kind of funny that the RISC-V fence instruction tries to be very flexible, letting you specify an unusually fine-grained bitset of predecessor and successor things to fence, and yet it's not flexible enough to express TSO, so there's an extra bit for that specific behavior.
010
shachaf @shachaf.net · 07/08/2026
I encouraged my friend Peter to write up a point about equity vs. cash compensation that we've discussed many times: peter.website/equity-beats...
peter.website
Equity is Worth More Than Cash Because of Optionality
When taking a job you should basically always max out the equity compensation
010
Reposted by shachaf
shachaf @shachaf.net · 22/09/2025
I wrote a short summary of the proof of the FLP theorem (an impossibility result about consensus). shachaf.net/w/flp
shachaf.net
The FLP theorem
142
shachaf @shachaf.net · 11/07/2026
Currently reading a paper and wishing it followed Lamport's dictum "State the Problem Before Describing the Solution".
010
shachaf @shachaf.net · 13/06/2026
Happy pigeon appreciation day!
110
shachaf @shachaf.net · 29/04/2026
It's kind of a scam that they call it a "field-programmable gate array" but then the only field you can program it with is GF(2).
020
Reposted by shachaf
Reuben Bond @rbn.bsky.social · 09/04/2026
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...
081
shachaf @shachaf.net · 19/04/2026
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
000
shachaf @shachaf.net · 28/03/2026
Makes sense, though I wonder whether I should think of zero as a limit ordinal anyway?
010
shachaf @shachaf.net · 28/03/2026
It's funny, I never noticed that strong induction doesn't need an explicit base case.
110
shachaf @shachaf.net · 23/02/2026
This follow-up is fun and I hadn't encountered it before: buttondown.com/jaffray/arch...
buttondown.com
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...
010
shachaf @shachaf.net · 19/02/2026
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!
110
shachaf @shachaf.net · 09/02/2026
@jaffray.bsky.social on linearity of expectation and copysets: buttondown.com/jaffray/arch...
buttondown.com
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...
130
shachaf @shachaf.net · 26/12/2025
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!
dotat.at
doubly dual shuffles – Tony Finch
030
shachaf @shachaf.net · 29/10/2025
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?
000
Reposted by shachaf
Justin @jaffray.bsky.social · 23/09/2025
this is imo one of the most elegant results in distributed computing and this is a great presentation of it!
051
shachaf @shachaf.net · 22/09/2025
I wrote a short summary of the proof of the FLP theorem (an impossibility result about consensus). shachaf.net/w/flp
shachaf.net
The FLP theorem
142
shachaf @shachaf.net · 09/08/2025
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).
hirzels.com
020
shachaf @shachaf.net · 09/08/2025
What are the biggest new things in computer science since say 2010?
010
Reposted by shachaf
shachaf @shachaf.net · 06/07/2025
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?
031
shachaf @shachaf.net · 06/07/2025
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?
031
shachaf @shachaf.net · 02/07/2025
Exciting news: I'm moving to London at the end of this month!
160
shachaf @shachaf.net · 01/07/2025
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.
000
shachaf @shachaf.net · 11/06/2025
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.
000
shachaf @shachaf.net · 11/06/2025
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.
110
Reposted by shachaf
Justin @jaffray.bsky.social · 05/05/2025
NULL BITMAP: How to Understand that Jepsen Report buttondown.com/jaffray/arch...
1105
shachaf @shachaf.net · 04/05/2025
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!
010
shachaf @shachaf.net · 29/04/2025
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...
buttondown.com
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...
100
shachaf @shachaf.net · 29/04/2025
I really liked this perspective on atomic commit from @jaffray.bsky.social!
221
shachaf @shachaf.net · 28/04/2025
What a clause in the new East coast dock worker union contract.
6. Master Contract signatories shall not use automation or artificial intelligence or quantum computing for the performance of clerical functions.
121
Reposted by shachaf
shachaf @shachaf.net · 24/04/2025
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?
221
shachaf @shachaf.net · 24/04/2025
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.
010
shachaf @shachaf.net · 24/04/2025
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?
221
shachaf @shachaf.net · 22/04/2025
I was reminded of @jaffray.bsky.social's great exposition of the CVM cardinality-estimation algorithm: buttondown.com/jaffray/arch...
buttondown.com
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...
010
shachaf @shachaf.net · 22/04/2025
Behold cat.
050
shachaf @shachaf.net · 12/04/2025
Greetings from London!
020
shachaf @shachaf.net · 01/04/2025
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.
010
shachaf @shachaf.net · 13/03/2025
I've been meaning to try FizzBee for this, I might do that!
110
shachaf @shachaf.net · 13/03/2025
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.
200
shachaf @shachaf.net · 13/03/2025
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).
100
shachaf @shachaf.net · 13/03/2025
Each node can have a bunch of processes/inflight requests running locally, which can do things like "take a snapshot of local persistent state", "send messages", "reply to message", "wait for replies", "write atomically to local persistent state".
100
shachaf @shachaf.net · 13/03/2025
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.
110
shachaf @shachaf.net · 10/03/2025
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...
shachaf.net
131
Reposted by shachaf
Ethan Clark @ethanclark.bsky.social · 22/02/2025
Sea Magic, a puzzle game about moving to cast spells, is out now! epicpikaguy.itch.io/sea-magic
epicpikaguy.itch.io
Sea Magic by Ethan Clark (EPICPIKAGUY)
Move to cast spells, optimize your score
02410
Reposted by shachaf
Curtis Bezault @cbezault.bsky.social · 15/02/2025
@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...
github.com
162
shachaf @shachaf.net · 13/02/2025
040
shachaf @shachaf.net · 18/01/2025
It's funny that a "circuit" in computer science is explicitly defined to be an acyclic graph.
020