Publications by Topic

Compact Routing and Graphs Algorithms
Foundations of Distributed Computing
Gossip
Research on Peer to Peer Systems
Quorums
Security in Distributed Systems
Group Communication
Misc

Compact Routing and Graph Algorithms

  1. Reconstructing Approximate Tree Metrics. By Ittai Abraham, Mahesh Balakrishnan, Fabian Kuhn, Dahlia Malkhi, Kunal Talwar, Venugopalan (Rama) Ramasubramanian. In the 26th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing(PODC 2007). To appear.

  2. Strongly-Bounded Sparse Decompositions of Minor Free Graphs. By Ittai Abraham, Cyril Gavoille, Dahlia Malkhi, and Udi Wieder. 19th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA '07). To appear. (Available as Technical Report, Microsoft Research, MSR TR-2006-192).

  3. On Space-Stretch Trade-Offs: Lower bounds. By Ittai Abraham, Cyril Gavoille and Dahlia Malkhi. In the 18th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2006), Cambridge, MA, USA , July/August 2006. PDF.

  4. On Space-Stretch Trade-Offs: Upper bounds. By Ittai Abraham, Cyril Gavoille and Dahlia Malkhi. In the 18th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2006), Cambridge, MA, USA , July/August 2006. PDF.

  5. Routing in Networks with Low Doubling Dimension. By Ittai Abraham, Cyril Gavoille, Andrew Goldberg and Dahlia Malkhi. In the 26th International Conference on Distributed Computing Systems (ICDCS 06), Portugal, July 2006. PDF.

  6. Compact Routing for Graphs Excluding a Fixed Minor. By Ittai Abraham, Cyril Gavoille and Dahlia Malkhi. The 19th Intl. Symposium on Distributed Computing (DISC), Cracow, Poland, September 2005. Springer direct link.

  7. Papillon: Greedy Routing in Rings. By Ittai Abraham, Dahlia Malkhi and Gurmeet Manku. Brief Announcement in the 19th Intl. Symposium on Distributed Computing (DISC), Cracow, Poland, September 2005. Springer direct link.

  8. Name Independent Routing for Growth Bounded Networks. By Ittai Abraham and Dahlia Malkhi. The 17th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA '05). Postscript, PDF.

  9. LLS : a Locality Aware Location Service for Mobile Ad Hoc Networks. By I. Abraham, D. Dolev and D. Malkhi. DIAL M-POMC 2004, Joint Workshop on Foundations of Mobile Computing , October 2004. PDF.

  10. Routing with Improved Communication-Space Trade-Off. By I. Abraham, C. Gavoille and D. Malkhi. Eighteenth International Symposium on Distributed Computing (DISC 2004). Postscript, PDF (directly from Springer).

  11. Compact Routing on Euclidian Metrics. By I. Abraham and D. Malkhi. Twenty-Third Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC 2004). PDF.

  12. Locality-Aware Network Solutions. A survey by Dahlia Malkhi. Leibnitz Center TR 2004-6, School of Computer Science and Engineering, The Hebrew University, 2004. Appears also in the Distributed Computing Column of the Bulletin of the European Association for TCS.

  13. Compact Name-Independent Routing with Minimum Stretch. By Ittai Abraham , Cyril Gavoille , Dahlia Malkhi , Noam Nisan and Mikkel Thorup. ACM Transactions on Algorithms. To appear.
    (Conference version appears in the Sixteenth ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 04). PDF.)

  14. LAND: Stretch (1+epsilon) Locality Aware Networks for DHTs. By Ittai Abraham, Dahlia Malkhi, Oren Dobzinski. ACM-SIAM Symposium on Discrete Algorithms (SODA04), New Orleans, LA, 2004. PDF.

  15. K-Clustering in Wireless Ad-Hoc Networks. By Yaacov Fernandess and Dahlia Malkhi. In the ACM Workshop on Principles of Mobile Computing (POMC 2002), Toulouse 2002, France. Postscript.

Foundations of Data Replication

  1. P2P Replica Synchronization with Vector Sets. By Dahlia Malkhi, Lev Novik and Chris Purcell. Special Issue of ACM Operating Systems Review devoted to systems work at Microsoft Research. PDF.
  2. Concise Version Vectors in WinFS. By Dahlia Malkhi and Doug Terry.  The 19th Intl. Symposium on Distributed Computing (DISC), Cracow, Poland, September 2005. Postscript. To appear in Distributed Computing, special issue on DISC 2005.
  3. Chasing the Weakest System Model for Implementing Omega and Consensus. By Martin Hutle, Dahlia Malkhi, Ulrich Schmid and Lidong Zhou. Brief Announcement In Eighth International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 06), Dallas, TX, USA, November 2006. PDF.
  4. Wait-Free Regular Storage from Byzantine Components. By Ittai Abraham, Gregory Chockler, Idit Keidar and Dahlia Malkhi. Information Processsing Letters. PDF.
  5. Omega Meets Paxos: Leader Election and Stability without Eventual Timely Links. By Dahlia Malkhi, Florin Oprea, and Lidong Zhou. The 19th Intl. Symposium on Distributed Computing (DISC), Cracow, Poland, September 2005. Postscript, PDF, (Full version, MSR TR 2005-93).
  6. Byzantine disk Paxos: Optimal resilience with Byzantine shared memory . By Ittai Abarham, Gregory Chockler, Idit Keidar and Dahlia Malkhi. Distributed Computing 18(5):387-408, April 2006. Springer direct link.
    (Conference version appeared in: Twenty-Third Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC 2004). PDF.) 
  7. Light-Weight Leases for Storage-Centric Coordination . By Gregory Chockler and Dahlia Malkhi. International Journal on Parallal Programming (IJPP)34(2):143-170, April 2006. Postscript, Spring link.
  8. Active Disk Paxos with Infinitely Many Processes. By G. Chockler, D. Malkhi. Distributed Computing 18(1):73-84, Special Issue on PODC 2002, July 2005. Springer direct link.
    (Conference version appeared in Proceedings of the 21st ACM Symposium on Principles of Distributed Computing (PODC '02), August 2002. Postscript.)
  9. Optimal Resilience Wait-Free Storage from Byzantine Components: Inherent Costs and Solutions. By Gregory Chockler, Idit Keidar and Dahlia Malkhi. 2nd Bertinoro Workshop on Future Directions in Distributed Computing, FuDiCo II: S.O.S. Survivability: Obstacles and Solutions.
  10. Objects Shared by Byzantine Processes. By D. Malkhi, M. Merritt, M. Reiter and G. Taubenfeld. Distributed Computing 16(1):37--48, February 2003. Postscript.
    (Conference version appeared in Proceedings of the 14th International Symposium on DIStributed Computing (DISC 2000). Postscript.)
  11. From Byzantine Agreement to Practical Survivability; A position paper. By D. Malkhi. In the International Workshop on Self-Repairing and Self-Configurable Distributed Systems (RCDS 2002), October 2002, Osaka, Japan. Postscript.
  12. State-Machine Replication with Infinitely Many Processes: A position Paper. By G. Chockler, D. Malkhi and D. Dolev. In proceedings of the International Workshop on Future Directions in Distributed Computing (FuDiCo), Bertinoro, Italy, 2002. Postscript.

  13. On k-set Consensus Problems in Asynchronous Systems. R. De Prisco, D. Malkhi and M. Reiter. IEEE Transactions on Parallel and Distributed Systems. Postscript.
    (Conference version appeared in The 18th ACM Symposium on Principles of Distributed Computing (PODC '99), May 1999.)

  14. Failure Detectors in Omission Failure Environments. By Danny Dolev, Roy Friedman, Idit Keidar and Dahlia Malkhi. Brief Announcement in Proceeding of the 16th Annual ACM Symposium on the Principles of Distributed Computing (PODC 97), Santa Barbara, CA, August 1997, page 286. Postscript (1 page), Postscript of full TR (previous version) .
  15. Unreliable Intrusion Detection in Distributed Computations. By Dahlia Malkhi and Michael Reiter. Proceedings of the 10th Computer Security Foundations Workshop (CSFW97), Rockport, MA, June 1997, pp. 116-124. abstract, Postscript .
  16. Failure Detectors in Omission Failure Environments. By Danny Dolev, Roy Friedman, Idit Keidar and Dahlia Malkhi. TR CS 96-1605, Dept. of Computer Science, Cornell University, September 1996. abstract, Postscript .

Gossip

  1. On Collaborative Content Distribution Using Multi-Message Gossip. By Yaacov Fernandess and Dahlia Malkhi. Journal of Parallel and Distributed Computing (JPDC). To appear.
    (Conference version received Best Paper Award in Twentieth IEEE International Parallel and Distributed Processing Symposium (IPDPS 2006), Greece, April 2006.) PDF, abstract.
  2. Diffusing without False Rumors: On Propagating Updates in a Byzantine Environment. By D. Malkhi, Y. Mansour and M. Reiter. Theoretical Computer Science 299(1-3):289-306, April 2003. Download paper from Elsevier Science or Download Postscript (preprint).
    (Conference version appeared in Proceedings of the 18th IEEE Symposium on Reliable Distributed Systems (SRDS '99), October 1999, EPFL, Lausanne, Switzerland, pp. 134-143. )
  3. Optimal Unconditional Information Diffusion. By D. Malkhi, E. Pavlov and Y. Sella. 15th International Symposium on DIStributed Computing (DISC 2001). Postscript
  4. Efficient Update Diffusion in Byzantine Environments. By D. Malkhi, M. Reiter, O. Rodeh and Y. Sella. 20th Symposium on Reliable Distributed Systems (SRDS 2001), October 2001. Postscript.
  5. Replication by Diffusion in Large Networks. By D. Malkhi and Y. Sella. European Research Seminar on Advances in Distributed Systems (Ersads 2001), Bologna, Italy, May 2001. Postscript.

Peer to peer overlays

  1. The Julia Content Distribution Network. By Danny Bickson and Dahlia Malkhi. The 2nd Usenix Workshop on Real Large Distributed Systems (WORLDS 05), San Francisco, December 2005. PDF.
  2. Practical Locality-Awareness for Large Scale Information Sharing . By Ittai Abraham, Ankur Badola, Danny Bickson, Dahlia Malkhi, Sharad Maloo and Saar Ron. The 4th Annual International Workshop on Peer-To-Peer Systems (IPTPS '05). Postscript, PDF. Springer direct link.
  3. Efficient Large Scale Content Distribution. By D. Bickson, D. Malkhi and D. Rabinowitz. The 6th Workshop on Distributed Data and Structures (WDAS'2004), Lausanne, Switzerland. Postscript.
  4. Limiting Duplicate Identities in Distributed Systems (A position paper). By Elliot Jaffe, Dahlia Malkhi and Elan Pavlov. 2nd Bertinoro Workshop on Future Directions in Distributed Computing, FuDiCo II: S.O.S. Survivability: Obstacles and Solutions.
  5. Robust Locality-Aware Lookup Networks. By Ittai Abraham and Dahlia Malkhi. International Workshop on Self-* Properties in Complex Information Systems (SELF-STAR), Bertinoro, Italy, June 2004. Springer's link, PDF.
  6. A Generic Scheme for Building Overlay Networks in Adversarial Scenarios. By I. Abraham, B. Awerbuch, Y. Azar, Y. Bartal, D. Malkhi and E. Pavlov. International Parallel and Distributed Processing Symposium (IDPDS 2003), April 2003, Nice, France. Postscript.
  7. Estimating Network Size from Local Information. By Keren Horowitz and Dahlia Malkhi. The Information Processing Letters journal 88(5):237--243, December 2003. Postscript.
  8. Atomic Data Access in Content Addressable Networks: A Position Paper. By N. Lynch, D. Malkhi and D. Ratajczak. Proceedings of the 1st International Workshop on Peer-to-Peer Systems (IPTPS'02). PDF.
  9. Dynamic Lookup Networks: A position paper. By D. Malkhi. In proceedings of the International Workshop on Future Directions in Distributed Computing (FuDiCo), Bertinoro, Italy, 2002. Postscript.
  10. Viceroy: A Scalable and Dynamic Emulation of the Butterfly. By D. Malkhi, M. Naor and D. Ratajczak. In Proceedings of the 21st ACM Symposium on Principles of Distributed Computing (PODC '02), August 2002. Postscript.

Quorums

  1. Probabilistic Quorums for Dynamic Systems. By Ittai Abraham and Dahlia Malkhi. Distributed Computing, special issue on DISC 2003. PDF.
    (Conference version appeared     in the 17th International Symposium on DIStributed Computing (DISC 2003), Sorento, Italy, October 2003, and received the Best student paper award)

  2. Aquarius: A Data-Centric approach to CORBA Fault-Tolerance. By Gregory Chockler, Dahlia Malkhi, Barak Merimovich, and David Rabinowitz. The workshop on Reliable and Secure Middleware, in the 2003 International Conference on Distributed Objects and Applications (DOA), Sicily, Italy, November 2003. PDF, Postscript, Springer direct link.

  3. A Quorum Based Approach to CORBA Fault-Tolerance. By G. Chokler, D. Dolev and D. Malkhi.
    European Research Seminar on Advances in Distributed Systems (Ersads 2001), Bologna, Italy, May 2001. Postscript.
  4. Persistent Objects in the Fleet System. By D. Malkhi, M. K. Reiter, D. Tulone and E. Ziskind. DARPA's second DARPA Information Survivability Conference and Exposition (DISCEX II), California, June 2001. Postscript.
  5. Fault Detection for Byzantine Quorum Systems. By L. Alvisi, D. Malkhi, E. Pierce and M. Reiter. IEEE Transactions on Parallel and Distributed Systems 12(9):996--1007, 2001. Postscript.
    (Conference version appeared in the Seventh IFIP International Working Conference on Dependable Computing for Critical Applications (DCCA-7), January 1999, San Jose, California, pp. 357-371.Postscript, abstract.)
  6. Backoff Protocols for Distributed Mutual Exclusion and Ordering. By G. Chokler, D. Malkhi and M. Reiter. ICDCS 2001. Postscript.

  7. Probabilistic Quorum Systems. By D. Malkhi, M. Reiter, A. Wool and R. Wright. The Information and Computation Journal 170(2):184--206, November 2001. Postscript.
    (Conference version appeared without Byzantine quorums in Proceeding of the 16th Annual ACM Symposium on the Principles of Distributed Computing (PODC 97), Santa Barbara, CA, August 1997, pp. 267-273. Byzantine quorums were added as a Brief announcement in Proceedings of the 17th Annual ACM Symposium on the Principles of Distributed Computing (PODC 98), June 1998, Puerto Vallarta, Mexico, page 321.)

  8. Dynamic Byzantine Quorum Systems. By Lorenzo Alvisi, Dahlia Malkhi, Evelyn Pierce, Michael Reiter and Rebecca Wright. International Conference on Dependable Systems and Networks (DSN, FTCS-30 and DCCA-8), New York, 2000. Postscript.
  9. An Architecture for Survivable Coordination in Large Distributed Systems. By Dahlia Malkhi and Michael Reiter. IEEE Transactions on Knowledge and Data Engineering, 12(2):187--202, April 2000. Postscript.
    This paper essentially subsumes two previous conference papers:
    Survivable Consensus Objects. By Dahlia Malkhi and Michael Reiter. 17th IEEE Symposium on Reliable Distributed Systems (SRDS 98), October 1998, Purdue University, West Lafayette, Indiana, pp. 271-279;
    Secure and Scalable Replication in Phalanx. By Dahlia Malkhi and Michael Reiter. 17th IEEE Symposium on Reliable Distributed Systems (SRDS 98), October 1998, Purdue University, West Lafayette, Indiana, pp. 51-60.
  10. The Load and Availability of Byzantine Quorum Systems. By Dahlia Malkhi, Michael Reiter and Avishai Wool. SIAM Journal of Computing 29(6):1889-1906, 2000.
    (Conference version: Proceeding of the 16th Annual ACM Symposium on the Principles of Distributed Computing (PODC 97), Santa Barbara, CA, August 1997, pp. 249-257.)
  11. Byzantine Quorum Systems. By Dahlia Malkhi and Michael Reiter. Distributed Computing, 11(4):203--213, 1998. Postscript, abstract,
    (conference version appeared in The 21st Annual Symposium on Theory of Computing (STOC), Texas, May 1997, pp. 569-578.)

Security in Distributed Systems

  1. Hold Your Sessions: an Attack on Java Servlet Session-id Generation. By Zvi Gutterman and Dahlia Malkhi. Cryptographers' Track, RSA 2005 Conference (CT-RSA 05). PDF.
  2. Fairplay --- A Secure Two-Party Computation System. By Dahlia Malkhi , Noam Nisan, Benny Pinkas and Yaron Sella. Best student paper award in Usenix Security 2004 (Security '04). PDF.
  3. E-Voting Without `Cryptography'. By D. Malkhi, O. Margoninsky and E. Pavlov. Proceedings of Financial Cryptography '02 (FC '02). Postscript.
  4. Anonymity without `Cryptography'. By D. Malkhi and E. Pavlov. Financial Cryptography '01. Postscript.

  5. Auditable Metering with Lightweight Security. By Matthew Franklin and Dahlia Malkhi. The Journal of Computer Security, 6(4):237--255, 1998. Postscript
    (Conference version: Financial Cryptography '97, (LNCS, 1318), R. Hirschfeld (Ed.), Anguilla, February 1997, pp. 151-160.)
  6. Secure Multicast in a WAN. By Dahlia Malkhi, Michael Merritt and Ohad Rodeh. Distributed Computing 13:19-28, 2000. abstract, Postscript
    (Conference version: The International Conference on Distributed Computing Systems (ICDCS 97), Baltimore, May 1997, pp. 87-94.)
  7. Secure Execution of Java Applets using a Remote Playground. By Dahlia Malkhi and Michael Reiter. IEEE Transactions on Software Engineering. Postscript, abstract.
    (Conference version appeared in 1998 IEEE Symposium on Security and Privacy, May 1998, Oakland, California, pp 40-51. )
  8. A High-Throughput Secure Reliable Multicast Protocol. By Dahlia Malkhi and Michael Reiter. The Journal of Computer Security, 5, 1997, pp 113-127. abstract, Postscript .
    (Conference version: Proceedings of the 9th Computer Security Foundations Workshop, Ireland, June, 1996, pp 9-17.)

Group Communication (my PhD topic; I spelled my name 'Dalia Malki' back then)

  1. The Transis Approach to High Availability Cluster Communication. By Danny Dolev and Dalia Malki. In Communications of ACM, 39(4), April 1996, pp 87-92. Postscript
  2. Deciding in Partitionable Networks. By Roy Friedman, Idit Keidar, Dalia Malki, Ken Birman and Danny Dolev. Technical Report 95-16, Institute of Computer Science, The Hebrew University of Jerusalem, November 1995. abstract, Postscript .
  3. The Design of the Transis System. By Danny Dolev and Dalia Malki In proceedings of the Dagstuhl Workshop on Unifying Theory and Practice in Distributed Computing, September 1995, pp. 83-98. Springer direct link , Postscript  
  4. The Transis Approach to High Availability Cluster Communication. By Dalia Malki, Yair Amir, Danny Dolev and Shlomo Kramer. Technical Report 94-14, Institute of Computer Science, The Hebrew University of Jerusalem, 1994. Postscript
  5. Uniform Actions in Asynchronous Distributed Systems . By Dalia Malki, Ken Birman, Aleta Ricciardi and Andre Schiper. In proceedings of the 13th annual ACM symposium on the Principles of Distributed Computing (PODC), Los Angeles, August 1994, pp. 274-284. Extended version available as Technical Report 94-1447, Computer Science Department, Cornell University. Postscript, tech report (.ps)
  6. An Asynchronous Membership Protocol that Tolerates Partitions. By Danny Dolev, Dalia Malki and Ray Strong . Research Report RJ 9727 (84359), IBM Research Division, IBM Almaden Research Center, March 1994. Also available as Technical Report TR94-6, Institute of Computer Science, The Hebrew University of Jerusalem, March 1994. Postscript
    (A Brief Announcement about this appears in: A Framework for Partitionable Membership Service. By Danny Dolev, Dalia Malki and Ray Strong. Brief announcement in the ACM symposium on Principles of Distributed Computing(PODC), 1996, p 343. Postscript .
  7. On Distributed Algorithms in a Broadcast Domain. By Danny Dolev and Dalia Malki. 20th Intl. Conference on Automata, Languages and Programming (ICALP), Lund Sweden, July 1993, pp. 371-387. Postscript
  8. Early Delivery Totally Ordered Multicast in Asynchronous Environments. By Danny Dolev, Shlomo Kramer and Dalia Malki.23nd Annual International Symposium on Fault-Tolerant Computing (FTCS), Toulouse, France, June, 1993, pp 544-553. Extended report available as Technical report 92-9, Institute of Computer Science, The Hebrew University of Jerusalem, Israel. Postscript, tech report (.ps)
  9. Membership Algorithms for Multicast Communication Groups. By Yair Amir, Danny Dolev, Shlomo Kramer and Dalia Malki. 6th Intl. Workshop on Distributed Algorithms proceedings (WDAG-6), (LNCS, 647), November 1992, Haifa, Israel, 292-312.Postscript
  10. Transis: A Communication Sub-System for High Availability. By Yair Amir, Danny Dolev, Shlomo Kramer and Dalia Malki. 22nd Annual International Symposium on Fault-Tolerant Computing (FTCS), July, 1992, 76-84. Extended report available as Technical Report 91-13, Institute of Computer Science, The Hebrew University of Jerusalem, Israel. Postscript, tech report (.ps)

Misc

  1. Warm Backup using Snooping. By Danny Dolev, Dalia Malki and Yuval Yarom. The First International Workshop on Services in Distributed and Networked Environments (SDNE), Prague, Czech Republic, June 1994, pp. 60-65. Postscript .

  2. Scalable Secure Storage when Half the System is Faulty. By N. Alon, H. Kaplan, M. Krivelevich, D. Malkhi, and J. Stern.  The Information and Computation Journal 174:203-213, 2002. PDF. (Conference version appears in Proceedings of the 27th International Colloquium on Automata, Languages and Programming (ICALP 2000), Geneva, Switzerland, pp. 576-587.)
    An addendum to this publication is found here.