The other idea I had once, instead of a federated model, was no servers.
Bittorrent based social network. Messages, pictures, whatever, all go into the swarm. If I want to follow you, my client asks around until it find a copy. The more people follow someone the easier it is to get copies when they are offline.
This would also have a sort of weird non-chronological arrival order. Messages that more people see arrive first, as do messages from people online.