OpenPGP has been dealing with multiple recipients since forever with no back channel even.
> ...aren't storing messages in a central server,...
Who cares if we are doing E2E?
> ...and those devices can be unavailable for indeterminate amounts of time and no guarantee that a subset of devices having the complete chat history will ever be on at the same time to sync.
You only have to store the encrypted messages for each individual client until they connect again. If you are doing perfect forward secrecy then the client has to keep the decryption key around until the next connection so the server stored messages can be decoded. Then the key is destroyed.
That's the Apple "You're not supposed to use our device that way" approach, and again, while it works for a huge swath of users and I am completely cognizant I'm in a tiny contrarian minority, it still and nevertheless feels like a hostile user experience.
Note that "Switching devices like that" is ever so tiny a misnomer; I am "Using multiple devices" (not replacing my phones permanently etc, which I get is a more difficult scenario... and one that Whatsapp historically deals with in the most insecure fashion imaginable; until recently their FAQ held explanations that you may get somebody else's messages if you get their phone number; or that if you switch your own phone number you need to email support and wait; it really feels they focused on the E2E encryption, important to tiny proportion of their userbase, over any other security consideration; but again... I get I'm alone in this perception :)
It's not that far fetched to make every conversation a implicit group conversation with n devices on both sides.
None of those are problems affecting Signal.
You're not supposed to be switching between devices like that. You're supposed to be proxying your messages through your primary device (i.e. cell phone) using the web interface.
Like the UX is bad for people with two phones and the mobile experience of WhatsApp web is nonexistent so that kinda sucks but "having one phone, and sometimes a tablet/laptop with the web interface" covers a lot of people.
E2E is hard when you have to route messages to multiple devices, aren't storing messages in a central server, and those devices can be unavailable for indeterminate amounts of time and no guarantee that a subset of devices having the complete chat history will ever be on at the same time to sync.