Cost distribution of the Chang–Roberts leader election algorithm and related problems

A detailed probabilistic analysis is proposed of the total number of messages of the Chang–Roberts leader election algorithm. The cost is shown to be closely related to the total path length in random recursive trees, the total left-path length in increasing binary trees and the major cost of an in situ permutation algorithm.