Xing Shi's Home Page

Research Interest

Probabilistic Combinatorics. Random graphs. P2P networks.



X. S. Cai and L. Devroye. The graph structure of a deterministic automaton chosen at random: full version. arXiv preprint arXiv:arXiv:1504.06238, 2015. URL


X. S. Cai and L. Devroye. The analysis of kademlia for random ids. arXiv preprint arXiv:1402.1191, 2014. URL (Accepted by Internet Mathematics.)

X. S. Cai, G. Perarnau, B. Reed, and A. B. Watts. Acyclic edge colourings of graphs with large girth. arXiv preprint arXiv:1411.3047, 2014. URL


X. S. Cai and L. Devroye. A probabilistic analysis of kademlia networks. In Algorithms and Computation, volume 8283 of Lecture Notes in Computer Science, 711–721. Springer Berlin Heidelberg, 2013. URL .

Master's Thesis

A probabilistic analysis of Kademlia.