METIVIER-2010-527102
Yves Métivier, Jérémie Chalopin. On the power of synchronization between two adjacent processes. Distributed Computing, 23(3):177-196, November 2010.
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
We study the power of local computations on labelled edges (which allow two adjacent vertices to synchronize and to modify their states simultaneaously in function of their previous states) through the classical election problem. We characterize the graphs for which this problem has a solution. As corollaries we characterize graphs which admit an election algorithm for two seminal models : Angluin's model and asynchronous systems where processes communicate with synchronous message passing (i.e., there is a synchronization between the process sending the message and the one receiving it)
Contact
Yves Métivier
Jérémie Chalopin
BibTex Reference
@article{METIVIER-2010-527102,
Author = {Métivier, Yves and Chalopin, Jérémie},
Title = {On the power of synchronization between two adjacent processes},
Journal = {Distributed Computing},
Volume = {23},
Number = {3},
Pages = {177--196},
Month = {November},
Year = {2010}
}
EndNote Reference [help]
Get EndNote Reference (.ref)