The uniform self-stabilizing orientation of unicyclic networks

• Author(s) / Creator(s)

  • Rudnicki, Piotr
  • Hoover, James

• Technical report TR91-02. We present a very simple protocol for the self-stabilizing orientation of a unicyclic network of uniform processors. It has the same O(n2) performance as the Israeli and Jalfon protocol for rings but is much simpler to state and furthermore operates under the weaker model of read/write demon asynchronicity. We also elucidate some of the techniques used in the design of such protocols, but not often stated in the literature. In addition, we propose a cleaner characterization of the various models used for such protocols by separating the issues of operation atomicity from the behaviour of the scheduling adversary. This eliminates the need to assume either a fair or proper scheduler when reasoning about the protocol | TRID-ID TR91-02

• Date created

  1991

• Subjects / Keywords

  • Scheduling adversary
  • Operation atomicity
  • Unicyclic network
  • Uniform processors

• Type of Item

  Report

• DOI

  https://doi.org/10.7939/R3639K80S

• License

  Attribution 3.0 International