We will now introduce a new part of the course: the study of locality in distributed systems. Broadly speaking, the problem of locality is as follows. In a distributed network without shared memory, processes cooperate by exchanging messages. Since sending messages to far away nodes is expensive, computation should be based on local information as much as possible. For what functions can this be achieved?
Note that in a distributed system a trivial strategy is always possible, provided the processors have distinct ID's: the network elects a leader (according to, say, the highest ID value) who then collects all the information, it computes the answers and sends them to everybody else. This is of course very expensive in terms of messages and we would like to avoid it. It is easy to come up with examples of trivial functions for which this is necessary however; for instance, summing n input values distributed across the network. What we would like to know is whether there are non trivial functions that can be computed under the locality constraint.
We shall see that this question leads to many very beautiful algorithmic results and to some challenging problems.