Analyzing the performance of randomized information sharing

Abstract

In large, collaborative, heterogeneous teams, team members often collect information that is useful to other members of the team. Recognizing the utility of such information and delivering it efficiently across a team has been the focus of much research, with proposed approaches ranging from flooding to complex filters and matchmakers. Interestingly, random forwarding of information has been found to be a surprisingly effective information sharing approach in some domains. In this paper, we investigate this phenomenon in detail and show that in certain systems, random forwarding of information performs almost half as well as a globally optimal approach. We present analytic and empirical results comparing random methods with theoretically optimal sharing in small-worlds, scale-free, and random networks. In addition, we demonstrate a method for modeling real domains that allows our results to be applied toward estimating information sharing performance.