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
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
0.7831510305404663
0 references
0.741426408290863
0 references
0.7355150580406189
0 references
0.7334282994270325
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