Computing the maximum salary

These questions (and many others) are studied in the literature under the heading of secret-sharing or common-knowledge protocols. A nice but short review appears in chapter 4 of David Gale's "Tracking the Automatic Ant".

The "sum protocol" you presented can be modified to determine how many people have salary x (without revealing their identity). Just have each participant communicate 0 or 1 according to whether or not she has salary x, and by scanning all x's in the (presumably known) range of salaries you can learn the distribution, as well as the maximum (by scanning down from some upper bound). However, this protocol reveals not only the max salary, but also how many people earn that max.

Such protocols are called $t$-private if they do not reveal any additional information unless $t$ people 'collude' and discuss their knowledge with each other. The protocol you mentioned is, in fact, $n$-private - unless everyone cooperates, they are all in the dark (EDIT: this is false, of course, as pointed out in the comments. The correct $n$-private protocol is described below). The sum is, essentially, the only function that can be computed $n$-privately. The maximum (without the extra knowledge of how many people earn it), the product etc. can all be computed $t$-privately for $t < n/2$, but not for $t \geq n/2$. The existence is proved by Ben-Or, Goldwasser and Wigderson in STOC 1988; the non-existence by Chor and Kushilevitz (STOC 1989) for Boolean functions and by Beaver for general integer-valued functions. This is all extracted from Gale's book.

How to compute the sum $n$-privately: Each person breaks up their salary into a sum of $n$ numbers, chosen at random except for the constraint that their sum is $n$. Each person now communicates the $j$th part to the $j$ person (including "communicating" one of the parts to herself). They then all announce the sums of all the pieces that were communicated to them. It's a fun exercise to show that no $k$ people can figure anything out other than whatever can be derived from their own salaries, for any $k < n$.