"We study the complexity of some fundamental problems in two models of computation, namely, communication complexity and distributed computing. In communication complexity, we have two (or more) parties who want to compute a function on an input split between them. In distributed computing, we have some asynchronous processes which have a common goal such as electing a leader. Both models of computation have one thing in common: communication, in different forms, is a critical resource. We prove lower bounds on communication for some problems in each model. In communication complexity, we first study the AUGMENTED-INDEX problem, a variant of the well studied INDEX problem motivated by applications in data streams and data structures. Here, the two parties need to compute the value of a bit string (Alice's input) at a given location (Bob's input). In addition to the location, Bob is given a prefix of the bit string of Alice. This input sharing between the parties is notorious for making lower bounds harder to prove. We describe the complete tradeoff curve between Alice's information cost and Bob;s information cost that is tight everywhere. The tradeoffs hold under an "easy" distribution where the output is promised to be some fixed value always. We prove passes-space tradeoff for streaming verification of data structures such as priority queues, stacks, and double-ended queues, using the information cost tradeoffs. Second, we investigate the direct sum question, which is a deep and important question for any model of computation. Here, we want to know whether computing a function on k independent input instances requires k times the resources required to compute the function on a single input instance. We prove a direct sum theorem for the communication complexity of functions whose hardness is captured by smooth corruption bound (which subsumes corruption bound, smooth discrepancy, and discrepancy) under a product distribution. In fact, we show that smooth corruption bound lower bounds information cost, and information-theoretic measure of communication which naturally has a direct sum property, under product distibutions. Finally, we prove a time-space tradeoff of mutual exclusion, a fundamental problem in distributed computing, in the cache-coherent model. Two important implications of our bounds are that polynomial space is necessary to achieve constant remote memory references, and polynomial remote memory references will be incurred with constant space. Our bonds are optimal except when the space usage is small. The most interesting aspect of our bounds is that we prove that solving mutual exclusion--which involves "messy" systems details such as asynchrony and cache coherence--is equivalent to solving a simple and a purely combinatorial bin-pebble game that we design."