On Bounding Jayanti's Distributed Mutual Exclusion Algorithm
Jayanti-s algorithm is one of the best known abortable mutual exclusion algorithms. This work is an attempt to overcome an already known limitation of the algorithm while preserving its all important properties and elegance. The limitation is that the token number used to assign process identification number to new incoming processes is unbounded. We have used a suitably adapted alternative data structure, in order to completely eliminate the use of token number, in the algorithm.
[1] P. Jayanti, "Adaptive and efficient abortable mutual exclusion," in Proc.
22nd ACM Annual Symposium on Principles of Distributed Computing,
July 13-16, 2003, pp. 295-304.
[2] P. Jayanti, "Efficient and practical constructions of LL/SC variables," in
Proc. 22nd ACM Annual Symposium on Principles of Distributed
Computing PODC 2003, July 13-16, 2003, pp. 285-294.
[3] D. L. Weaver and T. Germond, The SPARC Architecture Manual.
Version 9, SPARC International, Inc.
[4] Intel Corporation. Intel Itanium Architecture Software Developer's
Manual, Volume 1: Application Architecture Revision 2.1, Oct. 2002.
[5] J. M. Tendler, S. Dodson, S. Fields, H. Le, and B. Sinharoy, IBM eserver
POWER4 System Microarchitecture, IBM, Oct. 2001.
[6] MIPS Computer Systems, MIPS64 Architecture for Programmers.
Volume II: The MIPS64 Instruction Set, Aug. 2002.
[7] R. Site, Alpha Architecture Reference Manual. Digital equipment
Corporation, 1992.
[8] P. Jayanti, "f-arrays: Implementation and applications," in Proc. 21st
ACM Annual Symposium on Principles of Distributed Computing PODC
2002, July 21-24, 2002, pp. 270-279.
[9] L. Lamport, "Time, clocks and the ordering of events in a distributed
system," Communications of the ACM, 1978, 21(7): 558-565.
[10] P. Tang, P.-C. Yew, and C.-Q. Zhu, "A parallel linked list for sharedmemory
multiprocessors," in Proc. 13th IEEE Annual International
Conference on Computer Software and Applications COMPSAC-89,
Sep. 20-22, 1989, pp. 130-135.
[11] M. J. Quinn, Parallel Computing: Theory and Practice. 2/e, McGraw-
Hill Companies, Inc., 1994.
[12] E. G. Jr. Coffman and P. J. Denning, Operating Systems Theory.
Prentice-Hall, Englewood Cliffs, NJ, 1973.
[13] V. J. Marathe, M. Moir, and N. Shavit, "Composite abortable locks," in
Proc. 20th IEEE International Parallel and Distributed Processing
Symposium IPDPS-06, April 25-29, 2006, pp. 1-10.
[14] H. Maegawa, "Memory organization and management for linked data
structures," in Proc. 19th ACM Annual Conference on Computer Science,
April 1991, pp. 105-112.
[1] P. Jayanti, "Adaptive and efficient abortable mutual exclusion," in Proc.
22nd ACM Annual Symposium on Principles of Distributed Computing,
July 13-16, 2003, pp. 295-304.
[2] P. Jayanti, "Efficient and practical constructions of LL/SC variables," in
Proc. 22nd ACM Annual Symposium on Principles of Distributed
Computing PODC 2003, July 13-16, 2003, pp. 285-294.
[3] D. L. Weaver and T. Germond, The SPARC Architecture Manual.
Version 9, SPARC International, Inc.
[4] Intel Corporation. Intel Itanium Architecture Software Developer's
Manual, Volume 1: Application Architecture Revision 2.1, Oct. 2002.
[5] J. M. Tendler, S. Dodson, S. Fields, H. Le, and B. Sinharoy, IBM eserver
POWER4 System Microarchitecture, IBM, Oct. 2001.
[6] MIPS Computer Systems, MIPS64 Architecture for Programmers.
Volume II: The MIPS64 Instruction Set, Aug. 2002.
[7] R. Site, Alpha Architecture Reference Manual. Digital equipment
Corporation, 1992.
[8] P. Jayanti, "f-arrays: Implementation and applications," in Proc. 21st
ACM Annual Symposium on Principles of Distributed Computing PODC
2002, July 21-24, 2002, pp. 270-279.
[9] L. Lamport, "Time, clocks and the ordering of events in a distributed
system," Communications of the ACM, 1978, 21(7): 558-565.
[10] P. Tang, P.-C. Yew, and C.-Q. Zhu, "A parallel linked list for sharedmemory
multiprocessors," in Proc. 13th IEEE Annual International
Conference on Computer Software and Applications COMPSAC-89,
Sep. 20-22, 1989, pp. 130-135.
[11] M. J. Quinn, Parallel Computing: Theory and Practice. 2/e, McGraw-
Hill Companies, Inc., 1994.
[12] E. G. Jr. Coffman and P. J. Denning, Operating Systems Theory.
Prentice-Hall, Englewood Cliffs, NJ, 1973.
[13] V. J. Marathe, M. Moir, and N. Shavit, "Composite abortable locks," in
Proc. 20th IEEE International Parallel and Distributed Processing
Symposium IPDPS-06, April 25-29, 2006, pp. 1-10.
[14] H. Maegawa, "Memory organization and management for linked data
structures," in Proc. 19th ACM Annual Conference on Computer Science,
April 1991, pp. 105-112.
@article{"International Journal of Information, Control and Computer Sciences:50275", author = "Awadhesh Kumar Singh", title = "On Bounding Jayanti's Distributed Mutual Exclusion Algorithm", abstract = "Jayanti-s algorithm is one of the best known abortable mutual exclusion algorithms. This work is an attempt to overcome an already known limitation of the algorithm while preserving its all important properties and elegance. The limitation is that the token number used to assign process identification number to new incoming processes is unbounded. We have used a suitably adapted alternative data structure, in order to completely eliminate the use of token number, in the algorithm.
", keywords = "Abortable, deterministic, local spin, mutual exclusion.", volume = "2", number = "2", pages = "271-7", }
