More Like this

1. DAG-GNN: DAG Structure Learning with Graph Neural Networks

   Yu, Y.; Chen, J.; Gao, T.; Yu, M. (April 2019, International Conference on Machine Learning 2019)
2. LiDO-DAG: A Framework for Verifying Safety and Liveness of DAG-Based Consensus Protocols

   https://doi.org/10.1145/3729306  

   Qiu, Longfei; Xiao, Jingqi; Shin, Ji-Yong; Shao, Zhong (June 2025, Proceedings of the ACM on Programming Languages)

   Blockchains operating at the global scale demand high-performance byzantine fault-tolerant (BFT) consensus protocols. Most classic PBFT-like protocols suffer from an issue known as the leader bottleneck, which severely limits their throughput and resource utilization. Recently, Directed Acyclic Graph, or DAG-based protocols, have emerged as a promising approach for eliminating the leader bottleneck and achieving better performance. They attain higher throughput by separating data dissemination and block ordering. However, their safety and liveness logic is also significantly more elaborate. So far, most DAG-based protocols have only enjoyed on-paper security proofs, and it is not clear how to construct formal proofs of these protocols efficiently. We introduce LiDO-DAG, a concurrent object model that abstracts the common logic of these protocols. LiDO-DAG is constructed by combining a DAG abstraction and LiDO, a recently proposed abstraction for leader-based consensus. To demonstrate that our framework enables rapid validation of new DAG-based protocol designs, we implemented LiDO-DAG in Coq and applied it to three recent DAG-based protocols, including Narwhal, Bullshark, and Sailfish. Our framework readily yields mechanized safety and liveness proofs for all three protocols, which are also the first mechanized liveness proofs of any DAG-based protocol. Our framework has also revealed an optimization for Sailfish that improves its worst-case latency. 

   more » « less
3. Minimizing DAG Utilization by Exploiting SMT

   https://doi.org/10.1109/RTAS54340.2022.00029  

   Osborne, Sims Hill; Bakita, Joshua; Chen, Jingyuan; Yandrofski, Tyler; Anderson, James H. (May 2022, Proceedings of the 28th IEEE Real-Time and Embedded Technology and Applications Symposium)
4. DAG-Structured Clustering by Nearest Neighbors

   Monath, Nicholas; Zaheer, Manzil; Dubey, Kumar Avinava; Ahmed, Amr; McCallum, Andrew (January 2021, Proceedings of The 24th International Conference on Artificial Intelligence and Statistics)

   null (Ed.)

   Hierarchical clusterings compactly encode multiple granularities of clusters within a tree structure. Hierarchies, by definition, fail to capture different flat partitions that are not subsumed in one another. In this paper, we advocate for an alternative structure for representing multiple clusterings, a directed acyclic graph (DAG). By allowing nodes to have multiple parents, DAG structures are not only more flexible than trees, but also allow for points to be members of multiple clusters. We describe a scalable algorithm, Llama, which simply merges nearest neighbor substructures to form a DAG structure. Llama discovers structures that are more accurate than state-of-the-art tree-based techniques while remaining scalable to large-scale clustering benchmarks. Additionally, we support the proposed algorithm with theoretical guarantees on separated data, including types of data that cannot be correctly clustered by tree-based algorithms. 

   more » « less
5. Feasibility Analysis of Conditional DAG Tasks

   https://doi.org/10.4230/LIPIcs.ECRTS.2021.12  

   Baruah, Baruah; Marchetti-Spaccamela, Alberto (July 2021, Proceedings of the EuroMicro Conference on Real-Time Systems (ECRTS 2021).)

   null (Ed.)