Exactly-once semantics in a replicated messaging system

Abstract

A distributed message delivery system can use replication to improve performance and availability. However, without safeguards, replicated messages may be delivered to a mobile device more than once, making the device's user repeat actions (e.g., making unnecessary phone calls, firing weapons repeatedly). In this paper we address the problem of exactly-once delivery to mobile clients when messages are replicated. We define exactly-once semantics and propose algorithms to guarantee it. We also propose and define a relaxed version of exactly-once semantics which is appropriate for limited capability mobile devices. We study the relative performance of our algorithms compared to weaker at-least-once semantics, and find that the performance overhead of exactly-once can be minimized in most cases by careful design of the system.