In either case, there appears to be a tradeoff between availability and maintaining consistency. If the ACID properties were to be taken seriously (as is necessary in many applications), then it is expensive, if not impossible, to provide high availability.Works citedCaching Strategies for Mobile DevicesRandolph ChungDepartment of Computer Science, Cornell UniversityIthaca, New York1) IntroductionWith the increasing popularity of Per-sonal Digital Assistants (PDAs) and other mo-bile devices, new applications are being de-veloped to take advantage of the mobility andubiquitous nature of these devices. A largeclass of these applications are information-gathering in nature: for example, to look upstock quotes, local weather, traffic conditions,etc. Presumably, each of these queries are per-sonalized and depend on a profile that astored within the users' PDA. Although indi-vidual queries may be customized, with theproliferation of these applications, it is likelythat the same data (e.g. traffic condition in aparticular area) will be queried by a largenumber of users. Caching techniques are es-sential to minimize connection time for mo-bile devices and to make these systems scal-able.Unfortunately, traditional cachingstrategies are often not applicable nor usefulin mobile applications. To better understandwhy this is so, one must first understand tradi-tional caching strategies, and examine thecharacteristics of mobile devices:Traditional caching strategies for client-serverarchitectures: [2]Stateful: Server sends invalidation or refresh mes-sages Server keeps track of which clients arepresent Clients inform server when theyconnect/disconnectStateless: Server does not know about which clientsare connected, nor the age of clients’caches Server broadcasts state changes / invalida-tion reports as data changes [asynchro-nous] Server periodically broadcasts invalida-tion reports [synchronous]Characteristics of mobile devices:-1- Often disconnected Would like to minimize connection timeto save resourcesIn light of these limitations and require-ments, a number of researchers have beenworking on novel caching strategies that pro-vide the flexibility required for mobile appli-cations. This survey paper will present a num-ber of these strategies.2) ACID vs. BASEIn traditional database applications,the ACID (Atomicity, Consistency, Isolationand Durability) properties are considered tobe of paramount importance. The design ofcaching strategies thus reflected this require-ment. In order to maintain consistency be-tween data on a database system and datamaintained in caches, either:i) caches have to periodically check withmain database to verify that their data isstill valid; orii) the system has to notify caches of changeseither as they occur or on a periodic basis.While these strategies work well incases where the main server and the cachesare close together and well connected, a lot ofeffort must be expended to deal with caseswhen the subsystems cannot communicatewith each other. This may be due to tempo-rary network partitions, or failure of some ofthe components of the system. In either case,if data were to be written to the databasewhile part of the system is unavailable, somemeans must be available to reconcile conflictsin the data when the separated componentslater reappear. Methods for handling these sit-uations include:i) not allowing writes unless all componentsare reachable; this is obviously not desir-able unless partitions are very rare; ii) using a quorum-based technique, such thatonly writes to a group with some majorityof members are accepted; this does notwork well in small group settingsIn either case, there appears to be atradeoff between availability and maintainingconsistency. If the ACID properties were to betaken seriously (as is necessary in many appli-cations), then it is expensive, if not impossi-ble, to provide high availability.In mobile applications, mobile devicesare often disconnected for long periods oftime. This wrecks havoc with techniquesmentioned above that require, for the mostpart, continuous connectivity. In light of thefact that many of the applications that mobile-2-devices are used for do not require absoluteadherence to the ACID properties, strategieshave been developed that provide high avail-ability at the cost of absolute consistency.Some researchers have dubbed this level ofconsistency as BASE [4] – basically avail-able, soft-state, eventual consistency. Mostcaching strategies described to date for mo-bile system take this approach ([3]). Essen-tially, this is a “read-any, write-any” ap-proach, where data can be read from or writ-ten to the database (or other permanent stor-age) at any time, even if some components areunavailable. Conflicts in the data are resolvedas they arise, often by using semantic infor-mation and, though undesirable, sometimesby human intervention. BASE semantics aredesirable in cases where approximate answersdelivered quickly are more useful than exactanswers delivered slowly. 3) Paper summariesTo better understand different ap-proaches to caching strategies, this sectionwill summarize four papers describing re-search work done over the past few years atRutgers, CMU and the Xerox Palo Alto Re-search Center. As mentioned earlier, most ofthese approaches are based on the idea oftrading consistency for availability, thougheach paper attacks a different part of the prob-lem.a) “Replication and Mobility”, B. R.Badrinath and T. Imieliński. Depart-ment of Computer Science, RutgersUniversityThe premise of this paper is that mo-bility is the next most challenging issue facingdistributed systems and thus an important areaof research. This paper raises (though it doesnot answer) the following questions: What are the conditions under which weneed replication? What objects do we want to replicate? Atwhich level do we replicate data? Do wereplicate dynamically changing informa-tion such as location information? How does mobility affect users and