This is an old revision of the document!
Ongoing projects
Leadership Election Among Numbered Agents with Constrained Interactions
Student: Stephen Voland
Supervisor: Patrick Dymond and Michael Jenkin
Description
This project is an examination of the efficiency with which numbered distributed agents are able to elect a leader, given certain constraints. It builds on the paper 'Efficient Leader Election Among Numbered Agents', by R. Chaturvedi, P. Dymond, and M. Jenkin.
When collections of agents are deployed to solve a problem it can be beneficial to establish a leader among the group. For certain applications it may be desirable to establish this leader in some static manner. For other situations it is desirable to have the group of agents establish the leader themselves. Chatuervedi et al. (2011) developed an algorithm that enables a group of identical agents differentiated only by their unique identification number to elect their own leader. Chaturvedi et al.'s work contained a very simple simulator for a specific algorithm. Ongoing work requires the development of a more sophisticated simulator of this collection of agents, in particular the development of a simulator that allows for systematic evaluation of certain properties of the collection of agents. It is also desirable to perform a rigorous mathematical analysis of some of the more simpler variants of the existing work.
The project will involve the creation of a simulator which will take parameters for the number of agents, their internal initial state such as arrangement in space, and a function to determine the probability of an interaction between two given agents based on their positions. In the most straightforward case, all paired interactions would be equally likely, and thus the agents would have no associated positions. Another case would have the agents spread randomly on a bounded plane, where the probability of a pair interacting would be inversely proportional to the distance between them. A third would have the agents distributed among rooms, and would allow an agent to communicate only with agents in the same or an adjacent room. The program will simulate a leadership election using the supplied parameters, and report properties of the simulation including how many interactions were necessary to complete the election, if the election was successful, and actual number of interactions taken for election
Theoretical results for such elections will also be determined, and will be compared with the experimental results for mutual validation.
Implementation and Analysis of a Non-blocking Chromatic Search Tree
Student: Trevor Brown
Supervisor: Eric Ruppert
Description
This project seeks to take the theoretical description of the non-blocking chromatic search tree that was developed in a previous CSE4080 project and produce a Java implementation, then perform experiments to test it and compare it with other leading concurrent dictionary structures.
Additionally, many potential performance improvements and structural or algorithmic variations on the aforementioned theoretical description were identified during the last project. This project would attempt to explore many of these variations to further refine the theoretical description, and produce a competitive dictionary algorithm. In particular, this project would provide a dictionary implementation with better worst-case performance guarantees than previous non-blocking dictionary implementations.
Finally, the project would attempt to establish formal proofs that the structure provides guarantees regarding balance and worst-case performance. If time permits, further work will be done towards establishing the correctness of the algorithm.
UCOSP: Development for Encyclopedia of Life
Student: Feng Sun
Supervisor: Vassilios Tzerpos
Description
The Encyclopedia of Life (EOL) is a free, online collaborative encyclopedia intended to document all of the 1.8 million living species known to science. It is compiled from existing databases and from contributions by experts and non-experts throughout the world.
The ultimate criteria of success for a web application is the user experience. EOL is no exception. This project involves creating a framework for describing how visitors are supposed to interact with Encyclopedia of Life. It automatically checks that a new version the EOL code is functioning as expected. It is very beneficial for open source projects to be released often, and automated tests decrease the cost of releases dramatically and ensure the integrity of the data, code, and visual representation. The tests are run either in production or a duplicate of the production environment. The acceptance testing framework can be extended to check any website, not only EOL, by changing the configuration and defining new test suites. It also enables testing a web application with different browsers and operating systems.
Acceptance testing is an import skill for aspiring developers. By participating in this project you will learn the inner mechanics of operating a browser automatically using scripts, emulating a real person's actions. This project will provide experience using Selenium (a leading open source acceptance testing tool), XML, XPATH, CSS selectors, and Behavior Driven Development.
More information: http://www.eol.org