nano_o · HackerTrans

It's impossible to do it deterministically (that's the famous FLP impossibility result), but if you accept to have liveness only with probability 1 then it's possible (for example, an early randomized asynchronous protocol is Ben-Or's protocol from 1983).

nano_o

7일 전discuss

What's interesting here is that this would be the first production implementation of an asynchronous consensus algorithm (QuePaxa). Paxos, Raft, etc. are all partially synchronous, meaning they rely on timeouts and only make progress if message delay is sufficiently small compared to timeout durations. QuePaxa doesn't rely on timeouts and makes progress even under wild fluctuations in message delay. The question is whether performance is competitive enough in the normal case, when message delay is small and doesn't vary much, and historically the answer has been "no" and that's why asynchronous protocols weren't used.

nano_o

2년 전discuss

The bug in the Paxos Made Simple paper is that Lamport forgot to mention that, upon accepting a proposal, an acceptor also implicitly promises not to accept any proposal in lower ballots. It's discussed at length here: https://stackoverflow.com/questions/29880949/contradiction-i...

nano_o

3년 전discuss

In your example, you can just add a variable that is incremented at every step and then use it to state your invariant that convergence must happen within 5 steps.

Sometimes you can encode properties that might initially seem hard to state in TLA+ in a similar way. Lamport has a recent paper explaining how to do that for hyperproperties such as information-flow security: http://lamport.azurewebsites.net/pubs/pubs.html?from=https:/...

nano_o

4년 전discuss

With fancy cryptography (e.g. zero-knowledge proofs), you can allow the public to verify that the tally is correct while keeping votes secret. It's called end-to-end verifiable voting, and this is a good introduction: https://www.microsoft.com/en-us/research/publication/end-end...

The idea is that people post their votes publicly, but encrypted, and there's a procedure (based on zero-knowledge proofs) that allows to check that an encrypted vote is correctly accounted for in the tally without decrypting said vote. If sufficiently many voters post their encrypted votes (and if it's not too predictable who will do so), a wrong tally will be detected with high probability.

comments