We study the memory requirements of self-stabilizing leader election (SSLE) protocols. We are mainly interested in two types of systems: anonymous systems and id-based systems. We consider two classes of protocols: de...
详细信息
We study the memory requirements of self-stabilizing leader election (SSLE) protocols. We are mainly interested in two types of systems: anonymous systems and id-based systems. We consider two classes of protocols: deterministic ones and randomized ones. We prove that a non-constant lower bound on the memory space is required by a SSLE protocol on unidirectional, anonymous rings (even if the protocol is randomized). We show that, if there is a deterministic protocol solving a problem on id-based systems where the processor memory space is constant and the id-values are not bounded then there is a deterministic protocol on anonymous systems using constant memory space that solves the same problem. Thus impossibility results on anonymous rings (i.e. one may design a deterministic SSLE protocol, only on prime size rings, under a centralized daemon) can be extended to those kinds of id-based rings. Nevertheless, it is possible to design a silent and deterministic SSLE protocol requiring constant memory space on unidirectional, id-based rings where the id-values are bounded. We present such a protocol. We also present a randomized SSLE protocol and a token circulation protocol under an unfair, distributed daemon on anonymous and unidirectional rings of any size. We give a lower bound on memory space requirement proving that these protocols are space optimal. The memory space required is constant on average.
When we consider an asynchronous distributed computation on which local checkpoints have been defined (namely, a communication and checkpoint pattern - in brief, CCP), two types of dependencies between its local check...
详细信息
When we consider an asynchronous distributed computation on which local checkpoints have been defined (namely, a communication and checkpoint pattern - in brief, CCP), two types of dependencies between its local checkpoints can be observed. The first type is due to causal sequences of messages that establish on-line trackable dependencies. The second type is due to non-causal sequences of messages (called Z-paths) that establish `hidden' dependencies between local checkpoints (a dependency is `hidden' if it can not be tracked online). The Rollback Dependency Trackability (RDT) property, defined by Y.-M. Wang, has been introduced to study CCPs. A CCP satisfies the RDT property if every pair of local checkpoints that are connected by a `hidden' dependency are also connected by a causal sequence of messages. The RDT property has a great interest: CCPs that satisfy this property allow relatively simple solutions to a lot of practical problems. This paper first introduces the notion of RDT-compliant property. In a given CCP, an X-path is a Z-path that satisfies a property X. The property X is RDT-compliant if every CCP without X-paths satisfies the RDT property. Then, the paper presents a particular RDT-compliant property. This property enjoys several very interesting features. (1) It is `visible' (i.e., it can be tested on-line). (2) It is stronger than previously known RDT-compliant properties. Consequently, this property provides a characterization of RDT better than the previous ones. The question of the minimal characterization of the RDT property is finally investigated.
暂无评论