Sharding Is Also NP-Complete
datafinnovation.medium.com
datafinnovation.medium.com
> The property we are going to look at is: reshuffling lists of ok-on-their-own transactions with a no-negative-balance requirement into a single merged list where the maximum number of possible transactions go through.
They key word being "maximum". So they just equated scaling with an optimization problem. It's well known and not surprising that optimization problems are NP hard.
I wouldn't even call this a scaling problem, since scaling is not about how to order things, but how to support higher transaction rates with fewer resources.
Sharding is similarly defined as some assignment problem that is divorced from sharding practice by requiring that all of a given list of transactions is assigned to shards while satisfying certain constraints.
It would be more appropriate to title these articles as "Optimal Scaling is NP-hard" / "Optimal Sharding is NP-hard".
In practice, one just uses some efficient, usually greedy, algorithm to find near optimal solutions.
because you can only get "nearly optimal" it's always possible to rig the system into a worst case. and if you promise low-low fees all the time that isn't expensive to do.
here an attack against the approximation algorithm is an economic attack. you cannot attack approximations in a normal scheduling system like this of course.
all of this is resolved if you do something as you say and add a defense mechanism (i.e. rapidly escalating fees or brownouts) when "near optimal"!="good enough."
Yes, sharing is NP-complete, but that's not, as far as I understand, a problem. Efficient scheduling of parcel delivery is NP-complete, the postal service runs fine, if probably slightly suboptimally.
Why does it matter if we do what everyone had always done in this type of situation, and just have everyone love in the shard they choose, moving when they feel like it?
Odd statement. The system the author describes is decidedly not general. It is in fact a very specific and nuanced system.
Or something.