Multi-Party Protocols

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 P 0 , ..., P k−1 that share information about a set of integers {a 0 , ...,a k−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 P i has access to every a j except for a i . For simplicity, we only allow the parties to communicate as follows.

Authors

• Ashok K. Chandra
• Merrick L. Furst
• Richard J. Lipton

Keywords

No keywords are indexed for this paper.