Lightnews — Scholar-powered news

Reposted by shachaf

Justin @jaffray.bsky.social · 22d

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

shachaf @shachaf.net · 24d

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

The FLP theorem

shachaf.net

1 5

shachaf @shachaf.net · 24d

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

The FLP theorem

shachaf.net

1 1 3

shachaf @shachaf.net · Aug 9

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

2

shachaf @shachaf.net · Aug 9

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

1

Reposted by shachaf

shachaf @shachaf.net · Jul 6

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?

1 3

shachaf @shachaf.net · Jul 6

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?

1 3

shachaf @shachaf.net · Jul 2

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

1 6

shachaf @shachaf.net · Jul 1

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.

shachaf @shachaf.net · Jun 10

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.

shachaf @shachaf.net · Jun 10

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.

1 1

Reposted by shachaf

Justin @jaffray.bsky.social · May 5

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

1 5 10

shachaf @shachaf.net · May 4

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!

1

shachaf @shachaf.net · Apr 29

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...

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...

buttondown.com

1

shachaf @shachaf.net · Apr 29

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

2 1 2

shachaf @shachaf.net · Apr 28

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.

1 1 2

Reposted by shachaf

shachaf @shachaf.net · Apr 23

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?

2 1 2

shachaf @shachaf.net · Apr 23

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.

1

shachaf @shachaf.net · Apr 23

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?

2 1 2

shachaf @shachaf.net · Apr 22

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

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...

buttondown.com

1

shachaf @shachaf.net · Apr 22

Behold cat.

5

shachaf @shachaf.net · Apr 12

Greetings from London!

2

shachaf @shachaf.net · Apr 1

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.

2

shachaf @shachaf.net · Mar 13

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

1 1

shachaf @shachaf.net · Mar 13

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.

2

shachaf @shachaf.net · Mar 13

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).

1