Absolute timestamps cannot be trusted in a byzantine environment, so we do precisely as you suggest - messages are transmitted with pointers to the previous message(s) in the room message graph, so you get a partial ordering within the room (just like git). We also sign the messages into a merkle graph (like git) to stop the shared datastructure being tampered with.