Simulation Frameworks for the Teaching and Learning of Distributed Algorithms

Abstract

Teaching and learning about distributed algorithms is difficult. This is because distributed algorithms are made up of multiple independent elements, each with their own state and control, who interact through the exchange of messages. Such a configuration results in a large amount of data which describes not only the local state information of each element within the distributed algorithm but also, their complex interactions. Thus, the use of traditional teaching methodologies, for example pseudo code descriptions, execution traces, chalk and talk do not lend themselves well to the easy disclosure of material which is highly concurrent in nature and which may suffer from partial failure that is, the loss or failure of one or more of its elements.

Consequently, animation was put forward as one means of capturing the temporal evolution of a distributed algorithm?s behaviour. However, creating an animation for each and every distributed algorithm that an instructor wishes to teach is a very time consuming process and one which instructors cannot readily commit to due to time constraints. Moreover, educational researchers have questioned the educational value of such systems as they may not engage learners in the high order thinking skills of analysis, synthesis and evaluation. As a result of this, researchers within the field of algorithm animation have looked for ways to expand the `communicative expressiveness of algorithm animation systems? by building algorithm simulation systems. These are systems which allow a learner to interact with, manipulate or change the behaviour of an algorithm while it executes by, for example, changing the state of its variables or by causing a message to fail.

However, like algorithm animation systems, building algorithm simulation systems is a very time consuming and difficult process as, not only, must an instructor implement the logic of the distributed algorithm that he is intending to animate but he must also define how it is to be animated. Moreover, he must define which components of an algorithm?s process that a learner can interact with, modify or change as it executes. Thus, researchers within the field of algorithm animation have looked for ways to combat the problem of building algorithm simulations by reanalyzing the educational benefit of algorithm animation systems. Informed by findings from constructionist educationalists, which show that learners who generate their own representations of an entity have a deeper understanding of that entity and better recall abilities than those who do not, researchers have developed systems to facilitate the easy creation of algorithm animations.

Drawing upon practices within software engineering of developing a framework whenever several or (partly) similar applications within a particular domain need to be developed, researchers have developed animation frameworks, which a learner can use to define the behaviour of an algorithm. These frameworks provide a set of prefabricated software building blocks that a learner can use to customise or build his own animation of an algorithm?s behaviour. However, whilst these systems allow a learner to construct an animation of a distributed algorithm?s behaviour in a timely manner, they do not allow him to exercise his higher order thinking skills by enabling him to manipulate the algorithm as it evolves.

Thus, informed by the strengths of algorithm simulation systems and algorithm construction systems, this thesis presents a simulation framework named FADA for the teaching and learning of distributed algorithms. The engagement model of FADA is that of a highly interactive simulation. Its underlying pedagogy is based on theories of constructionism and social constructivism. The design is also informed by the theories of dual coding and epistemic fidelity. Simulations are written in a conventional programming language, in this case JAVA, with a wrapper class making transparent calls to the underlying visualization API. The development environment contains an editor, a wizard and a debugger as typified by modern programming environments. To overcome the cost, in terms of development time, for creating new simulations, a framework for common message passing algorithms has been developed. Of particular note is that this framework also acts as a basis for scaffolding learners in the process of constructing their own simulations, a? la the theory of constructionism.

As a consequence of its design, FADA can be attributed two modes of use. It can be used by instructors and learners as an interactive presentation tool. FADA provides an instructor or learner with a collection of pre-canned simulations that he can use to present to a class for discussion, exploration and feedback. The latter is informed by theory of social constructivism. FADA can also be used as a tool to allow instructors and learners to create their own simulations of an algorithm?s behaviour. These can then be added to the aforementioned collection of simulations provided by FADA in order to create a repository of algorithm simulations.

A number of exploratory case studies were carried to investigate both the pedagogical and operational effectiveness of FADA. The aim of the case studies was twofold; to investigate to what extent the ability to view an algorithm?s behaviour, interact with its behaviour in real time, customize or build its implementation facilitates learners in acquiring a deep understanding of its process and facilitates instructors in their teachings. From a pedagogical perspective, results suggest that learners engage with and are motivated by such systems and as a consequence, are challenged to test their understanding of an algorithm?s behaviour in a deep way. Equally, results suggest that instructors find such systems an effective, intuitive and concrete means by which to demonstrate and convey the dynamic and concurrent behaviour of an algorithm. From an operational perspective, results suggest that instructors find such systems easy to use and assist them in creating active simulations for use in their own teachings in a timely and efficient manner. In summary the main contributions of this research are:

The development of an algorithm animation system that engages learners in higher order thinking with an algorithm?s behaviour.

The development of a novel framework to facilitate the easy and quick creation of an active algorithm simulation.

Results from exploratory case studies as to the effectiveness of active simulation systems in engaging and motivating learners to experiment with their understanding of an algorithm?s behaviour in a deep manner.