DAJ: Distributed Algorithms in Java

Overview

DAJ is an interactive, visual aid for studying distributed algorithms. Interactive, because you must explicitly specify every step of the interleaved execution sequence. Visual, because the state of the nodes is continuously displayed. Study aid, because they solve one of the most difficult problems encountered by students of these algorithms by automatically doing the necessary book-keeping. The program can create a log file of commands so that you can automatically replay scenarios until you understand them. Fourteen algorithms are current implemented, and you can implement other algorithms with only an elementary knowledge of Java. Visualizations are included for the virtual global structures contructed by some of the algorithms.

Algorithms implemented

  1. Byzantine generals algorithm for consensus (byzantine failures).
  2. Byzantine generals algorithm for consensus (crash failures).
  3. Byzantine generals algorithm for consensus by Berman and Garay (Algorithm 5.2 of Attiya and Welch).
  4. EIGStop algorithm for consensus (Section 6.2.3 of Lynch).
  5. Ricart-Agrawala algorithm for mutual exclusion.
  6. Suzuki-Kasami algorithm for mutual exclusion.
  7. Neilsen-Mizuno algorithm for mutual exclusion.
  8. Lamport algorithm for mutual exclusion.
  9. Maekawa algorithm for mutual exclusion.
  10. Carvalho-Roucairol algorithm for mutual exclusion.
  11. Dijkstra-Scholten algorithm for detecting termination.
  12. Chandy-Lamport algorithm for global snapshots.
  13. Huang algorithm for termination detection.
  14. Mattern algorithm for termination detection.

References

  • M. Ben-Ari. Interactive Execution of Distributed Algorithms. ACM Journal of Educational Resources in Computing 1(2), 2001.
  • A. Tikvati, M. Ben-Ari, Y. Ben-David Kolikant. Virtual trees for the Byzantine Generals algorithm. Thirty-Fifth SIGCSE Technical Symposium on Computer Science Education. Norfolk, VA, 2004.
  • H. Attiya and J. Welch. Distributed Computing. McGraw-Hill, 1998.
  • N. Lynch. Distributed Algorithms. Morgan Kaufman, 1996.

Download

Download from GitHub: https://github.com/motib/daj.

Acknowledgments

I wish to thank Judith Bishop of the University of Pretoria for her pioneering use of this software in her classes. University of Pretoria students Richard McGladdery, Frederick Kemp, Frank Harvie, Derick Burger, Darrell Newing and Leoni Lubbinge wrote several of the algorithms, which were adapted to version 2 by Basil Worrall. Basil also found some bugs in version 3. The virtual trees for the Byzantine Generals algorithm were designed by Ahuva Tikvati of the Weizmann Institute of Science and programmed by Antoine Pineau of the University of Joensuu. The visualization of the spanning tree of the Dijkstra-Scholten algorithm is based upon a program by Maor Zamsky. Otto Seppälä and Ville Karavirta of the Helsinki University of Technology implemented new algorithms.