Depending how strict you want to be about this, torrents and Secure Scuttlebutt are pretty good in this respect. I especially love Secure Scuttlebutt because it simply makes the client the store of which messages it's seen which also means there is no authoritative view of the whole network but that's by design.
But probably the even better example here is email. It's the OG federated protocol and nobody thinks of it that way. Probably because casual users have consolidated around a handful of convenient clients (gmail, hotmail, whatever) and not thought too hard about how emails get exchanged from one corporate mail server to another.