Personal Information Current Teaching Current Projects Past Projects Publications Grants Past Teaching Students Dal FCS Dal

Personal Information

  • Position: Instructor
  • Office: 208 Goldberg Building, 6050 University Ave, Halifax, NS, CANADA, B3H 1W5
  • Institution: Faculty of Computer Science, Dalhousie University
  • Phone: 902-494-2501
  • Fax: 902-492-1517
  • Teaching Interests:
    • Data Structures and Algorithms
    • Distributed Computing and Systems
    • Operating Systems
    • Foundations of Computer Science
    • Computer Organization and related topics
  • Research Interests:
    • Distributed Computing and Distributed Systems
    • Discrete Mathematics
    • Operating Systems and related topics
    • Computational Complexity
    • Formal Languages
    • Quantum Computation
  • Curriculum Vitae
  • Email:

Current Teaching

I am teaching the following courses in 2014/2015

Current Projects

 I am presently involved in three projects:

Distributed Content-Independent Classification of Spam

The amount of spam has skyrocketed in the past few years. Traditionally, spam was sent by single source mass mailers (spammers), making it relatively easy to screen out through the use of blacklists. Today many spammers use bot-nets to send out the spam, rendering the blacklists ineffective. Unfortunately, content-based spam filters provide only temporary relief, resulting in a never-ending cat-and-mouse game between spammers and filter developers.

Over the past couple years two undergraduate students at the University of Winnipeg: Scott Lindenberg and Thomas Redekopp, and I have been designing and implementing Trinity, a distributed, content-independent spam classification system that is specifically aimed at bot-net generated spam. Trinity is specifically designed to be used within the existing e-mail infrastructure, complementing existing spam classifiers. It does not require special hardware, changes to the underlying protocols, or changes to the mail transfer agents.

Trinity uses source identification in combination with a peer-to-peer based distributed database to collaboratively identify e-mails that are likely to have originated from bot-nets. Due to its distributed nature, the system is tolerant of failed or malicious peers and can tolerate denial-of-service attacks from the very same bot-nets that produce spam.

The Role of Synchrony in Shared-Memory Systems

I am investigating how synchrony in shared-memory systems can be leveraged to yield efficient distributed algorithms. Most algorithms for solving problems in a distributed fashion do not make any assumption about how synchronized the components of the underlying distributed system are. While such assumptions allow for very general design methodologies, they ignore a useful attribute of most distributed systems---namely, that the components of many distributed systems are comparatively synchronized.

I am interested in determining the types of synchrony present in distributed systems, identifying the forms that are most useful, designing distributed algorithms that can leverage these forms of synchrony. This investigation seeks to expand our understanding of the foundations of computer science and improve our ability to design more efficient and robust distributed systems.

Safe Resource Allocation in Parallel Systems

The correctness of parallel applications that perform asynchronous message passing typically relies on the underlying system having sufficient resources, such as memory for message buffers, to process undelivered messages. If such applications are executed on systems that lack sufficient resources, the applications may deadlock, wasting computation time and resources.

In collaboration with Dr. Pedersen of the University of Nevada, Las Vegas, I am investigating algorithms for determining optimal deadlock-free resource allocations for parallel applications. Specifically, we are focusing on memory resources (buffers) used for storing undelivered messages. We have shown that determining a deadlock-free optimal buffer allocations for a given application is computationally intractable, necessitating the use of approximation techniques. We are investigating approximation techniques for determining near-optimal deadlock-free buffer allocations.

Past Projects

My post-doctoral work was in the area of distributed computing. My supervisor and I investigated the implementation and complexity of synchronous shared-memory objects. We derived several efficient wait-free implementations of snapshot objects that used only shared atomic registers and showed that these implementations were optimal. We also investigated various wait-free implementations of synchronous long-lived renaming objects that used shared atomic registers and counters.

My doctoral dissertation comprises three parts. First, I investigated growth processes on formulas, generalizing a result of Valiant (1984) and developed a general framework for analyzing such processes. Second, I investigated growth processes on reversible circuits and characterized almost all such growth processes. Third, I investigated the reversible circuit complexity of finite Boolean functions and characterized families of Boolean functions that could realized by polynomial-size reversible circuits. The thesis is titled Growth Processes on Formulas and Reversible Circuits .

My masters research involved defining and characterizing various models of quantum finite automata. These are some of the simplest models of quantum computation possible and provide insights into more complex models of quantum computation. My masters thesis is titled Models and Characterizations of 1-Way Quantum Finite Automata .

Publications

Journal Publications

Conference and Workshop Publications

Manuscripts in Preparation or Submission

  • Alex Brodsky and Faith Ellen, "Efficient Synchronous Snapshots", article in preparation.

Tech Reports

Grants

The majority of this research has been funded by NSERC, including a Discovery Grant, a Post Doctoral Fellowship, and a Post-Graduate Scholarship.

  • NSERC Discovery Grant, $14,000 per annum, 2006 - 2009
  • NSERC Post Doctoral Fellowship, $40,000 per annum, 2003 - 2005
  • University Graduate Killam Fellowship, $23,000 per annum, 1999 - 2003
  • NSERC Post Graduate Scholarship, $19,000 per annum, 1999 - 2001

Past Teaching

2013/2014
  • CSCI 3136: Principles of Programming Languages
  • CSCI 3120: Operating Systems
  • CSCI 1106: Animated Computing
  • CSCI 4176: Mobile Computing
2012/2013
  • CSCI 3132: Object Oriented Programming
  • CSCI 4176: Mobile Computing
2011/2012
  • CSCI 2110: Computer Science III
  • CSCI 3120: Operating Systems
  • CSCI 3132: Object Oriented Programming
  • CSCI 4176: Mobile Computing
2010/2011
  • CSCI 1106: Animated Computing
  • CSCI 3120: Operating Systems
  • CSCI 4176: Mobile Computing
2009/2010
  • CSCI 1106: Animated Computing
  • CSCI 1107: Social Computing
  • CSCI 2132: Software Development
  • CSCI 3120: Operating Systems
University of Winnipeg (pre 2009)

Here is a statement of my teaching philosophy.

Students

I have supervised the following students:

  • Diana Paterson, Ph.D., 2013 - present, Dalhousie University
  • Haifng Ye, MEC, 2012, Dalhousie University
  • Joseph Howse, M.Sc. 2011 - 2012, Dalhousie University
  • Scott Lindenberg, 2007 - 2008, University of Winnipeg
  • Thomas Redekopp, 2007 (NSERC USRA), University of Winnipeg