Cost-sensitive analysis of communication protocols
Baruch Awerbuch, Alan E. Baratz, David Peleg · 1990
This paper introduces the notion of cost-sensitive communication complexity and exemplifies it on the following basic communication problems: computing a global function, network synchronization, clock synchronization, controlling protocols' worst-case execution, connected components, spanning tree, etc., constructing a minimum spanning tree, constructing a shortest path tree. IntroductionTraEic load is one of the major factors affecting the behavior of a communication network.This fact is well recognized, and is the reason why most