On Bounding Jayanti's Distributed Mutual Exclusion Algorithm

Authors: Awadhesh Kumar Singh

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.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1329729

References:

[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.