Multicast is an efficient mechanism for distributing data from one sender to multiple receivers. Many applications need a reliable multicast service which is not provided by the existing IP multicast protocol. Providing such a service on a large scale requires efficient algorithms for error recovery. This dissertation presents a randomized reliable multicast protocol called RRMP which has demonstrably achieved several good properties. The protocol eliminates message implosion by diffusing the responsibility of error recovery among all members in the group and improves the robustness of the system against process failures. It provides good local recovery by dynamically organizing members into an error recovery hierarchy according to their geographic locations. It optimizes buffer management through an innovative two-phase buffering algorithm that explicitly addresses the variances in delivery latency for large multicast groups. The algorithm reduces buffer requirements by adaptively allocating buffer space to messages most needed in the system and by spreading the load of buffering among all members in the group. The key idea of RRMP is to use randomization as a powerful technique to achieve high robustness and efficiency in reliable multicast communications. The RRMP protocol works well within the existing IP multicast framework and does not require additional support from network routers. Both analysis and experimental results show that the performance penalty due to randomization is low and can be tuned according to application requirements.