Randomized Algorithms
Applications of Probabilistic Concepts -- the Aggie connection
The application of probabilistic concepts in computer science is
something that might happen right next door. The following references
should give you an idea what is going on in Aggieland. It is needless
to say that this list is incomplete. Hopefully, you will contribute
soon!
- N.M. Amato, M.T. Goodrich, and E.A. Ramos, Linear time triangulation of a simple polygon made easier via randomization, Proceedings of the 16th Annual ACM Symposium on Computational Geometry (SoCG'00), pp. 201-212, 2000.
- N.M. Amato, M.T. Goodrich, and E.A. Ramos, Computing Faces in Segment and Simplex Arrangements, Proceedings of the 26th ACM Symposium on Theory of Computing (STOC), 1995, pp. 672-682.
- L. Cai, J. Chen, and J. Hastad, Circuit bottom fan-in and computational power, SIAM Journal on Computing 27, pp. 341-355, 1998.
- J. Chen, J., I.A. Kanj, and G. Wang, Hypercube network fault
tolerance: a probabilistic approach, Proc. 2002 International
Conference on Parallel Processing (ICPP'02), pp. 65-72, 2002.
- B.A. Coan and J.L. Welch, Transaction Commit in a Realistic Timing
Model, Distributed Computing, Vol. 4, No. 2, pp. 87-103, 1990.
- S. Dolev, E. Schiller, and J.L. Welch, J. L., Random Walk for
Self-Stabilizing Group Communication in Ad-Hoc Networks, Proc.
21st Symposium on Reliable Distributed Systems, Oct 2002.
- S. Dolev and J.L. Welch, Self-Stabilizing Clock Synchronization in
the Presence of Byzantine Faults, 2nd Workshop on Self-Stabilizing
Systems, May 1995.
- Y. Guan, X. Fu, R. Bettati, and W. Zhao, An Optimal Strategy for Anonymous Communication Protocols,
Proceedings of the 22th International Conference on Distributed Computing Systems, Vienna, Austria, July 2002.
- Y. Guan, X. Fu, D. Xuan, P.U. Shenoy, R. Bettati, and W. Zhao,
NetCamo: camouflaging network traffic for QoS-guaranteed mission critical applications, IEEE Transactions on Systems, Man, and Cybernetics, Vol 31, No. 4, July 2001, pp. 253 - 265.
- M.R. Hribar, V.E. Taylor, D.E. Boyce, Implementing parallel
shortest path for parallel transportation applications, Parallel
Computing, 31, pp. 1537-1568, 2001
- H. Lee and J.L. Welch, Randomized Shared Queues Applied to
Distributed Optimization Algorithms, Proc. 12th International
Symposium on Algorithms and Computation (ISAAC), December 2001.
- H. Lee and J.L. Welch, Applications of probabilistic quorums to
iterative algorithms, Proc. 21st IEEE International Conference on
Distributed Computing Systems (ICDCS), pp. 21-30, April 2001.
- D. Leonard, V. Rai, D. Loguinov, On Lifetime-Based Node Failure and Stochastic Resilience of Decentralized
Peer-to-Peer Networks, ACM Sigmetrics, 2005
- V.E. Taylor, R.L. Stevens, K.E. Arnold, Parallel molecular dynamics: Implications for massively parallel machines, J. Parallel and Distributed Computing, 45, pp. 166-175, 1997
- S. Voorhies, H. Lee, and A. Klappenecker,
Randomized caching, probabilistic queuing, and denial of service attacks, preprint, 2003.
X. Wang, Y. Zhang, X. Li, and D. Loguinov, On
Zone-Balancing of Peer-to-Peer Networks: Analysis of Random Node Join, ACM Sigmetrics, 2004.