We present an algorithm for totally ordered messages in the face of network partitions and site failures. The algorith always allows a majority of connected processors in the network to make progress (i.e. to order messages), if they remain connected for sufficiently long, regardless of past failures. Furthermore, our algorithm always allows processors to initiate messages, even when they are not members of a connected majority component in the network. Thus, messages can eventually become totally ordered even if their initiator is never a member of a majority component. The algorithm guarantees that when a majority is connected, each message is ordered within two communication rounds, if no failure occur during these rounds.