Danny Hendler's home page
I am a faculty member in the department
of Computer Science at Ben-Gurion University. I have returned to
Academy in 2001 after working hard for 18 years in the High-Tech
industry; somewhat surprisingly, I have been working (almost) as hard since then.
Research interests
I am mainly interested in both the practical and the theoretical aspects of concurrent programming. More
specifically, my work in these areas has focused so far on the following topics:
- Transactional memory
- Local spin mutual-exclusion and leader-election algorithms
- Highly scalable shared-memory algorithms
- Contention-aware metrics and algorithms
- Lower bounds for message-passing and shared-memory systems
- Dynamic load balancing in shared-memory systems
I am also interested in machine-learning based anomaly detection and in packet classification algorithms, specifically those using content-addressable memory.
Teaching
Professional activities
Journal articles
-
RMR-Efficient Implementations of Comparison
Primitives Using Read and Write Operations,
with Wojciech Golab, Vassos Hadzilacos and Philipp Woelfel, Distributed Computing 25(2): 109-162. A preliminary version appeared in proc. of PODC 2007.
-
On the Inherent Sequentiality of Concurrent Objects,
with Faith Ellen and Nir Shavit, SIAM Journal on Computing 41(3): 519-536. A preliminary version appeared in proc. of FOCS 2005.
-
Layered Interval Codes for TCAM-Based Classification,
with David Hay and Anat Bremler-Barr, Computer Networks 56(13): 3023-3039. A preliminary version appeared in proc. of INFOCOM 2009.
-
On the Impact of Serializing Contention Management on STM Performance,
with Tomer Heber and Adi Suissa, Journal of Parallel and Distributed Computing 72(6): 739-750, 2012. A preliminary version appeared in proc. of OPODIS 2009.
-
Randomized Mutual Exclusion with sub-logarithmic RMR complexity,
with Philipp Woelfel, Distributed Computing 24(1): 3-19, 2011. A preliminary version appeared in proc. of PODC 2009.
-
Space-efficient TCAM-based classification using Gray coding,
with Anat Bremler-Barr, IEEE Transactions on Computers 61(1): 18-30, 2012. A preliminary version appeared in proc. of INFOCOM 2007.
-
PEDS: A Parallel Error Detection Scheme for TCAM Devices,
with Anat Bremler-Barr, David Hay and Ron M. Roth, IEEE/ACM Transactions on Networking, 18(5):
1665-1675, 2010. A preliminary version appeared in INFOCOM 2009 (best paper award runner up).
-
An O(1) RMRs Leader Election Algorithm,
with Wojciech Golab and Philipp Woelfel, SIAM Journal on Computing 39(7): 2726-2760, 2010. A preliminary version appeared in proc. of PODC 2006.
-
A Scalable Lock-Free Stack Algorithm,
with Nir Shavit and Lena Yerushalmi, Journal of Parallel and Distributed Computing 70(1): 1-12, 2010. A preliminary version appeared in proc. of SPAA 2004.
-
Time and Space Lower Bounds for Implementations Using kCAS,
with Hagit Attiya, Transactions on Parallel and Distributed Systems 21(2): 162-173, 2010. A preliminary version appeared in proc. of DISC 2005.
-
The Complexity of Obstruction-free Implementations,
with Hagit Attiya, Rachid Guerraoui and Petr Kouznetsov, Journal of the ACM 56(4), 2009.
-
Bounded-Wait Combining: Constructing Robust and High-Throughput Shared Objects,
with Shay Kutten, Distributed Computing 21(6): 405-431, 2009. A preliminary version appeared in proc. of DISC 2006.
-
Solo-Valency and the Cost Of Coordination,
with Nir Shavit, Distributed Computing 21(1): 43-54, 2008. A preliminary version appeared in proc. of PODC 2003.
-
A dynamic-sized nonblocking work stealing deque,
with Yossi Lev, Mark Moir and Nir Shavit, Distributed Computing 8(4) (special issue of
selected papers from DISC 2004): 267-277, 2006.
-
On the inherent weakness of conditional primitives,
with Faith Ellen Fich and Nir Shavit, Distributed Computing 8(3) (special issue of
selected papers from PODC 2004): 115-120, 2006.
-
On the Complexity of Global Computation in the Presence of Link Failures: the General Case,
with Yehuda Afek, Distributed Computing 8(3): 115-120, 1995. A preliminary version appeared in proc. of ISTCS 2003.
Conference papers not yet in journals
-
Lower Bounds for Restricted-Use Objects,
with Jim Aspnes, Hagit Attiya and Keren Censor-Hillel, SPAA 2012, pages 172-181.
-
A Dynamic Elimination-Combining Stack Algorithm,
with Gal Bar-Nissan and Adi Suissa, OPODIS 2011, to pages 544-561.
-
Metric Anomaly Detection via Asymmetric Risk Minimization,
with Aryeh Kontorovich and Eitan Menachem, SIMBAD 2011, pages 17-30.
-
Laws of Order: Expensive Synchronization in
Concurrent Algorithms Cannot be Eliminated,
with Hagit Attiya, Rachid Guerraoui, Petr Kuznetsov, Maged M. Michael and Martin Vechev, POPL 2011, pages 487-498.
-
An Adaptive Technique for Constructing Robust
and High-Throughput Shared Objects,
with Shay Kutten and Erez Michalak, OPODIS 2010, pages 318-332.
-
Scalable Flat-Combining Based Synchronous Queues,
with Itai Incze, Nir Shavit and Moran Tzafrir, DISC 2010, pages 79-93.
-
Adaptive Randomized Mutual Exclusion in Sub-Logarithmic Expected Time,
with Philipp Woelfel, PODC 2010, pages 141-150.
-
Flat Combining and the Synchronization-Parallelism Tradeoff,
with Itai Incze, Nir Shavit and Moran Tzafrir, SPAA 2010, pages 355-364.
-
Scheduling Support for
Transactional Memory Contention Management,
with Alexandra Fedorova, Pascal Felber, Julia L. Lawall, Walther Maldonado, Patrick Marlier, Gilles Muller and Adi Suissa, PPoPP 2010, pages 79-90.
-
CAR-STM: Scheduling-Based Collision Avoidance and Resolution for Software
Transactional Memory,
with Shlomi Dolev and Adi Suissa, PODC 2008, pages 125-134.
-
Tight RMR Lower Bounds for Mutual Exclusion and Other Problems,
with Hagit Attiya and Philipp Woelfel, STOC 2008, pages 217-226.
-
Synchronizing Without Locks is Inherently Expensive,
with Hagit Attiya, Rachid Guerraoui and Petr Kouznetsov, PODC 2006, pages 300-307.
-
Work Dealing,
with Nir Shavit, SPAA 2002, pages 164-172.
-
Non-Blocking Steal-Half Work Queues,
with Nir Shavit, PODC 2002, pages 280-289.
Submitted papers