Distributed algorithm for K-entries to critical section based on the directed graphs

ABSTRACT

This paper proposes a token based mutual exclusion algorithm for distributed systems that allows K simultaneous entries to a critical section. In the algorithm, a logical directed graph is maintained in a connected network.This algorithm does not use sequence numbers, and the number of messages required to provide mutual exclusion, is between 0 and 2*(N-l) where N is the number of processes in the network.

REFERENCES

• 1: [1] O. S. F Carvalho and G. Roucairol, "On Mutual Exclusion in Computer Networks," Comm. ACM Vol. 26, 2 (1983), pp. 3-5.
• 2: K. M. Chandy , J. Misra, The drinking philosophers problem, ACM Transactions on Programming Languages and Systems (TOPLAS), v.6 n.4, p.632-646, Oct. 1984 [doi>10.1145/1780.1804]
• 3: D. Ginat , D. D . Sleator, A tight amortized bound for path reversal, Information Processing Letters, v.31 n.1, p.3-5, April 1989 [doi>10.1016/0020-0190(89)90101-4]
• 4: J. M. Helary , N. Plouzeau , M. Raynal, A distributed algorithm for mutual exclusion in an arbitrary network, The Computer Journal, v.31 n.4, p.289-295, August 1988
• 5: Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
• 6: [6] G. Lelann, "Distributed systems, Towards a Formal Approach," IFIP Congress, Toronto, Canada, (1977), pp. 155-160.
• 7: Mamoru Maekawa, A N algorithm for mutual exclusion in decentralized systems, ACM Transactions on Computer Systems (TOCS), v.3 n.2, p.145-159, May 1985 [doi>10.1145/214438.214445]
• 8: [8] M. L. Neilsen and M. Mizuno, "A DAG-Based Algorithm for Distributed Mutual Exclusion," Proc. 11th IC on DCS, (1991).
• 9: Kerry Raymond, A distributed algorithm for multiple entries to a critical section, Information Processing Letters, v.30 n.4, p.189-193, February 1989 [doi>10.1016/0020-0190(89)90211-1]
• 10: Michel Raynal, A simple taxonomy for distributed mutual exclusion algorithms, ACM SIGOPS Operating Systems Review, v.25 n.2, p.47-50, April 1991 [doi>10.1145/122120.122123]
• 11: Michel Raynal, A Distributed Solution to the k-out of-M Resources Allocation Problem, Proceedings of the International Conference on Computing and Information: Advances in Computing and Information, p.599-609, May 27-29, 1991
• 12: Glenn Ricart , Ashok K. Agrawala, An optimal algorithm for mutual exclusion in computer networks, Communications of the ACM, v.24 n.1, p.9-17, Jan. 1981 [doi>10.1145/358527.358537]
• 13: Pradip K. Srimani , R. L. N. Reddy, Another distributed algorithm for multiple entries to a critical section, Information Processing Letters, v.41 n.1, p.51-57, Jan. 21, 1992 [doi>10.1016/0020-0190(92)90079-B]
• 14: Ichiro Suzuki , Tadao Kasami, A distributed mutual exclusion algorithm, ACM Transactions on Computer Systems (TOCS), v.3 n.4, p.344-349, Nov. 1985 [doi>10.1145/6110.214406]
• 15: [15] M. Trehel and M. Naimi, "A Distributed Algorithm for Mutual Exclusion Based on Data Structures and Fault Tolerance," Proc. IEEE Phoenix Conf. on Communication, (1987), p. 256-276.
• 16: [16] M. Trehel and M. Naimi, "A Distributed Algorithm for Mutual Exclusion in Arbitrary Network Using the Lift Strategy," TENCOM 87, Seoul Korea (1987), pp. 1050-1055.
• 17: [17] J. L. Van de Snepscheut, "Fair Mutual Exclusion on a Graph of Processes," Distributed Computing Vol. 2 (1987), pp. 113-115.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Mutual exclusion
      D.4.7 Organization and Design
          Subjects: Distributed systems

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

General Terms:
Algorithms, Design, Performance

Keywords:
distributed algorithm, logical directed graph, mutual exclusion