Self-stabilization is a versatile methodology for designing fault-tolerant distributed algorithms for transient faults. Many self-stabilizing distributed algorithms adopt the state-reading model (or locally shared memory model), in which each process can read the local variables of its direct neighbor processes, in addition to its own local variables. In this paper, we propose a new model, named the R( \(d_r\) )W( \(d_w\) ) model. In this model, each process can read the local variables of processes within a distance of \(d_r\) ( \(\ge 1\) ) and write the local variables of processes within a distance of \(d_w\) ( \(\ge 0\) ). We present several self-stabilizing distributed algorithms in the proposed model. Furthermore, we present a transformer that directly simulates the R(1)W(1) model in the synchronous message passing model.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Extending the Writing Distance: the R( \(d_r\) )W( \(d_w\) ) Communication Model for Self-stabilizing Distributed Algorithms

  • Hirotsugu Kakugawa,
  • Sayaka Kamei,
  • Masahiro Shibata,
  • Fukuhito Ooshita

摘要

Self-stabilization is a versatile methodology for designing fault-tolerant distributed algorithms for transient faults. Many self-stabilizing distributed algorithms adopt the state-reading model (or locally shared memory model), in which each process can read the local variables of its direct neighbor processes, in addition to its own local variables. In this paper, we propose a new model, named the R( \(d_r\) )W( \(d_w\) ) model. In this model, each process can read the local variables of processes within a distance of \(d_r\) ( \(\ge 1\) ) and write the local variables of processes within a distance of \(d_w\) ( \(\ge 0\) ). We present several self-stabilizing distributed algorithms in the proposed model. Furthermore, we present a transformer that directly simulates the R(1)W(1) model in the synchronous message passing model.