Abstract
We present a new approach, the GeoQuorums approach, for implementing atomic read/write shared memory in ad hoc networks. Our approach is based on abstract nodes associated with certain geographic locations. We assume the existence of focal points, geographic areas that are normally “populated” by mobile hosts. For example, a focal point may be a road junction, a scenic observation point, or a water resource in the desert. Mobile hosts that happen to populate a focal point participate in implementing shared atomic putget objects, using a replicated state machine approach. These objects are then used to implement atomic read/write operations. The GeoQuorums algorithm defines certain intersecting sets of focal points, known as quorums. The quorum systems are used to maintain the consistency of the shared memory. We present a mechanism for changing quorum systems on the fly, thus improving efficiency. Overall, the new GeoQuorums algorithm efficiently implements read and write operations in a highly dynamic, mobile network.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Dolev, S., Pradhan, D.K., Welch, J.L.: Modified tree structure for location management in mobile environments. Computer Communications: Special Issue on Mobile Computing 19, 335–345 (1996)
Lamport, L.: On interprocess communication - parts I and II. Distributed Computing 1, 77–101 (1986)
Herlihy, M.P., Wing, J.M.: Linearizability: A correctness condition for concurrent objects. ACM Trans. on Programming Languages and Systems 12, 463–492 (1990)
Navas, J.C., Imielinski, T.: Geocast - geographic addressing and routing. In: ACM/IEEE Intl. Conference on Mobile Computing and Networking, pp. 66–76 (1997)
Camp, T., Liu, Y.: An adaptive mesh-based protocol for geocast routing. Journal of Parallel and Distributed Computing: Special Issue on Mobile Ad-hoc Networking and Computing, 196–213 (2002)
Gifford, D.K.: Weighted voting for replicated data. In: Proceedings of the seventh symposium on operating systems principles, pp. 150–162 (1979)
Thomas, R.H.: A majority consensus approach to concurrency control for multiple copy databases. Transactions on Database Systems 4, 180–209 (1979)
Upfal, E., Wigderson, A.: How to share memory in a distributed system. Journal of the ACM 34, 116–127 (1987)
Attiya, H., Bar-Noy, A., Dolev, D.: Sharing memory robustly in message-passing systems. Journal of the ACM 42, 124–142 (1995)
Prisco, R.D., Fekete, A., Lynch, N.A., Shvartsman, A.A.: A dynamic primary configuration group communication service. In: Proceedings of the 13th International Symposium on Distributed Computing, pp. 64–78 (1999)
Lynch, N., Shvartsman, A.: RAMBO: A reconfigurable atomic memory service for dynamic networks. In: Proc. of the 16th Intl. Symp. on Distributed Computing, pp. 173–190 (2002)
Gilbert, S., Lynch, N., Shvartsman, A.: RAMBO II: Rapidly reconfigurable atomic memory for dynamic networks. In: Proc. of the Intl. Conference on Dependable Systems and Networks, pp. 259–269 (2003)
Garcia-Molina, H., Barbara, D.: How to assign votes in a distributed system. Journal of the ACM 32, 841–860 (1985)
Herlihy, M.: Dynamic quorum adjustment for partitioned data. Trans. on DB Systems 12, 170–194 (1987)
El Abbadi, A., Skeen, D., Cristian, F.: An efficient fault-tolerant protocol for replicated data management. In: Proc. ofthe 4th Symp. on Principles of Databases, pp. 215–228. ACM Press, New York (1985)
Dolev, D., Keidar, I., Lotem, E.Y.: Dynamic voting for consistent primary components. In: Proc. of the Sixteenth Annual ACM Symp. on Principles of Distributed Computing, pp. 63–71. ACM Press, New York (1997)
Englert, B., Shvartsman, A.: Graceful quorum reconfiguration in a robust emulation of shared memory. In: Proc. of the International Conference on Distributed Computer Systems (ICDCS 2000), pp. 454–463 (2000)
Haas, Z.J., Liang, B.: Ad hoc mobile management with uniform quorum systems. IEEE/ACM Transactions on Networking 7, 228–240 (1999)
Stojmenovic, I., Pena, P.E.V.: A scalable quorum based location update scheme for routing in ad hoc wireless networks. Technical Report TR-99-11, Computer Science, SITE, University of Ottawa (1999)
Karumanchi, G., Muralidharan, S., Prakash, R.: Information dissemination in partitionable mobile ad hoc networks. In: Proceedings of IEEE Symposium on Reliable Distributed Systems, pp. 4–13 (1999)
Dolev, S., Gilbert, S., Lynch, N.A., Shvartsman, A.A., Welch, J.L.: Geoquorums: Implementing atomic memory in ad hoc networks. Technical Report LCS-TR-900, MIT (2003)
Priyantha, N.B., Chakraborty, A., Balakrishnan, H.: The cricket location-support system. In: Proc. of the 6th ACM MOBICOM, pp. 32–43 (2000)
Ko, Y.B., Vaidya, N.: Geotora: A protocol for geocasting in mobile ad hoc networks. In: Proc. of the IEEE Intl. Conference on Network Protocols, pp. 240–249 (2000)
de Berg, M., van Kreveld, M., Overmars, M., Schwarzkopf, O.: Computational Geometry: Algorithms and Applications, 2nd edn. Springer, Heidelberg (2000)
Dolev, S., Schiller, E., Welch, J.: Random walk for self-stabilizing group communication in ad-hoc networks. In: Proceedings of the 21st IEEE Symposium on Reliable Distributed Systems, pp. 70–79 (2002)
Lynch, N.: Distributed Algorithms. Morgan Kaufmann, San Francisco (1996)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dolev, S., Gilbert, S., Lynch, N.A., Shvartsman, A.A., Welch, J.L. (2003). GeoQuorums: Implementing Atomic Memory in Mobile Ad Hoc Networks. In: Fich, F.E. (eds) Distributed Computing. DISC 2003. Lecture Notes in Computer Science, vol 2848. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-39989-6_22
Download citation
DOI: https://doi.org/10.1007/978-3-540-39989-6_22
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-20184-7
Online ISBN: 978-3-540-39989-6
eBook Packages: Springer Book Archive