Commenced in January 2007
Frequency: Monthly
Edition: International
Paper Count: 30124
On Bounding Jayanti's Distributed Mutual Exclusion Algorithm

Authors: Awadhesh Kumar Singh


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):

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 960


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