Networks such as Peer-to-Peer (P2P), ad hoc, wireless sensor, and other complex networks do not support optimal communication between different devices across their configurations. They require appropriate algorithms to distribute data because they may have unspecific structures with a large amount of nodes, energy constraints, channel restrictions, and delays. The desired communication algorithms for these networks are simple and robust in order to handle these unpredictable characteristics. For example, gossip algorithms are used as core messaging algorithms for many distributed applications in wireless ad-hoc networks, sensor networks, and peer-to-peer networks because the underlying networks have complex unstructured topologies. This thesis provides a theoretical analysis of the base-line gossip algorithm where the goal is to maximize the aggregate message throughput in all to-all communication nodes. For allto- all communication, every node attempts to broadcast its messages to all other nodes. By establishing a connection between the gossip algorithm and percolation theory in random graphs, we are able to analytically derive the aggregate throughput as a function of the basic parameters of the gossip algorithm. We use this formulation to find the optimal points in the algorithm parameters to obtain the resulting maximum aggregate throughput. The results are derived for a simplified model of the gossip algorithm and for specific classes of random networks. These results shed light on the fundamental tradeoffs involved in the gossip protocol. These tradeoffs can be used as a guideline for optimizing the performance of these algorithms.