Bounded time-stamps. (English) Zbl 0776.68018
We develop a theory of bounded time-stamps. Time-stamp schemes are defined and the complexity of their implementation is analyzed. This indicates a direction for developing a general tool for converting time- stamp based protocols to bounded protocols.
MSC:
| 68M10 | Network design and communication in computer systems |
References:
| [1] | Afek Y, Gafni E, Tromp J, Vitányi P: Wait-free test-and-set. In: Segall A, Zaks S (eds) Distributed algorithms (Proc 5th Int Workshop on Distributed Algorithms, Haifa, Israel, November 1992). Lecture Notes Comput Sci, Vol. 649. Springer, Berlin Heidelberg New York 1992, pp 95–109 |
| [2] | Awerbuch B, Mansour Y, Shavit N: Polynomial end-to-end communication. Proc 30th Annual Symposium on Foundations of Computer Science, 1989, pp 358–363 |
| [3] | Chor B, Israeli A, Li M: On processor coordination using asynchronous hardware. Proc 6th Annual ACM Symposium on Principles of Distributed Computing, 1987, pp 86–97 |
| [4] | Dolev D., Shavit N: Bounded concurrent time-stamp systems are constructible. Proc 21st Annual ACM Symposium on Theory of Computing, 1989, pp 454–466 |
| [5] | Dwork C, Herlihy M, Plotkin SA, Waarts O: Time-lapse snapshots. Proc Israeli Symposium on the Theory of Computing and Systems, 1992, pp 154–170 · Zbl 0928.68135 |
| [6] | Dwork C, Waarts O: Simple efficient bounded concurrent timestamping or bounded concurrent timestamp systems are comprehensible! Proc 24th Annual ACM Symposium on Theory of Computing, 1992, pp 655–666 · Zbl 1065.68501 |
| [7] | Erdös P: On a problem of graph theory. Math Gazette 47:220–223 (1963) · Zbl 0117.17402 · doi:10.2307/3613396 |
| [8] | Finn SG: Resynch procedures and a failsafe newtwork protocol. IEEE Trans Commun COM-27 (6):840–846 (1979) |
| [9] | Gawlick R, Lynch N, Shavit N: Concurrent timestamping made simple. Proc Israeli Symposium on the Theory of Computing and Systems, 1992, pp 171–183 |
| [10] | Graham RL, Spencer JH: A construction to a tournament problem. Can Math Bull 14(1):45–48 (1971) · Zbl 0209.55804 · doi:10.4153/CMB-1971-007-1 |
| [11] | Israeli A, Li M: Bounded time-stamps. 28th Annual EEE Symposium on Foundations of Computer Science, 1987, pp 371–382 |
| [12] | Israeli A, Pinhasov M: A concurrent time-stamp scheme which is linear in time and space. In: Segall A, Zaks S (eds) Distributed Algorithms (Proc 5th Int Workshop on Distributed Algorithms, Haifa, Israel, November 1992). Lect Notes Comput Sci, Vol. 649. Springer, Berlin Heidelberg New York 1992, pp 95–109 |
| [13] | Katseff HP: A new solution to the critical section problem. Conference Record of the 10th Annual ACM Symposium on the Theory of Computing, Dan Diego May 1978, pp 86–88 · Zbl 1282.68173 |
| [14] | Katz S, Shmueli O: Cooperative distributed algorithms for dynamic cycle prevention. IEEE Trans Software Eng SE 13(5):540–552 (1987) · Zbl 0615.68021 · doi:10.1109/TSE.1987.233199 |
| [15] | Lamport L: A new solution of Dijkstra’s concurrent programming problem. Commun ACM 17(8):453–455 (1974) · Zbl 0281.68004 · doi:10.1145/361082.361093 |
| [16] | Lamport L: The mutual exclusion problem. Part I: a theory of interprocess communication. J ACM 33(2):313–326 (1986) · Zbl 0627.68017 · doi:10.1145/5383.5384 |
| [17] | Lamport L: The mutual exclusion problem. Part II: statement and solutions. J ACM 33(2):327–348 (1986) · Zbl 0627.68018 · doi:10.1145/5383.5385 |
| [18] | Segall A: Distributed network protocols. IEEE Trans Inf Theory IT-29(1):23–35 (1983) · Zbl 0531.94026 · doi:10.1109/TIT.1983.1056620 |
| [19] | Soloway SR, Humblet PA: On distributed network protocols for changing topologies. (preprint) |
| [20] | Szekeres E, Szekeres G: On a problem of schutte and by Erdös. Math Gazette 49:290–293 (1965) · Zbl 0134.43502 · doi:10.2307/3612854 |
| [21] | Vitányi PMB, Awerbuch B: Atomic shared register access by asynchronous hardware. 27th Annual IEEE Symposium on Foundations of Computer Science, 1986, pp 233–243 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
