Efficient transformation of distance-2 self-stabilizing algorithms |
| |
Authors: | Volker Turau |
| |
Affiliation: | Hamburg University of Technology, Institute of Telematics, Schwarzenbergstraße 95, 21073 Hamburg, Germany |
| |
Abstract: | Self-stabilizing algorithms for optimization problems can often be solved more easily using the distance-two model in which each vertex can instantly see the state information of all vertices up to distance two. This paper presents a new technique to emulate algorithms for the distance-two model on the distance-one model using the distributed scheduler with a slowdown factor of O(m) moves. Up until now the best transformer had a slowdown factor of O(n2m) moves. The technique is used to derive improved self-stabilizing algorithms for several graph domination problems. The paper also introduces a generalization of the distance-two model allowing a more space efficient transformer. |
| |
Keywords: | Self-stabilization Distributed algorithms Fault tolerant algorithms |
本文献已被 ScienceDirect 等数据库收录! |