A de-centralised network, with chosen usernames. Is it possible?

I was wondering if it would be possible to have a de-centralised network, which still allowed each person to choose a username. As an example, imagine a de-centralised Twitter, where you go to register through a client, and if the username isn't taken, it gives you the username. If it is taken, it doesn't allow you to take it. If they owned the account with that username, they would then be able to login to their account from a new client, on a new device. I'm wondering if this is possible? A few years ago, I'd have assumed not, but now with de-centralised systems growing popular, such as with Bitcoin, I'm wondering if it is?