Cost distribution of the Chang-Roberts leader election algorithm

摘要

A detailed probabilistic analysis of the cost of the Chang-Roberts leader election algorithm is proposed. Meanwhile the constructive bijections among related measures are presented, repectively, included the total path length of random recursive trees and the cost of an in-situ permutation algorithm.