New models and algorithms for future networks

Abstract
In future networks transmission and switching capacity will dominate processing capacity. In this paper we investigate the way in which distributed algorithms should be changed in order to operate efficiently in this new environment. We introduce a class of new models for distributed algorithms which make explicit the difference between switching and processing. Based on these new models we define new message and time complexity measures which, we believe, capture the costs in many high speed networks more accurately than traditional measures. In order to explore the conse- quences of the new models, we examine three problems in distributed computation. For the problem of maintaining network topology we devise a broadcast algorithm which takes O(n) mes- sages and O( log n) time in the new measure. For the problem of leader election we present a simple algorithm that uses O(n) messages and O(n) time. The third problem, distributed compu- tation of a "globally sensitive" function, demonstrates some important features and trade-offs in the new models and emphasizes the differences with the traditional network model.