We are concerned with the problem of minimizing the complexity of communication in a distributed information gathering scenario, where a recipient gathers the information from a set of correlated informants, by interactively communicating with those. We assume that the joint distribution of the informants’ data is known only to the recipient. Realizing that there can be different objectives to achieve in such a communication scenario, our work provides the optimal communication protocols, which minimize the number of messages and bits exchanged to achieve these objectives. Both, worst-case and average-case scenarios are considered.