Concurrency in heavily loaded neighborhood-constrained systems

ABSTRACT

Let G be a connected undirected graph in which each node corresponds to a process and two nodes are connected by an edge if the corresponding processes share a resource. We consider distributed computations in which processes are constantly demanding all of their resources in order to operate, and in which neighboring processes may not operate concurrently. We advocate that such a system is general enough for representing a large class of resource-sharing systems under heavy load. We employ a distributed scheduling mechanism based on acyclic orientations of G and investigate the amount of concurrency that it provides. We show that this concurrency is given by a number akin to G's chromatic and multichromatic numbers, and that, among scheduling schemes which require neighbors in G to alternate in their turns to operate, ours is the one that potentially provides the greatest concurrency. However, we also show that the decision problem corresponding to optimizing concurrency is NP-complete.

REFERENCES

• 1: Baruch Awerbuch, Complexity of network synchronization, Journal of the ACM (JACM), v.32 n.4, p.804-823, Oct. 1985 [doi>10.1145/4221.4227]
• 2: Valmir Carneiro Barbosa, Concurrency in systems with neighborhood constraints (distributed systems, parallel processing, dining philosophers, simulated annealing), 1986
• 3: C. Berge, Graphs and Hypergraphs, Elsevier Science Ltd, 1985
• 4: 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]
• 5: DIJKSTRA, E.W. Cooperating sequential processes. In t~rogramming Languages, F. Genuys, Ed. Academic Press, New York, 1968, pp. 43-112.
• 6: GArNI, r. M., AND BERTSEKAS, D.P. Distributed algorithms for generating loop-free routes in networks with frequently changing topology. IEEE Trc:ns. Commun. COM-29, i (Jan. 1981), 11-18.
• 7: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 8: GROTSCHEL, M., LOV.~SZ, r., AND SCHRIJVER, A. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1, 2 (1981), 169-197.
• 9: KARP, R.M. Reducibility among combinatorial probleias. In Complexity of Computer Computations, R. E. Miller and J. W. Thatcher, Eds. Plenum P~ess, New York, 1972, pp. 85-103.
• 10: KIRKPATRICK, S., GELATT, C. D., AND VECCHI, M.P. Optimization by simulated annealing. Science 220, 4598 (May 13, 1983), 671-680.
• 11: 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]
• 12: STAHL, S. n-tuple colorings and associated graphs. J. Ccmbinatorial Theory, Ser. B 20, 2 (April 1976), 185-203.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.3 Formal Languages
          Subjects: Decision problems

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

General Terms:
Algorithms, Performance, Theory