This research presents a distributed algorithm for computing optimal coalition structure, an important area of research in multiagent systems. Since the number of coalition structures grows exponentially even for a small number of agents, a distributed algorithm can deal with the problem when the number of agents is larger. While most algorithms for the problem works lexicographically, our algorithm works based on the average contribution of the agents in coalitions. We split the task of computing optimal coalition structure into two parts: i) partitioning the search space for each agent, and ii) generating the optimal coalition structure by each agent. While traditional parallel algorithms assume reliable communication among nodes (allowing for constantly exchanging data), distributed environments cannot guarantee such environments because communication in real world is unpredictable. Therefore, the main purpose of our algorithm is to minimize communication between agents (in most cases the results will be realized by multiple agents about the same time) while maintain g the algorithm’s speed. In addition, we improve the performance of the value-oriented algorithm used for searching optimal coalition structure. While the existing algorithm follows the depth-first search strategy, we apply the breadth-first search to increase the performance. We also provide the empirical results of our algorithm which show that the communication among agents is minimal and the global result can be achieved relatively fast.