The Entropy of Traces in Parallel ComputationRajit ManoharThe following problem arises in the context of parallel computation: how many bits of information are required to specify any element from an arbitrary (non-empty) subset of a finite set? In this note, we calculate the amount of information necessary as well as the asymptotic behavior of the average information necessary. We characterize algorithms that specify the element from the subset in an optimal fashion. |
|
|
|