Why not have everyone hold a copy of some arbitrarily old section of the history of posts (in their client, as a separate program on their device, whatever) with a choice to hold the entire history.

Then, you connect to some peers, add a post by communicating it with them, and they communicate with others and so on, adding it to their local copy, until everyone has the message? Essentially, everyone is a relay.