Vervious

Previous discussion (in 2020): https://news.ycombinator.com/item?id=25326645

Also, I personally think the current blockchain literature is much more intuitive and easier to follow, for learning about consensus. The Byzantine case isn't really that different than the crash case if we assume cryptography. On the other hand, Raft is a spiderweb of a protocol, very easy to get wrong.

Tbh I always direct people who want to read old important papers to lecture notes or textbooks, at least in distributed algorithms or CS theory.

I've found that the original papers are always super dense and the material has usually evolved to be more explainable, especially when someone has put in the time to compile it as part of a course.

yeah if someone proved P != NP --> OWFs, that would be the seminal result of a generation of work in computer science theory.

Just wanted to emphasize your point about "worst case hardness" -- even if 3SAT turns out to be hard (due to P != NP), it is only hard in the worst case (for a very small subset of all possible 3SAT problems). Most 3sat problem instances are (probably?) easy.

In crypto, we need to sample "average case hard" problems, where on average, a random problem that we sample is hard. This is in contrast to, for instance, uniformly sampling from the set of all 3SAT instances, which gives an easy problem on average.

A continuation of this line of research essentially looks at turning worst case hard problems into average case hard problems. Asymptotics are already way on the backburner since we are in theory world.

(Note that a One way function is average case hard)

can you link the preprint by chance? I can never find the actual papers from quanta...

How is this different from saying 80% of engineers went to engineering school?

"The observed placement rates would imply that faculty with doctorates from the top 10 units are inherently 2 to 6 times more productive than faculty with doctorates from the third 10 units." At least looking at top CS conferences the authorship of accepted papers ARE in fact this correlated (it seems to me).

The main question that requires answering, I think, is why we let Tether and Bitfinex print a bunch of Tether and buy a bunch of Bitcoin during low volume periods. The Bloomberg report et al and the SEC both suggest that this is happening, constituting clear price manipulation.

Is that not by definition fraud? It's like the US federal reserve printing a bunch of stimulus. At least our central banks are nominally appointed by elected officials, on the basis of a social contract.

Note, "The majority of Bitcoin trades are now conducted in Tether, 70 percent by volume. By comparison, only 8 percent of trade volume is conducted in real dollars, with the remainder being other crypto-to-crypto pairs."

Why is this flagged? The argument presented is very reasonable and requires a rebuttal. It is also an uncommon argument I haven't seen previously on the front page. The main argument is that Tether is acting like an unregulated central bank that holds all the power over the price of cryptocurrencies. Thus, crypto holders who are not in on the fraud are like a flock of Bison being driven off a cliff, if there is ever a run on Tether.

The other comments on this thread are worthless and just shilling crypto.

It seems to depend on how specialized you are. I bet it would be very difficult for any automated tool to understand how good a paper is. Until then, you have to rely on other people who understand the paper, to get good paper recommendations. Most papers are incredibly specialized and I bet can only be totally understood by a few dozen/hundred/thousand people (depending on field?). In other words, if you are a student, ask your advisor/professor. If you are looking for general papers to read about systems, someone's probably written a blog post about it. Or popular science magazines (e.g. Quanta) might be nice.

Oh, or you can browse conference proceedings of the top conferences (in CS, at least.) (Though those are also, gigantic, and you probably want to filter even further...)

I feel that Google Scholar Alerts are only useful once you can filter paper titles / taglines by yourself, which requires tremendous expertise. I would be very surprised if any automated tool could replace other people and their technical expertise (which took years of training to develop) as a paper filtering tool. Otherwise you might as well automate peer review.

To be fair, it is quite murky to what extent groups like Al-Haq are associated with the PFLP (which, with its history of aircraft hijackings and suicide bombings, is undoubtedly a terrorist group). There is plenty of purported evidence of financial and personnel links out there, and I really doubt HN is the right forum to decide either way (unless someone is an expert).

in what world is there a selfish financial incentive for whistleblowing?

A correct Multi-party computation protocol (MPC) by definition is private. MPC from its inception has used zero-knowledge proofs as a building block (i.e. see the GMW compiler from the 1980s) (though other approaches exist).

Pretty sure Paxos is easily extended to the byzantine setting with digital signatures (i.e. Byzantine Paxos has also been around forever). Also PBFT has been around since the 1980s.

Only distinction is classical consensus is permissioned whereas blockchains are typically permissionless.

Honestly I think your comment is so broad that it's vacuous.

In this specific case, mitigating the spread of zebra mussels through prevention has a clear and explicit benefit, in preserving natural north american ecosystems. The collapse of Lake Michigan's fisheries is a case in point.

I recall paper trail had some errors in their post on paxos (iirc), which made me more skeptical of the publication in general. But these are good links!!

I guess most research shouldn't be surprising, otherwise there'd be an eureka every day

It's crazy how much and how little maintenance a high-tech aquascape needs. I just got back from a six-week trip and all the stems and carpet are completely overgrown, but algae is still minimal and the fish and shrimp are none-the-wiser.

no CRYPTO or PODC?

Maybe historically, before the public even had computers, but do you have anything to support your claim for cryptography in the modern era?

there are also a variety of problems that are hard to approximate.

(In the context of embedding paxos in some sort of proof-of-concept replication system. Something like Multi-paxos.)

You're right, I guess we generally talk about state machine replication instead of one-shot systems.

(For more, Ittai Abraham has a series of nice posts: https://decentralizedthoughts.github.io/2019-06-01-2019-5-31...)

Right, when run in a fully asynchronous setting, where the network adversary can always deliver messages in the order of their choice, the FLP impossibility result says that Paxos cannot terminate.

Thus, for Paxos to make progress, the network needs to eventually "heal" and deliver messages in a timely manner -- that's what we mean by partial synchrony. Streamlet, likewise, tolerates arbitrary network delays (in the sense that no two players will agree on different things even if Comcast maliciously scheduled every message), but also requires partial synchrony to make progress (i.e. once in a while Comcast will deliver messages in timely fashion and in order, like you expect).

(Partial synchrony is arguably the most practical of the theoretical synchrony models for consensus. There are other models, i.e. "periods of synchrony", but they all end up capturing the same idea).

FLP, however, is a fairly weak statement. It only rules out termination for deterministic protocols. We can in fact design randomized asynchronous protocols that make progress (with good probability), regardless of the ordering in which messages are delivered. I.e. as long as Comcast eventually delivers every message -- and letting it choose delays arbitrarily -- a randomized protocol could make progress. These are the "true" asynchronous protocols. (Paxos is not one of them)

I guess the original asynchronous consensus protocol is Ben-Or's protocol (which takes 2^n time in expectation IIRC, where n is the number of players). We can reduce the running time using some (fairly sophisticated) cryptography -- the most famous is the Canetti-Rabin protocol, and Cachin and many others have worked on it since. Most of the complexity (for polynomial time protocols) is in building a "global common coin" -- i.e. a global coin that everyone agrees on the result of; once you have that we can use Mostefaoui's protocol for instance. Building this coin is incredibly complicated (much more so than Paxos) unless we assume some strong cryptographic trusted setup (i.e. a nice threshold signature scheme). How practical any of these schemes are is an open question.

No complexity is hidden here. Streamlet is (essentially) in the same setting as paxos. Just like in paxos, messages can take arbitrarily long to deliver.

The only assumption is that clocks are synchronized, which is much, much weaker. (We can actually remove even this assumption. But it's easier to think about this way.)

i.e. I think it's monday at the same time you think it's monday, or I think it's epoch 1 at the same time you think it's epoch 1. or my quartz crystal oscillates at the same rate as your quartz crystal. Importantly, a message sent during epoch 1 might arrive in epoch 3, or never at all.

Paxos is also in the partially synchronous setting - it requires some network synchrony in order to terminate, just like streamlet (For truly asynchronous protocols, there's a whole, complicated literature).

We could actually run a generic clock synchronization protocol to synchronize clocks over a partially synchronous network. I guess paxos kind of builds that in, which adds to its complexity.

Safety in particular doesn't require any timing assumption.

(Note that messages can still be delayed arbitrarily in both protocols)

I don't think it hides any complexity, but I guess that's for the reader to decide.

Raft on the other hand... I've implemented versions of both paxos and raft, and by golly was the latter more difficult to get right.

Paxos shouldn't be the first protocol you learn -- I think it gives consensus this mistaken reputation for being "difficult to understand".

Consensus protocols (and the related problems of state machine replication, permissioned blockchains) have really come a long way over the years. They've become more performant and much simpler (in my opinion).

(I'll take the opportunity to pub streamlet: it's simpler, has only two message types "propose" & "vote", and it tolerates malicious faults. https://decentralizedthoughts.github.io/2020-05-14-streamlet...)

Funding top research institutions are in fact long shot bets.

Where else does research get done? Who pays for the buildings, where each one costs hundreds of millions of dollars? Scholarships? Who pays for new tenured positions?

Yes, administrative costs could be cut (I think substantially). But there's this long-going misunderstanding about the roles of endowments at American universities. These endowments have been budged into the next century of operation -- each year they are expected to generate some income to cover operating expenses. These expenses include salaries, financial aid, etc. The larger the endowment, the more income. They can't just drain the whole thing to pay for a building, because then they auction off the future for the present.

Depends on your definition of impact. Tesla certainly is not improving education outcomes worldwide, nor funding healthcare research; nor is spaceX saving rainforests from being cut down every day, or helping sustain democracy.

I guess EVs have less environmental impact after four years of use, but do Teslas last that long? The intent there (and the impact) is still very much to monetize