They don't actually have to be online at the same time (and they don't care about whether Charlie is online or not: it's a pairwise protocol): they just to be able to send and receive one another messages, and to store state. Fortunately the former is some Signal's quite good at, and storing state is something that phone hard drives are quite good at.
> Also, how does this protocol even help? What's the use case? It allows participants to discover mutual contacts, but what then? Do we use Bob as a web-of-trust style introducer? What if Alice doesn't even want to talk to Charlie? Do we do this for all the friends Alice has in common with Bob? Do we do this for all the friends Alice has in common with everyone?
It's the exact same use case as Signal's existing contact-discovery code, only private: it enables Alice & Bob to share information about a mutual acquaintance, e.g. Charlie. This might be used to share Charlie's key ID, in a trust on first use style. Note that this is no less secure than everyone everywhere trusting Open Whisper Systems on first use.
The idea is that when one starts using Signal, one exchanges keys in some out-of-band mechanism (NFC is a likely candidate) with an acquaintance, and then from that person get keys of mutual acquaintances, and from then others, and so on and so forth. Whenever you add a new acquaintance, one can reiterate the same protocol with all previous acquaintances (it's amenable to batching, too, which is nice) in order to propagate that information.
It may have some interesting uses in a certificate transparency sense, but I don't know about that.
> You end your last post with "So, problem solved" but I'm not sure this protocol even solves any practical problems for the Signal use case
It solves the exact same problems the Signal contact-discovery protocol solves, without actually revealing all one's contacts to OWS. That's all. If it did nothing more than that, it would be a good thing.
