In this work we present a novel protocol for total ordering of messages in asynchronous distributed environments prone to machine and communication link failures. Using the protocol as a building block, we constructed a Totally Ordered Group Communication (TOGC) system, i.e., a group communication service with a totally ordered multicast primitive. TOGC is a powerful infrastructure for building distributed fault-tolerant applications such as totally ordered broadcast, consistent object replication, distributed shared memory, Computer Supported Cooperative Work (CSCW) applications and distributed monitoring and display applications. An important contribution of the total ordering protocol described in this work is its ability to dynamically adjust the message delivery flow to changes in the transmission rates of the participating processes. The adaptation is accomplished by assigning delivery priorities (weights) to messages according to sender transmission rates. The priorities are det...