No label defined (Q3832036)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 4108139
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 4108139

      Statements

      0 references
      1989
      0 references
      selective extinction of messages
      0 references
      election on a ring
      0 references
      paths of recognition
      0 references
      The author introduces a very interesting temporal consideration in solving the problem of recognizing a leader in circular configurations of processors. This problem was formulated by \textit{G. Lelann} [Distributed systems. Towards a formal approach (IFIP Congress 1977, North Holland, 155-160 (1977)]. Its classical solution uses the method of selective extinction of messages [\textit{E. J. Chang} and \textit{R. Roberts}, Commun. ACM 22, No.5, 281-283 (1979; Zbl 0394.68023)], which essentially consists in the rapid elimination of the initiators with small numbers. The recognition message sent by the initiator processor i will be stopped when arriving to another initiator j if \(j>i\). The election ends when an initiator i receives the message sent by itself. The time passed between the first recognition message and the end of election is called response time. The author considers the problem of reducing the response time. He modifies the selective extinction method as following. Let the message sent by the initiator i contain a variable denoting the maximum number of the initiator processors encountered. The initiator j, \(j>i\), will no longer stop the message that comes from i, but it will retransmit the message after updating this variable. The traffic will increase: corresponding with each initiator, there will be a message that circulates in the ring, creating a so called path of recognition. The election ends when a path of recognition is closed. The corresponding initiator will be the first to know the leader. The author develops an algorithm for unidirectional rings and one for bidirectional rings. He presents the algorithms in ADA. With the intention to estimate the performances (time and traffic) of the algorithms, the author considers the framework of ``the centaurs race'' introduced by \textit{A. Jean-Marie} and \textit{F. Baccelli} [The Centaurs Race. Performance Evaluation of an Election Algorithm on a ring (Rapport INRIA no. 926) (1988)], to give a model of time in a distributed asynchronous context.
      0 references

      Identifiers