Treffer: Cost distribution of the Chang-Roberts leader election algorithm and related problems
Title:
Cost distribution of the Chang-Roberts leader election algorithm and related problems
Authors:
Source:
Theoretical computer science. 369(1-3):442-447
Publisher Information:
Amsterdam: Elsevier, 2006.
Publication Year:
2006
Physical Description:
print, 20 ref
Original Material:
INIST-CNRS
Subject Terms:
Computer science, Informatique, Sciences exactes et technologie, Exact sciences and technology, Sciences et techniques communes, Sciences and techniques of general use, Mathematiques, Mathematics, Combinatoire. Structures ordonnées, Combinatorics. Ordered structures, Combinatoire, Combinatorics, Théorie des graphes, Graph theory, Sciences appliquees, Applied sciences, Recherche operationnelle. Gestion, Operational research. Management science, Recherche opérationnelle et modèles formalisés de gestion, Operational research and scientific management, Optimisation. Problèmes de recherche, Optimization. Search problems, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Informatique théorique, Theoretical computing, Algorithmique. Calculabilité. Arithmétique ordinateur, Algorithmics. Computability. Computer arithmetics, Algorithme, Algorithm, Algoritmo, Arbre binaire, Binary tree, Arbol binario, Informatique théorique, Computer theory, Informática teórica, Méthode récursive, Recursive method, Método recursivo, Permutation, Permutación, Problème valeur extrême, Extreme-value problems, Algorithme élection, Arbre aléatoire, Chemin aléatoire, Longueur chemin, Extrema finding, In situ permutation, Increasing binary trees, Leader election, Left-to-right minima, Maxima finding, Recursive trees
Document Type:
Fachzeitschrift
Article
File Description:
text
Language:
English
Author Affiliations:
Department of Electronic Engineering, National Taiwan University of Science and Technology, Taipei 106, Tawain, Province of China
ISSN:
0304-3975
Rights:
Copyright 2007 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems
Mathematics
Operational research. Management
Mathematics
Operational research. Management
Accession Number:
edscal.18312644
Database:
PASCAL Archive
Weitere Informationen
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.