A method, system, and computer-readable medium is described for facilitating interactions between software programs by providing a reliable data queuing service that enables the programs to store and retrieve elements of data queues. In some situations, the data queuing service is provided to users who purchase usage of the data queuing service for application programs executed by or otherwise affiliated with the users. In addition, accessibility of the data queuing service to remote executing programs may be enhanced via a defined API of the data queuing service, such as a Web services-based API. Availability of the data queuing service may also be enhanced in some situations by using multiple alternative distributed systems for a data queue such that each of the alternative systems stores a subset of the elements of the data queue.