Roy Friedman - List of Publications

Highlighted Paper

In early 1996, Ken Birman and I submitted the following paper to PODC. This paper formally proves that no system can implement strongly consistent (non commuting) operations in a responsive (highly available) manner despite network partitions. Unfortunately, the paper was flatly rejected with all three reviewers claiming that the result was not interesting. Four years later, Eric Brewer presented during a PODC keynote speech a conjecture, which became to be known as Brewer's CAP theorem, stating exactly the same thing (but in an informal manner). This was later formally proved and discussed in multiple other papers, all failing to give credit to our original result. Interstingly, our explicit restriction to non-commuting operations hinted at a way to circumvent the impossibility result by using commutative operations, as was later rediscovered by other works, who also failed to give us credit.

  • If you need a good caching solution, I strongly advise to read our recent TinyLFU paper (integrated into the Caffeine Java cache) where we offer a novel cache management scheme, which yielded the best hit ratio among all schemes we have experimented with on all traces we have tested. And like all best things in life, it is totally free -- no royalties to pay and an open source reference implementa tion.
  • Papers in Journals

    1. R. Friedman, G. Kliot, C. Avin. Probabilistic quorum systems in wireless Ad Hoc networks ACM Transactions Computer Systems (TOCS) 28(3), September 2010

    2. M. Vecchio, A. C. Viana, A. Ziviani, R. Friedman. DEEP: Density-based proactive data dissemination protocol for wireless sensor networks with uncontrolled sink mobility Computer Communications 33(8), 929-939, May 2010

    3. R. Friedman, A. Shotland, G. Simon. Efficient route discovery in hybrid networks Ad Hoc Networks 7(6), 1110-1124, August 2009

    4. V. Drabkin, R. Friedman, G. Kliot. On the (Un)Reliability of TCP Connections: The Return of the End-to-End Argument. IEEE Distributed Systems Online, 9(8), August 2008

    5. Z. Bar-Yossef, R. Friedman, G. Kliot. RaWMS - Random Walk Based Lightweight Membership Service for Wireless Ad Hoc Networks ACM Transactions on Computer Systems (TOCS), 26(2), 1-66, June 2008

    6. A. Agbaria and R. Friedman. Model-based performance evaluation of distributed checkpointing protocols Performance Evaluation, 65(5), 345-365, May 2008

    7. R. Friedman, D. Gavidia, L. Rodrigues, A. C. Viana, and S. Voulgaris. Gossiping on MANETs: the beauty and the beast Operating Systems Review, 41(5), 67-74, October 2007

    8. R. Friedman, A. Mostefaoui, S. Rajsbaum, M. Raynal. Asynchronous Agreement and Its Relation with Error-Correcting Codes IEEE Transactions on Computers, 65(7), 865-875, July 2007

    9. R. Friedman, A. Mostefaoui, M. Raynal. On the Respective Power of <>P and <>S to Solve One Shot Agreement Problems IEEE Transactions on Parallel and Distributed Systems, 18(5), 589-597, May 2007.

    10. E. Anceaume, R. Friedman and M. Gradinariu. Managed Agreement: Generalizing Two Fundamental Distributed Agreement Problems Information Processing Letters, 101(5), March 2007.

    11. R. Friedman and E. Hadad. Analyzing Distributed-System Performance: Latency vs. Throughput, IEEE Distributed Systems Online, 6(1), January 2006.

    12. R. Friedman, A. Mostefaoui, and M. Raynal. <>P_mute-Based Consensus for Asynchronous Sytems, Parallel Processing Letters, 15(2), pages 169-182, June 2005.

    13. R. Friedman, A. Mostefaoui, and M. Raynal. Asynchronous Bounded Lifetime Failure Detectors Information Processing Letters, 94(2), pages 85-91, April 2005.

    14. R. Friedman, A. Mostefaoui, and M. Raynal. Simple and Efficient Oracle-Based Consensus Protocols for Asynchronous Byzantine Systems IEEE Transactions on Dependable and Secure Computing, March 2005.

    15. R. Friedman and G. Tcharny. Evaluating Failure Detection in Mobile Ad-Hoc Networks, International Journal of Wireless and Mobile Computing Vol. 1, No. 8, 2005.

    16. R. Friedman, A. Mostefaoui, M. Raynal. A Weakest Failure Detector-Based Asynchronous Consensus Protocol for f'<'n Information Processing Letters, 90(1), pages 39-46, 2004.

    17. A. Agbaria, H. Attiya, R. Friedman, and R. Vitenberg, Quantifying Rollback Propagation in Distributed Checkpointing. Journal of Parallel and Distributed Computing, 63(4), pages 370-384, 2004.

    18. G. Chockler, R. Friedman and R. Vitenberg. On the Composability of Consistency Conditions. Information Processing Letters, 86(4), pages 169-176, 2003.

    19. A. Agbaria and R. Friedman. Starfish: Fault-Tolerant Dynamic MPI Programs on Clusters of Workstations. Cluster Computing: The Journal of Networks, Software Tools and Applications, 6(3), pages 227-236, 2003.

    20. A. Agbaria and R. Friedman. Virtual Machine Based Heterogeneous Checkpointing. Software: Practice and Experience, Vol 32, No 12, pages 1175-1192, October 2002.

    21. R. Friedman, S. Manor, and K. Guo. Scalable Stability Detection Using Logical Hypercube. IEEE Transactions on Parallel and Distributed Systems, Vol. 13, No. 9, pages 972-984, September 2002.

    22. R. Friedman and E. Hadad, Client Side Enhancements using Portable Interceptors. Computer System Science and Engineering, Vol. 17, No. 2, pages 3-9, 2002.

    23. R. Friedman and E. Hadad, A Group Object Adaptor-Based Approach to CORBA Fault-Tolerance, IEEE Distributed Systems Online, Vol. 2, No. 7, Special Issue on Middleware 2001, November 2001.

    24. R. Friedman, E. Biham, A. Itzkovitz, and A. Schuster, Symphony: Managing Virtual Servers in the Global Village, Cluster Computing: The Journal of Networks, Software Tools and Applications, Vol. 4, No. 3, pages 221-233, 2001

    25. R. Friedman and D. Mosse, Load Balancing Schemes for High-Throughput Distributed Fault-Tolerant Servers, Journal of Parallel and Distributed Computing, Vol. 59, No. 3, pages 475-488, December 1999.

    26. R. Baldoni, R. Friedman, and R. van Renesse, The Hierarchical Daisy Architecture for Causal Delivery, Distributed Systems Engineering Journal, Vol. 6, pages 71-81, 1999

    27. K. Birman, R. Friedman, M. Hayden, and I. Rhee. Middleware Support for Distributed Multimedia and Collaborative Computing, Software: Practice and Experience, Vol. 29, No. 14, pages 1285-1312, 1999

    28. H. Attiya and R. Friedman. A Correctness Condition for High-Performance Multiprocessors. SIAM Journal of Computing. Vol. 27, No. 2, April 1998.

    29. H. Attiya, S. Chaudhuri, R. Friedman, and J. Welch. Shared Memory Consistency Conditions for Non-Sequential Execution: Definitions and Programming Strategies. SIAM Journal of Computing. Vol. 27, No. 1, February 1998.

    30. A. Dubrovsky, R. Friedman, and A. Schuster. Load Balancing in a Distributed Shared Memory System. International Journal of Applied Software Technology. Vol. 27, No. 8, August 1997.

    31. R. Friedman, M. Goldin, A. Itzkovitz, and A. Schuster, Millipede: Easy Parallel Programming in Available Distributed Environments. Software: Practice and Experience. Vol. 27, No. 8, pages 929-965, August 1997. A shorter version appeared in Euro-par 96.

    32. H. Attiya and R. Friedman. Limitation of Fast Consistency Conditions for Distributed Shared Memories. Information Processing Letters. Vol. 5, No. 5, 1996, Pages 243-248.

    33. R. Friedman. Implementing Hybrid Consistency with High Level Synchronization Operations. Distributed Computing. Vol. 9, No. 3, pages 119-129, 1995.

    Papers in Conferences

    1. G. Einziger and R. Friedman. A Formal Analysis of Conservative Update Based Approximate Counting. IEEE International Conference on Computing, Networking and Communications (ICNC), Anaheim, California, USA February 16-19, 2015. Also available as Technical Report CS-2014-04, Department of Computer Science, Technion.

    2. V. Drabkin, R. Friedman, G. Kliot, and M. Segal. RAPID: Reliable Probabilistic Dissemination in Wireless Ad-Hoc Networks. 26th IEEE Symposium on Reliable Distributed Systems(SRDS), Baijing, China, October 2007.

    3. V. Drabkin, R. Friedman, and M. Gradinariu. Self-stabilizing Wireless Connected Overlays 10th International Conference On Principles Of Distributed Systems(OPODIS), Bordeaux, France, December 2006.

    4. R. Friedman and E. Hadad. Using Selective Acknowledgements to Reduce the Memory Footprint of Replicated Services 8th International Symposium on Distributed Objects and Applications(DOA), Montpellier, France. October/November 2006.

    5. R. Friedman and E. Hadad. Adaptive Batching for Replicated Servers 25th IEEE Symposium on Reliable Distributed Systems(SRDS), Leeds, UK. October 2006.

    6. V. Drabkin, R. Friedman, and A. Kama. Practical Byzantine Group Communication 26th International Conference on Distributed Computing Systems (ICDCS), Lisbon, Portugal. July 2006.

    7. Z. Bar-Yossef, R. Friedman, and G. Kliot. RaWMS - Random Walk based Lightweight Membership Service for Wireless Ad Hoc Networks 7th ACM International Symposium on Mobile Ad Hoc Networking and Computing(MobiHoc), Florence, Italy. May 2006.

    8. R. Friedman, M. Raynal, and C. Travers. Two Abstractions for Implementing Atomic Objects in Dynamic Systems 9th International Conference on Principles of Distributed Systems (OPODIS), Pisa, Italy. December 2005.

    9. R. Friedman, A. Mostefaoui, M. Raynal. Intersecting Sets: a Basic Abstraction for Asynchronous Agreement Problems 11th IEEE International Symposium, Pacific Rim Dependable Computing (PRDC), Changsha, China. December 2005.

    10. V. Drabkin, R. Friedman, and M. Segal Efficient Byzantine Broadcast in Wireless Ad-Hoc Networks. The IEEE International Conference on Dependable Systems and Networks (DSN), Yokohama, Japan. June 2005.

    11. A. Agbaria and R. Friedman. A Replication- and Checkpoint-Based Approach for Anomaly-Based Intrusion Detection and Recovery. The 2nd International Workshop on Security in Distributed Computing Systems (SDCS), June 2005.

    12. R. Friedman and G. Korland. Timed Grid Routing (TIGR) Bites off Energy 6th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHOC), May 2005, Urbana, USA.

    13. R. Friedman, A. Mostefaoui, M. Raynal. Building and Using Quorums Despite any Number of Process Crashes Fifth European Dependable Computing Conference (EDCC) April 2005.

    14. R. Friedman, A. Most\'efaoui, and M. Raynal. The Notion of Veto Number for Distributed Agreement Problems. 6th International Workshop on Distributed Computing (IWDC), Kolkata, India. December 2004.

    15. E. Anceaume, R. Friedman, M. Gradinariu, and M. Roy. An Architecture for Dynamic Scalable Self-Managed Distributed Transactions 6th International Symposium on Distributed Objects and Applications (DOA). October 2004.

    16. R. Friedman, A. Mostefaoui, M. Raynal. Simple and Efficient Oracle-Based Consensus Protocols for Asynchronous Byzantine Systems 23rd IEEE Symposium on Reliable Distributed Systems (SRDS), October 2004.

    17. R. Friedman and M. Raynal. The Benefits of the Functional Modular Approach to Distributed Data Management Systems. Workshop on Dependable Distributed Data Management (in conjunction with SRDS), Florianopolis, Brazil. October 2004.

    18. R. Friedman, A. Mostefaoui, M. Raynal. On the Notion of Veto Number and the Respective Power of <>P and <>S to Solve One Shot Agreement Problems 18th International Symposium on DIStributed Computing (DISC), October 2004.

    19. R. Friedman, M. Gradinariu, and G. Simon, Locating Cache Proxies in MANETs. 5th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHOC), May 2004, Tokyo, Japan.

    20. R. Vitenberg and R. Friedman, On the Performance of a CORBA Caching Service over the Wide Internet. 5th International Symposium on Distributed Objects and Applications (DOA), November 2003.

    21. R. Friedman and A. Kama, Transparent Fault-Tolerant Java Virtual Machine. 22nd IEEE Symposium on Reliable Distributed Systems (SRDS), October 2003.

    22. R. Vitenberg, R. Friedman, On the Locality of Consistency Conditions. 17th International Symposium on DIStributed Computing (DISC), October 2003.

    23. A. Agbaria, A. Freund and R. Friedman, Evaluating Distributed Checkpointing Protocols. 23rd IEEE International Conference on Distributed Computing Systems (ICDCS), May 2003.

    24. R. Friedman, L. Baram and S. Abarbanel, Fault-Tolerant Multi-Server Video-on-Demand Service. 17th IEEE International Parallel and Distributed Processing Symposium (IPDPS), April 2003.

    25. R. Friedman, A. Mostefaoui, S. Rajsbaum and M. Raynal. Using Error-Correcting Codes to Solve Distributed Agreement Problems: A Future Direction in Distributed Computing? Future Directions in Distributed Computing: Research and Position Papers Springer-Verlag LNCS #2584, 2003

    26. R. Friedman. Fuzzy Group Membership. Future Directions in Distributed Computing: Research and Position Papers Springer-Verlag LNCS #2584, 2003

    27. R. Friedman and D. Laor. Soft Real-Time Layered Group Communication. 14th IASTED International Conference on Parallel and Distributed Computing and Systems (PDCS 2002), November 2002.

    28. R. Friedman. Caching Web Services in Mobile Ad-Hoc Networks: Opportunities and Challenges. 2nd ACM Workshop on Principles of Mobile Computing (POMC), Toulouse, France. October 2002.

    29. H. Atzmon, R. Friedman and R. Vitenberg. Replacement Policies for a Distributed Object Caching Service. 4th International Symposium on Distributed Objects and Applications (DOA 2002), October 2002.

    30. R. Friedman, A. Mostefaoui, S. Rajsbaum, and M. Raynal, Distributed Agreement and its Relation with Error-Correcting Codes 16th International Symposium on DIStributed Computing (DISC 2002) , October 28-30, 2002. Toulouse, France

    31. R. Friedman. Fuzzy Group Membership. FuDiCo 2002: International Workshop on Future Directions in Distributed Computing, Bertinoro, Italy, June 2002.

    32. A. Agbaria and R. Friedman. Virtual Machine Based Heterogeneous Checkpointing. International Parallel and Distributed Processing Symposium (IPDPS 2002), Ft. Lauderdale, FL, USA, April 2002.

    33. R. Friedman and E. Hadad. FTS: A High-Performance CORBA Fault-Tolerance Service. Workshop on Object-oriented Real-time Dependable Systems (WORDS 2002), San Diego, CA, USA, January 2002.

    34. A. Agbaria, H. Attiya, R. Friedman, and R. Vitenberg. Quantifying Rollback Propagation in Distributed Checkpointing. 20th IEEE Symposium on Reliable Distributed Systems (SRDS 2001), October 2001.

    35. R. Friedman and R. Vitenberg. A Framework for Caching Multimedia Objects in the Internet. International Workshop on Multimedia Middleware, October 2001

    36. R. Friedman and E. Hadad. Client Side Enhancements using Portable Interceptors. Workshop on Object-oriented Real-time Dependable Systems (WORDS 2001), Rome, Italy, January 2001.

    37. G. Chockler, R. Friedman, and R. Vitenberg. Consistency Conditions for a CORBA Caching Service. 14th International Symposium on DIStributed Computing (DISC 2000), October 2000.

    38. G. Chockler, D. Dolev, R. Friedman, and R. Vitenberg. Implementing a Distributed CORBA Caching Service. Middleware 2000, April 2000. Best Paper Award.

    39. R. Friedman, S. Manor, and K. Guo. Scalable Stability Detection Using Logical Hypercube. 18th IEEE Symposium on Reliable Distributed Systems (SRDS '99), October 1999.

    40. R. Friedman, E. Biham, A. Itzkovitz, and A. Schuster. Symphony: Managing Virtual Servers in the Global Village. 5th International Euro-Par Conference, September 1999.

    41. A. Agbaria and R. Friedman. Starfish: Fault-Tolerant Dynamic MPI Programs on Clusters of Workstations. 8th IEEE International Symposium on High Performance Distributed Computing (HPDC 99), August 1999.

    42. R. Friedman. Recent Advances and Challenges in Group Communication. 3rd International Austrian-Israeli Technion Symposium: Software for Communication Technology, April 1999.

    43. K. Birman, R. Friedman, M. Hayden, and I. Rhee. Middleware Support for Distributed Multimedia and Collaborative Computing. 10th SPIE/ACM MultiMedia Computing and Networking (MMCN '98), January 1998.

    44. R. Friedman and D. Mosse. Load Balancing Schemes for High-Throughput Distributed Fault-Tolerant Servers. 16th Symposium on Reliable Distributed Systems (SRDS '97), 1997. Also available as Technical Report 96-1616, Department of Computer Science, Cornell University.

    45. R. Friedman and A. Vaysburd. Fast Replicated State Machines Over Partitionable Networks. 16th Symposium on Reliable Distributed Systems (SRDS '97), 1997. Earlier version available as Technical Report 95-1554, Department of Computer Science, Cornell University.

    46. K. Birman, W. Vogels, K. Guo, M. Hayden, T. Hickey, R. Friedman, S. Maffeis, R. van Renesse, and A. Vaysburd. Moving the Ensemble Groupware System to Windows NT and Wolfpack. USENIX Windows NT Workshop, 1997.

    47. R. Baldoni, R. Friedman, and R. van Renesse. The Hierarchical Daisy Architecture for Causal Delivery. 17th International Conference on Distributed Computing Systems (ICDCS '97) , 1997. Also available as Technical Report 96-1610, Department of Computer Science, Cornell University.

    48. R. Friedman and R. van Renesse. Packing Messages as a Tool for Boosting the Performance of Total Ordering Protocols. 6th IEEE International Symposium on High Performance Distributed Computing (HPDC '97), 1997. Also available as Technical Report 95-1527, Department of Computer Science, Cornell University.

    49. R. Friedman and R. van Renesse. Strong and Weak Virtual Synchrony in Horus. 15th Symposium on Reliable Distributed Systems (SRDS '96), 1996. Also available as Technical Report 95-1537, Department of Computer Science, Cornell University.

    50. R. Friedman and K. Birman. Using Group Communication Technology to Implement a Reliable and Scalable Distributed IN Coprocessor. TINA 96. Also available as Technical Report 96-1605, Department of Computer Science, Cornell University.

    51. R. van Renesse, K. Birman, R. Friedman, M. Hayden, and D. Karr. A Framework for Protocol Composition in Horus. 14th ACM Symp. on Principles of Distributed Computing (PODC '95).

    52. H. Attiya and R. Friedman. Programming DEC-Alpha Based Multiprocessors the Easy Way. 6th ACM Symp. on Parallel Algorithms and Architectures (SPAA 94). Also available as Technical Report LPCR 9411, Department of Computer Science, The Technion.

    53. R. Friedman. Implementing Hybrid Consistency with High Level Synchronization Operations. 12th ACM Symp. on Principles of Distributed Computing (PODC '93), 1993. Also available as Technical Report 781, Department of Computer Science, The Technion.

    54. H. Attiya, S. Chaudhuri, R. Friedman, and J. Welch. Shared Memory Consistency Conditions for Non-Sequential Execution: Definitions and Programming Strategies. 5th ACM Symposium On Parallel Algorithms and Architectures (SPAA '93), 1993.

    55. H. Attiya and R. Friedman. A Correctness Condition for High-Performance Multiprocessors. 24th ACM Symp. on the Theory Of Computing (STOC '92), 1992.

    Technical Reports

    1. R. Friedman and Nir Hauser COARA: Code Offloading on Android with AspectJ Technical Report arXiv:1604.00641, April 2016.

    2. G. Einziger and R. Friedman TinyLFU: A Highly Efficient Cache Admission Policy Technical Report arXiv:1512.00727, December 2015.

    3. G. Einziger and R. Friedman Counting with TinyTable: Every Bit Counts! Technical Report CS-2015-04, Department of Computer Science, The Technion. March 2015.

    4. G. Einziger and R. Friedman TinySet - An Access Efficient Self Adjusting Bloom Filter Construction Technical Report CS-2015-03, Department of Computer Science, The Technion. March 2015.

    5. R. Friedman and G. Kliot. Location Services in Wireless Ad Hoc and Hybrid Networks: A Survey Technical Report CS-2006-10, Department of Computer Science, The Technion. April 2006.

    6. R. Friedman and E. Hadad. A Case for Efficient Portable Serialization in CORBA Technical Report CS-2005-18, Department of Computer Science, The Technion. December 2005.

    7. R. Friedman and M. Raynal. Modularity: a First Class Concept to Address Distributed Systems Technical Report PI-1707, IRISA, Rennes, France. April 2005.

    8. R. Friedman and G. Korland. RLISE: Relative Location with Incomplete Stationary Emitters Technical Report CS-2005-06, Department of Computer Science, The Technion. February 2005.

    9. R. Friedman and S. Manor. Causal Ordering in Deterministic Overlay Networks Technical Report CS-2004-04, Department of Computer Science, The Technion. April 2004.

    10. R. Friedman and G. Tcharny. Fuzzy Membership Based Reliable Delivery for Mobile Ad-Hoc Networks Technical Report CS-2003-14, Department of Computer Science, The Technion. December 2003.

    11. R. Friedman and G. Tcharny. Stability Detection in Mobile Ad-Hoc Networks Technical Report CS-2003-12, Department of Computer Science, The Technion. November 2003.

    12. R. Friedman, A. Mostefaoui, M. Raynal. Building and Using Pt-Based Quorums Despite any Number t of Process of Crashes Technical Report PI-1583, IRISA, Rennes, France. September 2003.

    13. A. Agbaria, Ari Freund, and R. Friedman. Evaluating Distributed Checkpointing Protocols Technical Report CS-2002-15, Department of Computer Science, The Technion. September 2002.

    14. R. Friedman. Fast Adaptive Multiple-Shot Consensus Technical Report CS-2002-08, Department of Computer Science, The Technion.

    15. R. Friedman. A Simple Coding-Theory Based Characterization of Conditions for Solving Consensus Technical Report CS-2002-06, Department of Computer Science, The Technion.

    16. K. Birman, R. Friedman, and M. Hayden. The Maestro Group Manager: A Structuring Tool For Applications With Multiple Quality of Service Requirements Technical Report 97-1619, Department of Computer Science, Cornell University.

    17. D. Dolev, R. Friedman, I. Keidar, and D. Malki. Failure Detectors in Omission Failure Environments. Technical Report 96-1608, Department of Computer Science, Cornell University.

    18. R. Friedman and K. Birman. Trading Consistency for Availability in Distributed Systems. Technical Report 96-1579, Department of Computer Science, Cornell University.

    19. R. Friedman, I. Keidar, D. Malki, K. Birman, and D. Dolev. Deciding in Partitionable Networks. Technical Report 95-1554, Department of Computer Science, Cornell University.

    20. R. Friedman. Using Virtual Synchrony to Develop Efficient Fault Tolerant Distributed Shared Memories. Technical Report 95-1506, Department of Computer Science, Cornell University.

    Back to Roy's home page