MDVM System Concept, Paging Latency and Round-2 Randomized Leader Election Algorithm in SG
Susmit Bagchi*, Hafizur Rahaman**, and Purnendu Das***
*Deptt. of Information Technology, Sikkim Manipal Inst. of Technology, Majitar, Sikkim, India
**Deptt. of Information Technology, Bengal Engineering and Science University, Shibpur, Howrah, India
***School of Information Technology, Bengal Engineering and Science University, Shibpur, Howrah, India
The future trend in the computing paradigm is marked by mobile computing based on mobile-client/server architecture connected by wireless communication network. However, the mobile computing systems have limitations because of the resource-thin mobile clients operating on battery power. The MDVM system allows the mobile clients to utilize memory and CPU resources of Server-Groups (SG) to overcome the resource limitations of clients in order to support the high-end mobile applications such as, m-commerce and virtual organization (VO). In this paper the concept of MDVM system and the architecture of cellular network containing the SG are discussed. A round-2 randomized distributed algorithm is proposed to elect a unique leader and co-leader of the SG. The algorithm is free from any assumption about network topology, buffer space limitations and is based on dynamically elected coordinators eliminating single point of failure. The algorithm is implemented in distributed system setup and the network-paging latency values of wired and wireless networks are measured experimentally. The experimental results demonstrate that in most cases the algorithm successfully terminates in first round and the possibility of second round execution decreases significantly with the increase in the size of SG (|Na|). The overall message complexity of the algorithm is O(|Na|). The comparative study of network-paging latencies indicates that 3G/4G mobile communication systems would support the realization of MDVM system.
-  G. Antonoiu and P. K. Srimani, “A Self-Stabilizing Leader Election Algorithm for Tree Graphs,” In the Journal of Parallel and Distributed Computing, 34(2), pp. 227-232, 1996.
-  S. Vasudevan, J. Kurose, and D. Towsley, “Design and Analysis of a Leader Election Algorithm for Mobile Ad-hoc Networks,” In the proc. of 12th IEEE International Conference on Network Protocols, 2004.
-  S. Dulman et al., “Wave Leader Election Protocol for Wireless Sensor Networks,” In proc. of 3rd International Symposium on Mobile Multimedia Systems and Applications, pp. 43-50, 2002.
-  S. Vasudevan, B. Decleene, I. Immerman, J. Kurose, and D. Towsley, “Leader Election Algorithms for Wireless Ad-hoc Networks,” DARPA Information Survivability Conference and Exposition, Vol.I, IEEE CS Press, 2003.
-  N. Malpani, J. Welch, and N. Vaidya, “Leader Election Algorithms for Mobile Ad-hoc Networks,” In proc. of 4th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, Boston, 2000.
-  I. Gupta, R. Renesse, and K. Birman, “A Probabilistically Correct Leader Election Protocol for Large Groups,” In proc. of International Symposium on Distributed Computing, Spain, 2000.
-  G. Itkis, C. Lin, and J. Simon, “Deterministic, Constant Space, Self-Stabilizing Leader Election on Uniform Rings,” In proc. of 9th International Workshop on Distributed Algorithms, Springer LNCS, 1995.
-  G. Frederickson and N. Lynch, “The Impact of Synchronous Communication on the Problem of Electing a Leader in a Ring,” 16
Annual ACM Symposium on Theory of Computing, pp. 493-503, 1984.
-  D. Ellie and P. Prakash, “Leader Election and Distributed Consensus with Quantum Resources,” Tech. Rep., McGill University, Canada, 2005.
-  G. Frederickson and N. Lynch, “Electing a Leader in a Synchronous Ring,” In the Journal of ACM, Vol.34, No.1, pp. 98-115, 1987.
-  B. Joffroy, G. Maria, and C. Johnen, “Randomized Self-Stabilizing and Space Optimal Leader Election under Arbitrary Scheduler on Rings,” Research Report No.1225, L.R.I.,
-  H. Attiya and J. Welch, “Distributed Computing: Fundamentals, Simulations and Advanced Topics,” London, UK, McGraw-Hill, 1998.
-  G. Tel, “Introduction to Distributed Algorithms,” 2nd Edition, Cambridge University Press, 2000.
-  N. Lynch, “Distributed Algorithms,” Morgan Kaufmann Publishers, 1996.
-  R. Gallager et al., “A Distributed Algorithm for Minimum Weight Spanning Trees,” In ACM Transactions on Programming Languages and Systems, Vol.4, No.1, pp. 66-77, 1983.
-  D. Peleg, “Time Optimal Leader Election in General Networks,” In Journal of Parallel and Distributed Computing, Vol.8, No.1, pp. 96-99, 1990.
-  J. Burns, “A Formal Model for Message Passing Systems,” TR 91, Indiana University, USA, 1980.
-  D. Hirschberg et al., “Decentralized Extrema-Finding in Circular Configurations of Processors,” Communication ACM, Vol.23, No.11, pp. 627-628, 1980.
-  B. Chor and C. Dwork, “Randomization in Byzantine Agreement,” Advances in Computing Research, Vol.5, pp. 443-498, 1989.
-  S. Bagchi, “Design Architecture and Model of MDVM System,” In proc. of IFIP International Conference on Intelligence in Communication Systems, Springer-Verlag LNCS, Vol.3283, 2004.
-  M. Nadia and Y. Kin, “DesigningWireless Enterprise Applications on Mobile Devices,” ICITA 2002.
-  MOWAHS, IDI, NTNU,
-  E. Pitoura et al., “Dealing with Mobility: Issues and Research Challenges,” TR-CSD-93-070, 1993.
-  R. Badrinath et al., “Impact of Mobility on Distributed Computations,” ACM OS Review, 1993.
-  A. Black and J. Inouye, “System Support for Mobility,” ACM SIGOPS, Ireland, 1996.
-  E. W. Weisstein, “Random Number,” From Math World – A Wolfram Web Resource,
-  B. Schilit and D. Duchamp, “Adaptive Remote Paging for Mobile Computers,” TR-CUCS-004-91, Columbia University, February, 1991.
-  Y. Shigemori et al., “A proposal of a Memory Management Architecture for Mobile Computing Environment,” IEEE DEXA, 2000.