Most trace-based proof systems for networks of processes are known to be incomplete. Extensions to achieve completeness are generally complicated and cumbersome. In this thesis, we isolate the componenets of a trace-based network proof system that are necessary and sufficient to achieve relative completeness. We then consider the expressiveness required of any trace logic that encodes these componenets.