Multi-party protocols

ABSTRACT

Many different types of inter-process communication have been examined from a complexity point of view [SP, Y]. We study a new model, in which a collection of processes P0, ..., Pk−1 that share information about a set of integers {a0, ...,ak−1}, communicate to determine a 0-1 predicate of the numbers. In this new model, tremendous sharing of information is allowed, while no single party is given enough information to determine the predicate on its own. Formally, each Pi has access to every aj except for ai. For simplicity, we only allow the parties to communicate as follows.

REFERENCES

• 1: A. Borodin, M. Fischer, D. Kirkpatrick, N. Lynch, M. Tompa, "A time-space tradeoff for sorting and related non-oblivious computations." Toronto, Dept. of Computer Science, Technical Report 79-01-01, 1979.
• 2: A. Borodin, D. Dolev, F. Fich, W. Paul, "Bounds for width-2 branching programs." These proceedings.
• 3: P. Erdös and R. Graham, Old and New Problems and Results in Combinatorial Number Theory. L'Enseignement Mathématique, Université de Genève, 1980.
• 4: M. Furst, J. Saxe, M. Sipser, "Parity, circuits and the polynomial-time hierarchy." 22ndSymposium on the Foundations of Computer Science, 1981, pp. 260-270; To appear in Mathematical Systems Theory.
• 5: R. Graham, Rudiments of Ramsey theory. Regional Conference Series in Mathematics, number 45, 1981.
• 6: R. Graham, B. Rothschild, J. Spencer, Ramsey Theory. Wiley-Interscience, 1980, p. 38.
• 7: Nicholas Pippenger, A Time-Space Trade-Off, Journal of the ACM (JACM), v.25 n.3, p.509-515, July 1978 [doi>10.1145/322077.322091]
• 8: K. Roth, "On certain sets of integers." J. London Math. Soc., 29, 1954, pp. 20-26.
• 9: Christos H. Papadimitriou , Michael Sipser, Communication complexity, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.196-200, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802192]
• 10: Martin Tompa, Time-space tradeoffs for computing functions, using connectivity properties of their circuits, Proceedings of the tenth annual ACM symposium on Theory of computing, p.196-204, May 01-03, 1978, San Diego, California, United States [doi>10.1145/800133.804348]
• 11: Andrew Chi-Chih Yao, Some complexity questions related to distributive computing(Preliminary Report), Proceedings of the eleventh annual ACM symposium on Theory of computing, p.209-213, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804414]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols

  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Model theory

General Terms:
Theory