TITLE: Exactly-once Semantics in a Replicated Messaging System

AUTHORS:
Yongqiang Huang and Hector Garcia-Molina
Department of Computer Science
Stanford University
Stanford, CA 94305
{yhuang, hector}@cs.stanford.edu

KEYWORDS:
exactly-once semantics, exactly-once algorithms, replicated messaging
systems, distributed message delivery, mobile information access,
limited capability clients, PDAs

ABSTRACT:
A wide-area 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).  Alternatively,
they may not be delivered at all, making the user miss important
messages.  In this paper we address the problem of exactly-once
delivery to mobile clients when messages are replicated globally.  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.