We consider a network of processors that cooperate to solve a problem by
exchanging messages across communication channels in a non-synchronized
manner. Such a network is naturally modelled as a connected,
undirected graph with processors represented as vertices
and communication channels represented as edges.
The measure of the communication cost of an asynchronous distributed algorithm
for such a network typically is the total number of messages sent.
This measure assumes that the cost of sending a message along any
link is equal to one. In a network of asynchronous processors,
the cost to send a message can differ significantly from one
communication link to another.
In this presentation, we assume that associated with each link
is a positive {\em weight\/} representing the cost of sending one message
along the link and the cost of an algorithm executed on a {\em weighted\/}
network
is the sum of the costs of all messages sent during its execution.
This, so called ``cost-sensitive" analysis,
has been introduced by Awerbuch, Baratz and Peleg in 1990.
We present optimal distributed algorithms for Leader Election
on a ring topology and Minimum Cost Spanning tree.
As we show, both algorithms are optimal with respect to this cost measure.
This is joint work with Lisa Higham, University of Calgary.