CHALOPIN_2007_HAL-00308126_1
Jérémie Chalopin, Emmanuel Godard, Yves Métivier, Gerard Tel. About the termination detection in the asynchronous message passing model. In Theory and Practice of Computer Science 33rd International conference on Current trends in theory and practice of computer science (SOFSEM 2007), Lecture notes in computer science, Volume 4362, Pages 200-211, Tchèque, République, 2007.
Download
Download paper:
Follow the link
Copyright notice:This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.
Abstract
{T}his paper presents a complete characterisation of the families of networks in which distributed computations can be performed in a process terminating manner, that is with explicit termination (at least one node of the network knows that every node has obtained its final state) in the asynchronous message passing model. {T}he characterisation encompasses all criteria that have been formulated in the past that were known to influence explicit termination: topological restriction (tree), topological knowledge (size or diameter), and local knowledge to distinguish nodes (identities or a leader). {T}hese results are now presented as corollaries of a single generalising theorem. {I}n addition our characterisation covers combinations of these, as well as new criteria, notably, link labelings.
Contact
Jérémie Chalopin
Emmanuel Godard
Yves Métivier
Gerard Tel
BibTex Reference
@InProceedings{CHALOPIN_2007_HAL-00308126_1,
Author = {Chalopin, Jérémie and Godard, Emmanuel and Métivier, Yves and Tel, Gerard},
Title = {{A}bout the termination detection in the asynchronous message passing model},
BookTitle = {{T}heory and {P}ractice of {C}omputer {S}cience 33rd {I}nternational conference on {C}urrent trends in theory and practice of computer science ({SOFSEM} 2007)},
Volume = {4362},
Pages = {200--211},
Series = {{L}ecture notes in computer science},
Publisher = {springer},
Address = {{T}ch{è}que, {R}{é}publique},
Year = {2007}
}
EndNote Reference [help]
Get EndNote Reference (.ref)