This document describes a protocol for reliably synchronizing states of nodes in a distributed environment through use of a Scalable Atomic Multicast (SAM) Service that ensures both atomicity and total order among messages sent to a multicast group. In addition to possessing good scalability property, this fault-tolerant protocol does not require explicit knowledge of multicast group membership, allows for non-disturbing state synchronization, and supports asynchronous non-blocking communications. According to one aspect of this invention, a dedicated sequencer is responsible solely for assigning sequence numbers to the multicast messages. The sequencer does not multicast the messages. Another aspect of the invention is the use of receiver-driven negative acknowledgments. According to third aspect, the invention supports message consolidation and garbage collection.