首页    期刊浏览 2024年12月02日 星期一
登录注册

文章基本信息

  • 标题:Self-Stabilizing Local Mutual Exclusion and Definition Refinement
  • 本地全文:下载
  • 作者:Jeffrey Beauquier ; Ajoy K. Datta ; Maria Gradinariu
  • 期刊名称:Chicago Journal of Theoretical Computer Science
  • 印刷版ISSN:1073-0486
  • 出版年度:2002
  • 卷号:2002
  • 出版社:MIT Press ; University of Chicago, Department of Computer Science
  • 摘要:

    Refining self-stabilizing algorithms which use tighter scheduling constraints (weaker daemon) into corresponding algorithms for weaker or no scheduling constraints (stronger daemon), while preserving the stabilization property, is useful and challenging. Designing transformation techniques for these refinements has been the subject of serious investigations in recent years. This paper proposes a new transformation technique for daemon refinement. The core of the transformer is a self-stabilizing local mutual exclusion algorithm. The local mutual exclusion problem is to grant a process the privilege to enter critical section if and only if none of its neighbors has the privilege. The contribution of this paper is twofold. First, we present a bounded-memory self-stabilizing local mutual exclusion algorithm for arbitrary networks, assuming any arbitrary daemon. After stabilization, this algorithm maintains a bound on the service time (the delay between two successive executions of critical section by a particular process). This bound is 0.5n(n-1) where n is the network size. Another nice feature of our algorithm is that it satisfies the strong safety property --- in any configuration, there is at least one privileged processor. Second, we use the local mutual exclusion algorithm to design two transformers which convert the algorithms working under a weaker daemon to ones which work under the distributed, arbitrary (or unfair) daemon. Both transformers preserve the self-stabilizing property. The first transformer refines algorithms written under the central daemon, while the second transformer refines algorithms designed for the k-fair (k >= (n-1)) daemon.

国家哲学社会科学文献中心版权所有