Fundamental problems in distributed and parallel computation will be investigated from both a theoretical and practical standpoint. A focal point of the research will be the study of the sequence transmission problem. The sequence transmission problem is the problem of transmitting an arbitrarily long sequence of messages from one party to another over a channel which both reorder and lose packets. This problem is an abstraction of the classic problem of designing an end-to-end transport layer protocol in the OSI model of a computer network. There is a series of new theoretical results, both upper and lower bounds, which raise the possibility of a new class of efficient protocols for this problem. This project will investigate this new class of protocols by analytically and experimentally exploring which variations have the best chance of practical implementations. Those with the most promise will be implemented under Unix using IP in a controlled experimental environment. Experiments will be undertaken on the INTERNET, but only after the protocols have been thoroughly verified. In addition to the sequence transmission problem, several other distributed and parallel computing problems will be studied.
