Multi-party Protocols
Chandra, Furst and Lipton generalized the notion of two-party communication protocols to multi-party communication protocols. They proposed a model in which a collection of processes (, ) have access to a set of integers (, ,… ) except one of them, so that is denied access to . These processes are allowed to communicate in order to arrive at a consensus on a predicate. They studied this model’s communication complexity, defined as the number of bits broadcast among all the processes. As an example, they studied the complexity of a k-party protocol for Exactly-N (do all ’s sum up to N?), and obtained a lower bound using the tiling method. They further applied this model to study general branching programs and obtained a time lower bound for constant-space branching programs that compute Exactly-N.
Read more about this topic: Richard J. Lipton