Haifeng Yu's home page

Haifeng YU
Associate Professor (with tenure)
Computer Science Department
School of Computing
National University of Singapore

Mailing address:
COM2-04-25
15 Computing Drive
School of Computing
National University of Singapore
Republic of Singapore 117418

Current Research Interests

Distributed Systems Security (e.g., blockchains and sybil attacks), Distributed Algorithms, Distributed Computing, Algorithms in Networking.

Information for students interested in joining our research group

Some example research projects in our group.

Some high-level guideline on how to do good research.

If you are considering being my student, please read Advisor's README first and then email me to set up a time to chat.

Research Opportunities (email me your CV and transcripts to apply)

Opening for post-docs: I am actively recruiting post-docs in the area of distributed systems security and algorithms in networking. The starting date is negotiable, and ideally should be by the end of 2024. The salary is internationally competitive (compared to Europe and US). Please email me to apply.

Opening for research interns for students from outside of NUS and undergraduate student researchers (USR) for NUS students : Subject to the final approval of funding, I am recruiting research interns/USRs for 2024. The interns/USRs are expected to work on issues related to distributed systems security and algorithms in networking. To qualify, the applicant needs to be a top undergraduate student in a top university, with a strong academic track record. I particularly welcome internship applicants with achievements in Mathematics/Physics/Information Olympiad at the national or international level. Please email me to apply.

Opening for Ph.D. students seeking advisors: I am actively recruiting Ph.D. students to collaborate on world-class research on distributed algorithms and network algorithms. Besides CS major students, I am also very interested in working with students with a Bachelor's degree in Mathematics. Students with Bachelor's degrees in other related areas (such as Physics) and with strong mathematical background are also very welcome.

Journal Editorial Board Membership

Program Committee Chair

Program Committee Member

Publications

Ruomu Hou, Haifeng Yu, and Yucheng Sun, "Selfied: Sybil Defense in Permissionless Blockchains via In-protocol Bandwidth Consumption." Computer Networks, Volume 256, Jan 2025.
Yucheng Sun, Ruomu Hou, and Haifeng Yu, "Using Multi-dimensional Quorums for Optimal Resilience in Multi-resource Blockchains." Formal Aspects of Computing, Volume 36, Issue 4, Dec 2024.
Yucheng Sun, Ruomu Hou, and Haifeng Yu, "Robust and Low-degree Overlay for Secure Flooding Against Resource-bounded Adversaries." Proceedings of the IEEE Pacific Rim International Symposium on Dependable Computing (PRDC'24), Oct 2024. Winner of Best Paper Award. Technical report version available as [Technical Report]. [Conference talk slides].
Irvan Jahja and Haifeng Yu, "Sublinear Algorithms in T-Interval Dynamic Networks." Algorithmica, Volume 86, Jul 2024.
Yucheng Sun, Ruomu Hou, and Haifeng Yu, "Using Multi-dimensional Quorums for Optimal Resilience in Multi-resource Blockchains." Proceedings of the IEEE Pacific Rim International Symposium on Dependable Computing (PRDC'23), Oct 2023. Winner of 2023 IEEE Distinguished Paper Award on Dependable Computing. Technical report version available as [Technical Report]. [Conference talk slides].
Ruomu Hou and Haifeng Yu, "Optimistic Fast Confirmation While Tolerating Malicious Majority in Blockchains." Proceedings of the IEEE Symposium on Security and Privacy (Oakland'23), May 2023. Technical report version available as [Technical Report]. [Conference talk slides].
Ruomu Hou, Irvan Jahja, Yucheng Sun, Jiyan Wu, and Haifeng Yu, "Achieving Sublinear Complexity under Constant T in T-interval Dynamic Networks." Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA'22), July 2022. Full version available as [Technical Report], May 2022. [Conference talk slides].
Ruomu Hou, Haifeng Yu, and Prateek Saxena, "Using Throughput-Centric Byzantine Broadcast to Tolerate Malicious Majority in Blockchains." Proceedings of the IEEE Symposium on Security and Privacy (Oakland'22), May 2022. Full version available as [Technical Report]. [Conference talk slides].
Irvan Jahja, Haifeng Yu, and Ruomu Hou, "On the power of randomization in distributed algorithms in dynamic networks with adaptive adversaries." Journal of Parallel and Distributed Computing, Volume 159, pp. 35-50, Jan 2022.
Steffen Bondorf, Binbin Chen, Jonathan Scarlett, Haifeng Yu, and Yuda Zhao, "Sublinear-Time Non-Adaptive Group Testing with O(k log n) Tests via Bit-Mixing Coding." IEEE Transactions on Information Theory, Volume 67, Issue 3, pp. 1559-1570, March 2021.
Ruomu Hou, Irvan Jahja, Loi Luu, Prateek Saxena, and Haifeng Yu, "Randomized View Reconciliation in Permissionless Distributed Systems." IEEE/ACM Transactions on Networking (ToN), Volume 28, Issue 5, October 2020.
Irvan Jahja, Haifeng Yu, and Ruomu Hou, "On the Power of Randomization in Distributed Algorithms in Dynamic Networks with Adaptive Adversaries." Proceedings of the International European Conference on Parallel and Distributed Computing (Euro-Par'20), August 2020. Full version available as [Technical Report TRA9/20].
Irvan Jahja and Haifeng Yu, "Sublinear Algorithms in T-interval Dynamic Networks." Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA'20), July 2020. Awarded Best Paper. Full version available as [Technical Report TRA5/20], May 2020. [Conference talk slides].
Haifeng Yu, Ivica Nikolic, Ruomu Hou, and Prateek Saxena, "OHIE: Blockchain Scaling Made Simple." Proceedings of the IEEE Symposium on Security and Privacy (Oakland'20), May 2020. Full version available as [Technical Report]. [Conference talk slides].
Irvan Jahja, Haifeng Yu, and Yuda Zhao, "Some Lower Bounds in Dynamic Networks with Oblivious Adversaries." Distributed Computing, Volume 33, Issue 1, pp. 1-40, Feb 2020. [PDF].
Steffen Bondorf, Binbin Chen, Jonathan Scarlett, Haifeng Yu, Yuda Zhao, "Cross-sender Bit-mixing Coding." Proceedings of the ACM/IEEE International Conference on Information Processing in Sensor Networks (IPSN'19), April 2019. Full version available as [Technical Report]. [Conference talk slides]
Haifeng Yu, Yuda Zhao, and Irvan Jahja., "The Cost of Unknown Diameter in Dynamic Networks." Journal of the ACM, Volume 65, Issue 5, Article 31, September 2018.
Ruomu Hou, Irvan Jahja, Loi Luu, Prateek Saxena, and Haifeng Yu, "Randomized View Reconciliation in Permissionless Distributed Systems." Proceedings of the INFOCOM'18 , April 2018. Full version available as [Technical Report TR12/17], Dec 2017. [Conference talk slides].
Irvan Jahja, Haifeng Yu, and Yuda Zhao, "Some Lower Bounds in Dynamic Networks with Oblivious Adversaries." Proceedings of the International Symposium on Distributed Computing (DISC'17) , October 2017. Full version available as [Technical Report TRA7/17], July 2017. [Conference talk slides].
Haifeng Yu, Yuda Zhao, and Irvan Jahja, "The Cost of Unknown Diameter in Dynamic Networks." Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA'16), July 2016. Full version available as [Technical Report TRA4/16], April 2016. [Conference talk slides].
Ziling Zhou, Binbin Chen, and Haifeng Yu, "Understanding RFID Counting Protocols." IEEE/ACM Transactions on Networking (ToN), Volume 24, Issue 1, pp. 312-327, Feb 2016.
Yuda Zhao, Haifeng Yu, and Binbin Chen, "Near-Optimal Communication-Time Tradeoff in Fault-Tolerant Computation of Aggregate Functions." Distributed Computing, Volume 29, Issue 1, pp. 17-38, Feb 2016.
Seth Gilbert, Xiao Liu, and Haifeng Yu, "On Differentially Private Online Collaborative Recommendation Systems." Proceedings of the International Conference on Information Security and Cryptology (ICISC'15), Nov 2015.
Yuda Zhao, Haifeng Yu, and Binbin Chen, "Near-Optimal Communication-Time Tradeoff in Fault-Tolerant Computation of Aggregate Functions." Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC'14), July 2014. [PDF]. Full version available as [Technical Report TRB5/14], May 2014.
Binbin Chen, Haifeng Yu, Yuda Zhao, and Phillip B. Gibbons, "The Cost of Fault Tolerance in Multi-Party Communication Complexity." Journal of the ACM, Volume 61, Issue 3, Article 19, May 2014.
Binbin Chen, Ziling Zhou, and Haifeng Yu, "Understanding RFID Counting Protocols." Proceedings of the ACM Annual International Conference on Mobile Computing and Networking (MobiCom'13), September 2013. [PDF]. Full version available as [Technical Report]. [Conference talk slides].
Haifeng Yu, Phillip B. Gibbons, and Chenwei Shi, "DCast: Sustaining Collaboration in Overlay Multicast despite Rational Collusion." Proceedings of the ACM Conference on Computer and Communications Security (CCS'12), October 2012. [PDF].
Binbin Chen, Haifeng Yu, Yuda Zhao, and Phillip B. Gibbons, "The Cost of Fault Tolerance in Multi-Party Communication Complexity." Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC'12), July 2012. [PDF]. Full version available as [Technical Report TRA5/12], 2012. [Conference talk slides]. [Slides for a longer, one-hour talk].
Binbin Chen, Ziling Zhou, Yuda Zhao, and Haifeng Yu, "Efficient Error Estimating Coding: Feasibility and Applications." IEEE/ACM Transactions on Networking (ToN), Volume 20, Issue 1, pp. 29-44, February 2012.
Haifeng Yu, "Sybil Defenses via Social Networks: A Tutorial and Survey." ACM SIGACT News Distributed Computing Column, Volume 42, Issue 3, pp 80-101, September 2011. [PDF]
Binbin Chen and Haifeng Yu, "Secure Aggregation with Malicious Node Revocation in Sensor Networks." Proceedings of International Conference on Distributed Computing Systems (ICDCS'11), June 2011. [PDF].
Haifeng Yu, Phillip B. Gibbons, and Chenwei Shi, "Brief Announcement: Sustaining Collaboration in Multicast despite Rational Collusion." Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC'11), June 2011. [PDF].
Haifeng Yu, "Secure and Highly-Available Aggregation Queries in Large-Scale Sensor Networks via Set Sampling." Distributed Computing, Volume 23, Issue 5, pp. 373-394, April 2011.
Binbin Chen, Ziling Zhou, Yuda Zhao, and Haifeng Yu, "Efficient Error Estimating Coding: Feasibility and Applications." Proceedings of ACM SIGCOMM Conference , August 2010. Awarded Best Paper. (Acceptance rate: 33 out of 276) [PDF]. Updated Technical Report.
Haifeng Yu, Phillip B. Gibbons, Michael Kaminsky, and Feng Xiao, "SybilLimit: A Near-Optimal Social Network Defense against Sybil Attacks." IEEE/ACM Transactions on Networking (ToN), Volume 18, Issue 3, pp. 885-898, June 2010.
Suman Nath, Haifeng Yu, and Haowen Chan, "Secure Outsourced Aggregation via One-way Chains." Proceedings of the ACM SIGMOD Conference (SIGMOD'09) , June 2009. [PDF].
Haifeng Yu, Chenwei Shi, Michael Kaminsky, Phillip B. Gibbons, and Feng Xiao, "DSybil: Optimal Sybil-Resistance for Recommendation Systems." Proceedings of the IEEE Symposium on Security and Privacy (Oakland'09), May 2009. (Acceptance rate: 26 out of 254). [PDF]. Full version available as [Technical Report]. [Talk Slides].
Haifeng Yu, "Secure and Highly-Available Aggregation Queries in Large-Scale Sensor Networks via Set Sampling." Proceedings of the 8th ACM/IEEE International Conference on Information Processing in Sensor Networks (IPSN'09), April 2009. Awarded Best Paper. (Acceptance rate: 21 out of 117). [PDF]. Full version available as [Technical Report]. [Talk Slides].
Haifeng Yu and Phillip B. Gibbons, "Optimal Inter-Object Correlation When Replicating for Availability." Distributed Computing, Volume 21, Number 5, February, 2009. (Special issue for PODC'07). [PDF].
Haifeng Yu, Michael Kaminsky, Phillip B. Gibbons, and Abraham Flaxman, "SybilGuard: Defending Against Sybil Attacks via Social Networks." IEEE/ACM Transactions on Networking (ToN), Volume 16, Issue 3, pp. 576-589, June 2008. [PDF].
Haifeng Yu, "Defending Against Sybil Attacks via Social Networks." One-hour talk I gave on SybilLimit in May 2008. [Talk slides]
Haifeng Yu, Phillip B. Gibbons, Michael Kaminsky, and Feng Xiao, "SybilLimit: A Near-Optimal Social Network Defense against Sybil Attacks." Proceedings of the IEEE Symposium on Security and Privacy (Oakland'08), May 2008. (Acceptance rate: 28 out of 249). [PDF]. Full version available as Technical Report [TRA2/08]. [PDF]. [Conference talk slides]
Haifeng Yu, Phillip B. Gibbons, and Michael Kaminsky, "Brief Announcement: Toward an Optimal Social Network Defense against Sybil Attacks." Proceedings of the 26th ACM Symposium on Principles of Distributed Computing (PODC'07), August 2007. [PDF].
Haifeng Yu, "Brief Announcement: DoS-Resilient Secure Aggregation Queries in Sensor Networks." Proceedings of the 26th ACM Symposium on Principles of Distributed Computing (PODC'07), August 2007. [PDF].
Haifeng Yu and Phillip B. Gibbons, "Optimal Inter-Object Correlation When Replicating for Availability." Proceedings of the 26th ACM Symposium on Principles of Distributed Computing (PODC'07), August 2007. (Acceptance rate: 32 out of 204). [PDF]. [Talk Slides].
Jeffrey Pang, Phillip B. Gibbons, Michael Kaminsky, Srinivasan Seshan, and Haifeng Yu, "Defragmenting DHT-based Distributed File Systems." Proceedings of International Conference on Distributed Computing Systems (ICDCS'07), June 2007. (Acceptance rate: 71 out of 528).
Amit Manjhi, Phillip B. Gibbons, Anastassia Ailamaki, Charles Garrod, Bruce M. Maggs, Todd C. Mowry, Christopher Olston, Anthony Tomasic, and Haifeng Yu, "Invalidation Clues for Database Scalability Services." Proceedings of International Conference on Data Engineering (ICDE'07), April 2007. (Acceptance rate: 122 out of 659).
Haifeng Yu, Michael Kaminsky, Phillip B. Gibbons, and Abraham Flaxman, "SybilGuard: Defending Against Sybil Attacks via Social Networks." Proceedings of ACM SIGCOMM Conference , September 2006. (Acceptance rate: 37 out of 298) [PDF]. Paper's SIGCOMM'06 public review by Thomas Anderson. [PDF]. (This paper is fast tracked to Transcations on Networking by SIGCOMM).
Haifeng Yu, Phillip B. Gibbons, and Suman Nath, "Availability of Multi-Object Operations." Proceedings of the Symposium on Networked Systems Design and Implementation (NSDI'06) , May 2006. Awarded Best Paper. (Acceptance rate: 28 out of 110) [PDF].
Suman Nath, Haifeng Yu, Phillip B. Gibbons, and Srinivasan Seshan, "Subtleties in Tolerating Correlated Failures in Wide-area Storage Systems." Proceedings of the Symposium on Networked Systems Design and Implementation (NSDI'06) , May 2006. (Acceptance rate: 28 out of 110) [PDF].
Scott Garriss, Michael Kaminsky, Michael Freedman, Brad Karp, David Mazieres, and Haifeng Yu, "RE: Reliable Email." Proceedings of the Symposium on Networked Systems Design and Implementation (NSDI'06) , May 2006. (Acceptance rate: 28 out of 110) [PDF].
Haifeng Yu, "Signed Quorum Systems." Distributed Computing, Volume 18, Number 4 (Special issue for PODC'04), March 2006. [PDF].
Haifeng Yu and Amin Vahdat, "The Costs and Limits of Availability for Replicated Services." ACM Transactions on Computer Systems (TOCS), Volume 24, Issue 1, February 2006.
Haifeng Yu and Amin Vahdat, "Consistent and Automatic Replica Regeneration." ACM Transactions on Storage (TOS), Volume 1, Number 1, February 2005. [PDF].
Praveen Yalagandula, Suman Nath, Haifeng Yu, Phillip B. Gibbons, and Srinivasan Seshan, "Beyond Availability: Towards a Deeper Understanding of Machine Failure Characteristics in Large Distributed Systems." Proceedings of the Workshop on Real, Large Distributed Systems (WORLDS '04) , December 2004. [PDF].
Haifeng Yu, "Signed Quorum Systems." Proceedings of the 23rd ACM Symposium on Principles of Distributed Computing (PODC'04), July 2004. (Acceptance rate:39 out of 224) [PDF].
Haifeng Yu and Amin Vahdat, "Consistent and Automatic Replica Regeneration." Proceedings of the Symposium on Networked Systems Design and Implementation (NSDI'04) , March 2004. (Acceptance rate: 27 out of 118) [PDF].
Haifeng Yu, "Overcoming the Majority Barrier in Large-Scale Systems." Proceedings of the 17th International Symposium on Distributed Computing (DISC'03) , October 2003. (Acceptance rate: 25 out of 90) [PDF].
Roger Barga, David Lomet, Stelios Paparizos, Haifeng Yu, and Sirish Chandrasekaran, "Persistent Applications via Automatic Recovery." Proceedings of the 17th International Database Engineering and Applications Symposium (IDEAS'03), July 2003.
Haifeng Yu, " Roadmap of TACT publications ." June 2003. Read this first if you do not know which TACT paper you are looking for.
Haifeng Yu and Amin Vahdat, "Design and Evaluation of a Conit-based Continuous Consistency Model for Replicated Services. " ACM Transactions on Computer Systems (TOCS), August 2002. [PDF]. This paper is the extended/combined version of the ICDCS'01 and OSDI'00 papers.
Haifeng Yu and Amin Vahdat, "Minimal Replication Cost for Availability." Proceedings of the 21st ACM Symposium on Principles of Distributed Computing (PODC'02), July 2002. [PDF]. This paper discusses replica placement to achieve optimal availability under the TACT continuous consistency model.
Haifeng Yu and Amin Vahdat, "The Costs and Limits of Availability for Replicated Services." Proceedings of the 18th Symposium on Operating Systems Principles (SOSP'01), October 2001. (Acceptance rate: 17 out of 85) [PDF]. This paper derives the theoretical availability upper bound, and then compares the availability of real protocols against the upper bound.
Haifeng Yu and Amin Vahdat, "Combining Generality and Practicality in a Conit-Based Continuous Consistency Model for Wide-Area Replication." Proceedings of the 21st International Conference on Distributed Computing Systems (ICDCS'01), April 2001. (Acceptance rate: 72 out of 212). [PDF]. This paper discusses the formal TACT continuous consistency model and its properties.
Haifeng Yu and Amin Vahdat, "Design and Evaluation of a Continuous Consistency Model for Replicated Services." Proceedings of the Fourth Symposium on Operating Systems Design and Implementation (OSDI'00), October 2000. (Acceptance rate: 24 out of 111). [PDF]. This paper discusses the TACT prototype design, implementation and evaluation.
Haifeng Yu and Amin Vahdat, "Efficient Numerical Error Bounding for Replicated Network Services." 26th International Conference on Very Large Databases (VLDB'00), September 2000. (Acceptance rate: 53 out of 351). [PDF]. This paper proposes practical consistency protocols to bound numerical error in the TACT consistency model.
Haifeng Yu and Amin Vahdat, "Building Replicated Internet Services Using TACT: A Toolkit for Tunable Availability and Consistency Tradeoffs." Second International Workshop on Advanced Issues of E-Commerce and Web-based Information Systems (WECWIS'00), June 2000.
Haifeng Yu and Gershon Kedem, "DRAM-Page Based Prediction and Prefetching." International Conference on Computer Design (ICCD'00), September 2000.