| A common task in parallel processing is the distributed computation of a function by a number of processors each of which possesses partial information relevant to the value of that function. In this thesis we develop protocols which allow for such computation to take place while maintaining the value of the function secret to an eavesdropper. Of interest is the communication complexity of such protocols. We begin by considering two processors and two channels, one secret and one public, and present a protocol which minimizes the number of bits exchanged over the secret channel, while maintaining {dollar}epsilon{dollar}-uncertainty about the value of the function for the eavesdropper. We show that all binary functions can be kept {dollar}epsilon{dollar}-secret using a constant number of bits independent of the size of their domain. We then generalize our results to N processors communicating over a network of arbitrary topology.; In a related problem, also of interest in parallel processing, we consider processors communicating over a mesh network with the objective of broadcasting information amongst each other. One instance of the problem involves a number of nodes all with the same message to be broadcasted. For that problem a lower-bound on the time to complete the broadcast, and an algorithm which achieves this bound are presented. In another instance, every node in the mesh has packets to be broadcast arriving independently, according to a Poisson random process. The stability region for performing such broadcasts is characterized, and broadcast algorithms which operate efficiently within that region are presented. These algorithms involve interacting queues whose analysis is known to be very difficult. Toward that end we develop an approximate model for analyzing interacting queues. This new approximation models an N-dimensional infinite Markov chain by means of two Markov chains, one being one-dimensional and infinite and the other being N-dimensional and finite. The transition probabilities of each chain are expressed in terms of statistics of the other chain. The two chains can be solved together using standard iterative methods to yield an approximation to the original N-dimensional infinite chain. The results of the approximation compare very well with simulation, especially when arrival rates are low. We show how this model can also be used to analyze the ALOHA multiple access protocol. |
