62 citations · 63 across the 4 of their papers we have counts for
5 papers · 1 filter
On the Importance of Having an Identity or, is Consensus really Universal?
Harry Buhrman, Alessandro Panconesi, Riccardo Silvestri +1
We show that Naming-- the existence of distinct IDs known to all-- is a hidden but necessary assumption of Herlihy's universality result for Consensus. We then show in a very preci…
Simple Optimal Wait-free Multireader Registers
Paul Vitanyi
Multireader shared registers are basic objects used as communication medium in asynchronous concurrent computation. We propose a surprisingly simple and natural scheme to obtain se…
Bounded Concurrent Timestamp Systems Using Vector Clocks
Sibsankar Haldar, Paul Vitanyi
Shared registers are basic objects used as communication mediums in asynchronous concurrent computation. A concurrent timestamp system is a higher typed communication object, and h…
Randomized Two-Process Wait-Free Test-and-Set
John Tromp, Paul Vitanyi
We present the first explicit, and currently simplest, randomized algorithm for 2-process wait-free test-and-set. It is implemented with two 4-valued single writer single reader at…
Space-Efficient Routing Tables for Almost All Networks and the Incompressibility Method
Harry Buhrman, Jaap-Henk Hoepman, Paul Vitanyi
We use the incompressibility method based on Kolmogorov complexity to determine the total number of bits of routing information for almost all network topologies. In most models fo…