Those are CP which is impossible in a distributed messaging system where it has to obviously be AP. Otherwise you'd have to guarantee that everyone involved is always online (no partition) to make progress on sending messages!

I think I have this right anyways. (CAP theorem for anyone curious.)

I think the most important property to preserve is causality; that is, if a user sends a message B after they have read (i.e., received) a message A, then B should come after A for everyone, because B depends on A. Basically use a Lamport clock.