I recently watched Ethan Buchman rebuild talk. It reminded me again of https://www.nkn.org and Cellular Automata by Stephen Wolfram. This seems a great way to further decentralize a network and also improve the scalability. NKN implemented their code actually in Go, and it might be worth to explore: https://github.com/nknorg/nkn
Initially, a combination of cosmos + nkn was my idea for the cosmos hackatom in Berlin, but it was way too complicated. Especially, since I only started too look into cosmos at this point.
Sure, I can give it a try. Cellular automata consensus tries to improve the efficiency/scalability of the whole consensus by focusing on some simple rules between nodes and their neighbors (instead of the whole system). So basically, it tries to mimic nature. To take Ethan Buchman’s hurricane example: The state/speed of the different layers of a hurricane depend on the neighbor molecules. Not every molecule knows the state of every other molecule.
This basically results in a reduction of the number of messages, which need to be sent in the network in order to archive consensus. I believe in PBFT, the number of necessary messages is O(N²), whereas NKN claims that to reduce this to O(N). IOTA also currently researches this topic, see: https://coordicide.iota.org/module5.1.1
In general, I think the approach makes sense and is an interesting research topic. I’m not sure NKN, IOTA or anyone else has really nailed it and a bullet proof solution.
Are there any consensus algorithms built on cellular automata which also have a formal proof of correctness in terms of temporal logic? (especially model checkable ones like TLA+ / PlusCal)
That’s a good point. Not that I know of. I only know about the Majority Vote Cellular Automata (MVCA) and the simulation/simplified mathematical proof in the NKN whitepaper (and some older papers). But there are a lot of information missing/outdated. It’s definitely different from their actual implementation. Apparently, they wanted to release more information on their wiki in the coming weeks: https://github.com/nknorg/nkn/wiki So I will keep you posted in case they actually publish something.