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.