University of California at Berkeley, Berkeley, CA, USA
Sylvia Ratnasamy, Paul Francis, Mark James Handley, Richard M. Karp, Scott Shenker
ACM SIGCOMM Computer Communication Review, vol. 31,no. 4,2001 – CCR
Hash tables - which map "keys" onto "values" - are an essential building block in modern software systems. We believe a similar functionality would be equally valuable to large distributed systems. In this paper, we introduce the ...
Sylvia Ratnasamy, Paul Francis, Mark James Handley, Richard M. Karp, Scott Shenker
2001 conference on Applications, technologies, architectures, and protocols for computer communications, 2001 – SIGCOMM
Hash tables - which map "keys" onto "values" - are an essential building block in modern software systems. We believe a similar functionality would be equally valuable to large distributed systems. In this paper, we introduce the ...
David E. Culler, Richard M. Karp, David A. Patterson, Abhijit Sahay, Klaus E. Schauser, Eunice E. Santos, Ramesh Subramonian, Thorsten von Eicken
ACM SIGPLAN Notices, vol. 28,no. 7,1993 – SIGPLAN_Notices
A vast body of theoretical research has focused either on overly simplistic models of parallel computation, notably the PRAM, or overly specific models that have few representatives in the real world. Both kinds of models encourage exploitation of ...
David E. Culler, Richard M. Karp, David A. Patterson, Abhijit Sahay, Klaus E. Schauser, Eunice E. Santos, Ramesh Subramonian, Thorsten von Eicken
fourth ACM SIGPLAN symposium on Principles and practice of parallel programming, 1993 – PPoPP
A vast body of theoretical research has focused either on overly simplistic models of parallel computation, notably the PRAM, or overly specific models that have few representatives in the real world. Both kinds of models encourage exploitation of ...
Journal of the ACM, vol. 19,no. 2,1972 – JACM
This paper presents new algorithms for the maximum flow problem, the Hitchcock transportation problem, and the general minimum-cost flow problem. Upper bounds on the numbers of steps in these algorithms are derived, and are shown to compale favorably ...
Richard M. Karp, Raymond E. Miller, Shmuel Winograd
Journal of the ACM, vol. 14,no. 3,1967 – JACM
A set equations in the quantities ai(p), where i = 1, 2, · · ·, m and p ranges over a set R of lattice points in n-space, is called a system of uniform recurrence equations if the following property holds: If p and q are in R and w is an integer ...
Sylvia Ratnasamy, Mark James Handley, Richard M. Karp, Scott Shenker
Networked Group Communication, Third International COST264 Workshop, vol. 2233,2001 – NGC
Most currently proposed solutions to application-level multicast organize the group members into an application-level mesh over which a DistanceVector routing protocol, or a similar algorithm, is used to construct source-rooted distribution trees. ...
Richard M. Karp, Scott Shenker, Christos H. Papadimitriou
ACM Transactions on Database Systems, vol. 28,no. 1,2003 – TODS
We present a simple, exact algorithm for identifying in a multiset the items with frequency more than a threshold θ. The algorithm requires two passes, linear time, and space 1/θ. The first pass is an on-line algorithm, generalizing a well-known ...
Richard M. Karp, Michael Luby, Friedhelm Meyer auf der Heide
Proceedings of the twenty-fourth annual ACM Symposium on Theory of Computing, STOC 1992, 1992 – STOC
We present a randomized simulation of a nlog log (n) log (n)-processor shared memory machine (DMM) with optimal expected delay O(log log (n)) per step of simulation. The time bound for the delay is guaranteed with overwhelming probability. The ...