You can have fully decentralized identities quite trivially: just create a public/private key. No consensus algorithms required. With browsers now supporting synchronization features to connect the browsers on all systems used by a single user, such a system could actually work quite well now, without the usability issues it would once have had.