Abstract:
In this paper we deal with the efficiency of token-based strategies for the basic problem of controlling the allocation of a shared resource in a ring of n processing entities. We propose new protocols that allow a bounded number of exchanged messages per access request to the resource, while this amount is unbounded for classical solutions. We also guarantee all the requests to be served within a maximum delay. The new proposed protocols are request-message-based strategies, in that a process entity sends a message to "inform" the token of the access request. © 1998 Elsevier Science B.V. All rights reserved.
Registro:
Documento: |
Artículo
|
Título: | Efficient token-based control in rings |
Autor: | Feuerstein, E.; Leonardi, S.; Marchetti-Spaccamela, A.; Santoro, N. |
Filiación: | Departamento de Computación, FCEyN, Universidad de General Sarmiento, Buenos Aires, Argentina Dipto. di Informatica e Sistemistica, Univ. di Roma La Sapienza, Roma, Italy School of Computer Science, Carleton University, Ottawa, Ont. K1S 5B6, Canada
|
Palabras clave: | Amortized analysis; Distributed computing |
Año: | 1998
|
Volumen: | 66
|
Número: | 4
|
Página de inicio: | 175
|
Página de fin: | 180
|
Título revista: | Information Processing Letters
|
Título revista abreviado: | Inf. Process. Lett.
|
ISSN: | 00200190
|
CODEN: | IFPLA
|
Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00200190_v66_n4_p175_Feuerstein |
Referencias:
- Andrews, D., Schulz, G., A token-ring architecture for local area networks: An update (1982) Proc. IEEE COMPCON, , Fall
- ANSI/IEEE Standards 802.2-1985, , 802.3-1985, 802.4-1985, 802.5-1985
- Bertsekas, D., Gallager, R., (1992) Data Networks, 2nd Ed., , Prentice-Hall
- Burns, J.E., Pachl, J., Uniform self-stabilizing rings (1989) ACM Trans. Programming Languages and Systems, 11 (2), pp. 330-344
- Bux, W., Performance issues in local area networks (1984) IBM J., 23 (4)
- Dijkstra, E.W., Self-stabilizing systems in spite of distributed control (1974) Comm. ACM, 17 (11), pp. 643-644
- Halsall, F., Data communications (1992) Computer Networks and Open Systems, 3rd Ed., , Addison-Wesley
- Israeli, A., Jalfon, M., Token management schemes and random walks yield self-stabilizing mutual exclusion (1990) Proc. 9th ACM Symposium on Principles of Distributed Computing, pp. 119-129
- Kakugawa, H., Yamashita, M., Uniform randomized self-stabilizing mutual exclusion on unidirectional ring under unfair c-deamon (1995) Proc. 2nd Workshop on Self-Stabilizing Systems, pp. 141-1413
- Lann, G.L., Distributed systems - Towards a formal approach (1977) Inform. Processing, 77, pp. 155-160. , B. Gilchrist (ed.), North-Holland
- Misra, J., Detecting termination of distributed computations using markers (1983) Proc. 2nd ACM Symposium on Principles of Distributed Computing, pp. 290-294
- Rego, V., Ni, L.M., Analytic models of cyclic service systems and their application to token-passing local networks (1988) IEEE Trans. Computers, C-37 (10), pp. 1224-1234
- Raynal, M., (1988) Distributed Algorithms and Protocols, , John Wiley & Sons
- Ross, F.E., FDDI - A tutorial (1986) IEEE Commun. Mag., 24, pp. 10-17
- Singhal, M., A taxonomy of distributed mutual exclusion (1993) J. Parallel Distrib. Comput., 18, pp. 94-101
- Suzuki, I., Kasami, T., A distributed mutual exclusion algorithm (1985) ACM Trans. Comput. Syst., 3-4, pp. 344-349
- Tarjan, R.E., Amortized computational complexity (1985) SIAM J. Alg. Discrete Meth., 6 (2), pp. 306-318
Citas:
---------- APA ----------
Feuerstein, E., Leonardi, S., Marchetti-Spaccamela, A. & Santoro, N.
(1998)
. Efficient token-based control in rings. Information Processing Letters, 66(4), 175-180.
Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00200190_v66_n4_p175_Feuerstein [ ]
---------- CHICAGO ----------
Feuerstein, E., Leonardi, S., Marchetti-Spaccamela, A., Santoro, N.
"Efficient token-based control in rings"
. Information Processing Letters 66, no. 4
(1998) : 175-180.
Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00200190_v66_n4_p175_Feuerstein [ ]
---------- MLA ----------
Feuerstein, E., Leonardi, S., Marchetti-Spaccamela, A., Santoro, N.
"Efficient token-based control in rings"
. Information Processing Letters, vol. 66, no. 4, 1998, pp. 175-180.
Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00200190_v66_n4_p175_Feuerstein [ ]
---------- VANCOUVER ----------
Feuerstein, E., Leonardi, S., Marchetti-Spaccamela, A., Santoro, N. Efficient token-based control in rings. Inf. Process. Lett. 1998;66(4):175-180.
Available from: https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00200190_v66_n4_p175_Feuerstein [ ]