No label defined (Q3787481)

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 4050992
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 4050992

      Statements

      0 references
      0 references
      1988
      0 references
      Archimedean networks
      0 references
      synchronous networks
      0 references
      limited asynchrony
      0 references
      distributed computation
      0 references
      logical ring
      0 references
      mutual exclusion
      0 references
      readers and writers
      0 references
      symmetry breaking problem
      0 references
      [For the entire collection see Zbl 0635.00015.] This work examines the effect of limited asynchrony on three fundamental problems of distributed computation: The problem of symmetry breaking in a logical ring, that of mutual exclusion, and the problem of readers and writers. We assume our distributed system to be Archimedean in the sense that processors know upper and lower bounds on the message delays and processor speeds. We use the knowledge of these bounds to get algorithms for the above mentioned problems which well improve the efficiency of algorithms presented by previous research. For the symmetry breaking problem we get a protocol which admits arbitrary initiation, and uses only linear number of message bits and linear time on the average. For the mutual exclusion problem we break the lower bound on the number of messages which holds in case of unrestricted asynchrony. We also find an important difference between Archimedean and synchronous networks. Our algorithms are practical in the sense that any existing distributed system up to now follows the Archimedean time assumption.
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references