I just stumbled upon Solidus, a proposed Cryptocurrency based on permissionless Byzantine Consensus:
In summary, this work presents Solidus, a scalable and incentive compatible cryptocurrency based on a fault-tolerant committee and permissionless Byzantine consensus. It is secure against withholding attacks such as selfish mining and provides instantaneous confirmation of transactions. Perhaps a limitation of Solidus is that the protocol is currently rather complex. It remains interesting future work to simplify and improve the Solidus protocol.
Solidus uses PoW for leader election to adapt the Practical Byzantine Fault Tolerance (PBFT) protocol to a permissionless setting. It comes with a whole set of incentive
mechanisms for different kinds of actions. As far as I can tell, it's far more sophisticated than BitcoinNG and ByzCoin and (promises) offers quite some advantages over them. However, it still relies on the assumption that at least 2/3 of the computing power is controlled by honest nodes.
The PBFT protocol is notoriously complicated! There is a derivative called RAFT that is simpler and easier to develop, but there is still a lot of complexity involved.
It's a novel idea though, one that I myself briefly researched quite some time ago, but I decided to steer clear of modifying traditional Byzantine consensus algorithms with POW/POS et all for a number of reasons.
Traditional byzantine consensus algorithms are designed to be used in private/permissioned systems (which is why a lot of companies touting private blockchains are using them as their consensus foundation).
They make an implicit assumption that the majority of actors in the system are permissioned, and that faults will most likely be hardware failures, connection issues and such....not actors that defect maliciously.
From their inception that assumption has held largely true and they have performed very well at enabling fault tolerant synchronization of data-centers and the like across the globe for many years, with almost all of the big centralized players using some variation of PBFT/RAFT to do so.
Permissionless however is a different beast altogether. Using POW as the function to determine leadership is a nice idea, and it does mitigate Sybil to a large degree...but...that still leaves a rather large problem...DDOS.
I skimmed the paper that you mentioned and I could find no mechanism detailed to prevent DDoS (perhaps I missed it? I plan to read in more detail tomorrow as its 4AM now). It mentions at the end of the paper that DDoS is harder to perform due to the committee, but the presence of the committee, while it might help to prevent complete stalls, doesn't appear to reduce disruption possibilities IMO. For the record the ease of DDoS, and the difficulty in guarding against them was the main issue that caused me to swiftly abandon my own research.
The issue lies in the fact that with a permissionless leader based Byzantine algorithm, it is trivial to discover who you need to DDoS to disrupt the network as you are internal to the network itself!
The "timeouts" of PBFT are required so that a node can monitor the current leader and signal when it thinks an election process is required. It also means you know who to attack so that an election signal is broadcast from the network majority, the processes is triggered, and once complete, you now know your new target.
Repeating that process can deadlock the network in a never ending cycle of elections where no transactions get processed (or processed very slowly).
This DDoS technique is more difficult in a permissioned environment as you are unable to determine who is the leader of that network unless you have managed to obtain permission. Even then, safe-guards can be implemented that can detect DDoS attacks much easier and ban or remove that node from the network topology and revoke connection permissions.
With permissionless thats not possible, obviously, as the attacker just spins up another node and re-connects and is immediately able to discover who to attack.