On the power of synchronization between two adjacent processes |
| |
Authors: | Jérémie Chalopin Yves Métivier |
| |
Affiliation: | 1. LIF, CNRS & Aix Marseille Université, 39 rue Joliot-Curie, 13453, Marseille, France 2. Université de Bordeaux, LaBRI UMR CNRS 5800, 351 cours de la Libération, 33405, Talence, France
|
| |
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). |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|