Journal Articles

• H. Buhrman, A. Panconesi, R. Silvestri, and Paul Vitanyi On the importance of having an identity or, is consensus really Universal?, Distributed Computing, 18(2006), 167--176.
• S. Haldar and P. Vitanyi, Bounded concurrent timestamp systems using vector clocks, J. Assoc. Comp. Mach., 49:1(2002), 101-126.
• J. Tromp and P. Vitanyi, Randomized two-process wait-free test-and-set, Distributed Computing, 15(2002), 127--135. Construction validation with the PRISM checker at the University of Birmingham (UK)
• H. Buhrman, M. Franklin, J. Garay, J.H. Hoepman, J. Tromp, P. Vitanyi, Mutual Search, J. Assoc. Comp. Mach., 46:4(1999), 517--536.
• A. Panconesi, M. Papatriantafilou, P. Tsigas, P. Vitanyi, Randomized Naming Using Wait-Free Shared Variables, Distributed Computing, 11(1998), 113--124.
• H. Buhrman, J.H. Hoepman, and P.M.B. Vitanyi, Space-efficient routing tables for almost all networks and the incompressibility method, SIAM J. Comput., 28:4(1999), 1414--1432.
• M. Li, J. Tromp and P.M.B. Vitanyi, How to share concurrent wait-free variables, J. Assoc. Comp. Mach., 43 (1996), 723-746.
• M. Li and P.M.B. Vitanyi, Optimality of Wait-Free Atomic Multiwriter Variables, Information Processing Letters, 43(1992), 107-112.
• E. Kranakis and P.M.B. Vitanyi, A note on weighted distributed Match-Making, Mathematical Systems Theory, 25(1992), 123-140.
• P.M.B. Vitanyi, Locality, communication and interconnect length in multicomputers, SIAM J. on Computing, 17 (1988), 659-672.
• S.J. Mullender and P.M.B. Vitanyi, Distributed match-making, Algorithmica. 3 (1988), 367-391.

Conference Articles

• R. Cilibrasi, Z. Lotker, A. Navarra, S. Perennes, P. Vitanyi,` About the lifespan of peer to peer networks, Proc. 10th Int'nl Conf. Principles Of Distributed Systems (OPODIS), Lecture Notes in Computer Science, Vol. 4305, Springer Verlag, Berlin, 2006, 290--305.
• H. Buhrman, H. Klauck, N.K. Vereshchagin, P.M.B. Vitanyi, Individual communication complexity, Proc. 21st Symp. Theoretical Aspects of Computer Science (STACS), Lecture Notes in Computer Science, Vol. 2996, Springer-Verlag, Berlin, 2004, 19--30.
• P. Vitanyi, Simple wait-free multireader registers, Proc 16th Intn'l Symp. Distributed Computing (DISC'02), Lecture Notes in Computer Science, Vol. 2508, Springer-Verlag, Berlin, 2002, 118--132.
• H. Buhrman, A. Panconesi, R. Silvestri, and Paul Vitanyi On the importance of having an identity or, is consensus really Universal?, Distributed Computing Conference (DISC'00), Lecture Notes in Computer Science, Vol. 1914, Springer-Verlag, Berlin, 2000, 134--148. (Final version published in Distributed Computing.)
• H. Buhrman, M. Franklin, J. Garay, J.H. Hoepman, J. Tromp, P. Vitanyi, Mutual Search, Proc. 9th ACM-SIAM Symposium on Discrete Algorithms, 1998.
• H. Buhrman, J.H. Hoepman and P.M.B. Vitanyi, Optimal routing tables, Proc. 15th ACM Symp. on Principles of Distributed Computing, 1996, 134-142.
• P.M.B. Vitanyi, Multiprocessor architectures and physical law, Proc. 2nd IEEE Workshop on Physics and Computation, PhysComp'94, Dallas (Texas), November 17-20, 1994, pp. 24-29.
• A. Panconesi, M. Papatriantafilou, P. Tsigas, P. Vitanyi, Randomized Wait-Free Distributed Naming, Proc. Fifth Annual International Symposium on Algorithms and Computation, Beijing, Springer Lecture Notes in Computer Science, Volume 834, 1994, pp 83-91.
• Y. Afek, E. Gafni, J. Tromp, P.M.B. Vitanyi, Wait-free test-and-set, pp. 85-94 in: Proc. 6th Workshop on Distributed Algorithms (WDAG-6), Lecture Notes in Computer Science, vol. 647, Springer Verlag, Berlin, 1992.
• E. Kranakis and P.M.B. Vitanyi, Weighted distributed Match-Making, Proceedings AWOC '88, Lecture Notes in Computer Science, vol. 319, Springer Verlag, Berlin, 1988, pp. 361-368.
• B. Awerbuch, L. Kirousis, E. Kranakis and P.M.B. Vitanyi, A proof technique for register atomicity, In: Proc. 8th Conf. Found. Software Techn. and Theoret. Comp. Sci., Lecture Notes in Computer Science, vol. 338, Springer Verlag, Berlin, 1988, pp. 286-303.
• L. Kirousis, E. Kranakis and P.M.B. Vitanyi, Atomic multireader register, Proceedings 2nd International Workshop on Distributed Algorithms, Lecture Notes in Computer Science, Vol 312, Springer Verlag, Berlin, 1987, pp. 278-296.
• P.M.B. Vitanyi and B. Awerbuch, Atomic shared register access by asynchronous hardware, Proceedings 27th Annual IEEE Symposium on Foundations of Computer Science, 1986, 233-243. Errata, FOCS'87. The Peterson-Burns's fix in their paper in FOCS'87 is erroneous as pointed out by Haldar and Vidyasankar in a report, see history in the Haldar-Vitanyi paper below. The problem in the errata is resolved by M. Li, J. Tromp and P.M.B. Vitanyi, How to share concurrent wait-free variables, J. Assoc. Comp. Mach., 43 (1996), 723-746. giving an optimal wait-free atomic multiwriter multireader register from wait-free atomic 1-writer 1-reader registers using bounded timestamps (by projections of the method also wait-free atomic multiwriter multireader register from wait-free atomic 1-writer multireader register, and wait-free atomic 1-writer multireader register from wait-free atomic 1-writer 1-reader register). It turns out that the method in the Vitanyi-Awerbuch original bounded multiwriter system (made error-free) is strong enough to implement a concurren bounded timestamp system from wait-free atomic 1-writer multireader registers S. Haldar and P. Vitanyi, Bounded concurrent timestamp systems using vector clocks, J. Assoc. Comp. Mach., 49:1(2002), 101-126.
• P.M.B. Vitanyi, Non-sequential computation and Laws of Nature, In: VLSI Algorithms and Architectures (Proceedings Aegean Workshop on Computing, 2nd International Workshop on Parallel Processing and VLSI), Lecture Notes In Computer Science 227, Springer Verlag, 1986, 108-120. (Invited)
• P.M.B. Vitanyi, Area penalty for sublinear signal propagation delay on chip, Proceedings 26th Annual IEEE Symposium on Foundations of Computer Science , 1985, 197-207.
• S.J. Mullender and P.M.B. Vitanyi, Distributed match-making for processes in computer networks. In: Proceedings 4th ACM Symposium on Principles of Distributed Computing , 1985, 261-271. Reprinted in Operating Systems Review , 1986.
• P.M.B. Vitanyi, Distributed elections in an Archimedean ring of processors (preliminary draft). 16th ACM Symposium on Theory of Computing, Washington D.C., 1984, 542 - 547

Book Articles

• P.M.B. Vitanyi, Registers, Encyclopedia of Algorithms, Ming-Yang Kao, Ed., Springer, 2008, Part 17, 10.1007/978-0-387-30162-4_338.
• P.M.B. Vitanyi, ``A modest proposal for communication costs in multicomputers,'' pp. 203-216 in: Concurrent Computations, Algorithms, Architecture, and Technology, (S.K. Tewksbury, B.W. Dickinson and S.C. Schwartz, eds.), Plenum Press, New York, 1988.

Unpublished and Miscellaneous

• J. Tromp and P.M.B. Vitanyi, A randomized algorithm for two-process wait-free test-and-set,, under revision for a technical journal.
• A. Israeli, M. Li and P.M.B. Vitanyi, Simple multireader registers using timestamp systems, CWI Tech. Rept. CS-R8758
• M. Li and P.M.B. Vitanyi, A very simple construction for atomic multiwriter register, Tech. Rept. TR-8701, Aiken Computation Laboratory, Harvard University, November 1987.
• P.M.B. Vitanyi, Time-driven algorithms for distributed control, CWI Report CS-R8510

Edited Books

• G. Tel and P.M.B. Vitanyi, Eds., Distributed Algorithms, Proc. 8th International Workshop, WDAG'94, Lecture Notes in Computer Science, Volume 857, Springer-Verlag, Heidelberg, 1994.

[Back |Home]