Investigating the Fundamental Network Burden of Distributed Cooperation
0Technology continues to move in the direction of parallel computation, whether it be in a computer or across the internet. Second order effects such as the communication needed to carry out a distributed algorithm have become a concern. In this light, we take an information theoretic look at the fundamental communication requirements in networks for distributing tasks. The model is simple: tasks are numbered; some nodes in the network are assigned tasks; others have to choose from the remaining unassigned tasks. However, finding the fundamental communication requirements, even in simple networks, proves to be challenging. In the same vein as distributed algorithms, we look at the communication and secrecy needed to carry out cooperative behavior in a game theoretic setting. Claude Shannon identified the secret key requirements for secret communication without assuming any complexity restrictions. With game theory in mind, we find new objectives, other than sending secret information. These modified objectives can relax the secret key requirement without compromising perfect secrecy. This result is demonstrated with a few examples.