Exactly-once semantics in a replicated messaging …

1 Exactly-once semantics in a replicated messaging systemAbstractA distributed message delivery system can use repli-cation to improve performance and availability. How-ever, without safeguards, replicated messages may bedelivered to a mobile device more than once, makingthe device s user repeat actions ( , making unnec-essary phone calls, firing weapons repeatedly). In thispaper we address the problem of Exactly-once deliveryto mobile clients when messages are replicated . Wedefine Exactly-once semantics and propose algorithmsto guarantee it. We also propose and define a relaxedversion of Exactly-once semantics which is appropri-ate for limited capability mobile devices.

2 We studythe relative performance of our algorithms comparedto weaker at-least-once semantics , and find that theperformance overhead of Exactly-once can be mini-mized in most cases by careful design of the IntroductionIn areplicated messaging system , messages are repli-cated at various servers, pending delivery to mobileclients. When the client makes a connection to thenetwork, it contacts any of the servers, and downloadsits pending messages. If messages are not replicated ,the client could not get its messages when its onlyserver was down. Furthermore, the connection to itsserver may be slow, making it impossible to down-load all the messages in a reasonable time.

3 Both ofthese problem are solved with replication: the clienthas a choice of servers, and can contact one that is nearby at the time of connection and that offersgood response replication is useful in critical applicationswhere it is important to deliver messages as soon as aclient makes any connection. For instance, in a mili-tary scenario, it is critical to get messages to units inthe field, no matter at what point they connect, andno matter how short their connection is. Even fornon-critical applications, replication can be very use-ful. For example, when an American traveler visitsEurope, it would be much more convenient to accesshis or her emails through a local server, rather thanrelying on a slow trans-Atlantic , of course, introduces the problem ofduplicate delivery.

4 A client can connect to one serverand download messageM1, and later connect to adifferent server and receiveM1a second time. Dupli-cate delivery can range from disastrous to simply annoying. For example, a message fire missile or buy stock may cause an action to be unintention-ally performed twice with clearly undesirable conse-quences. In other cases, a duplicate message to callFred back can be simply confusing, since the recip-ient does not know whether Fred wants to talk tohim/her a second this paper we study mechanisms for ensuringthat messages are deliveredexactly once(no deliveryand duplicate delivery must be ruled out).

5 While thisproblem has been extensively studied in the past (seeour related work section), we believe it is importantto revisit the problem in the context of a replicatedmessage system for mobile clients. In particular, wewill Study how servers with replicas can coordinateto eliminate or reduce the likelihood of duplicatedelivery. Explore duplicate elimination mechanisms thatmay be appropriate for clients with no or limitedstable storage. Study weaker Exactly-once semantics that maybe useful in a mobile environment. Present an evaluation metric for comparingexactly-once mechanisms, useful for highlightingtheir weaknesses or strengths in a mobile stress that we are not discovering new mech-anisms for Exactly-once delivery.

6 All of the ideaswe present ( , sequence numbers to identify dupli-cates) are well known. Our goal is instead to adaptthese well known building blocks into mechanismsthat are well suited for a mobile environment, and toevaluate the also stress that not all applications requirestrict Exactly-once semantics . However, if we can finda mechanism that guarantees Exactly-once delivery ata reasonable performance and complexity cost, then1we may still want to use it. Thus, we believe thatregardless of the application, it is important to un-derstand how Exactly-once delivery can be achievedwith replicated messages, so that an informed deci-sion can be made regarding message delivery , note that some applications may not re-quire Exactly-once delivery because they implementtheir own safeguards.

7 For example, the message tofire a missile may specify which missile to fire, sothat a duplicate message will not cause a second fir-ing. However, these applications mechanisms ( ,missile numbers, application sequence numbers) areidentical to the mechanisms we describe here. Thus,whether Exactly-once is guaranteed by the messagingsystem or by the application, the issues are the same,and the results we present here are structure of our paper is as follows. We start inSection 2 by defining more precisely our frameworkand the notion of Exactly-once delivery. The algo-rithms for guaranteeing Exactly-once semantics aregiven in Section 3.

8 Section 4 describes our perfor-mance model, while Section 5 presents selected com-parisons of the strategies. We discuss related work inSection 6 and conclude in Section Delivery semanticsFigure 1 illustrates a replicated messaging are located at various locations around theglobe. The servers are connected by a fixed wide areanetwork, , the Internet. These servers are respon-sible for storing and delivering messages to call these messagesnotesto distinguish them fromother network traffic that does not require deliveryguarantees ( , Exactly-once semantics ). When anew note is generated, it is replicated to all serversfor delivery to the client.

9 The replication happensunder the guidance of a separate replication proto-col, which we do not consider in detail client, which is typically a wireless informationaccess device like a PDA, stays disconnected from theserver network most of the time. It occasionally es-tablishes a wireless connection into a network accesspoint, which then lets it communicate with one of theservers to get its notes. Because client connectionscan be short lived, or may not provide good connec-tivity to all servers, it is important to replicate notesat multiple servers. This way, when a connection ismade, note delivery can be made from the server thatoffers best service.

10 However, without any safeguards,a note can be delivered more than once to a client bydifferent semantics of a note specify the required deliv-Figure 1: replicated message delivery properties, , whether duplicates are allowed,or whether the note needs to be delivered by a dead-line. In this paper, we focus on the following seman-tics: Exactly-once : a note should eventually be deliv-ered to its target once, and only mentioned earlier, notes that lead to irrevoca-ble changes in the physical world often need Exactly-once guarantees. We focus on notes destined for amobile, wireless device, for instance, asking someoneon the shipping floor to send some goods, instructinga soldier in the field to initiate some action, askinga traveling manager to change the asking price foran acquisition, or telling a nurse in the emergencydepartment to administer some drugs.