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 Role of Synchrony in Shared Memory Systems
- Safe Resource Allocation in Parallel Systems
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
- Jan Baekgaard Pedersen, Alex Brodsky, and Jeffery Samson,
"Approximating the Buffer Allocation Problem Using Epochs",
Journal of Parallel and Distributed Computing, 68, 1263-1282, 2008.
- Alex Brodsky and Shlomo Hoory,
"Simple Permutations Mix Even Better",
Random Structures and Algorithms, 32(3), 274-289, 2008.
- Alex Brodsky and Nicholas Pippenger,
"The Boolean Functions Computed by Random Boolean Formulas OR
How to Grow the Right Function",
Random Structures and Algorithms, 27(4), 490--519, 2005.
- Alex Brodsky, Jan Baekgaard Pedersen, and Alan Wagner,
"On the Complexity of Buffer Allocation in Message Passing Systems",
Journal of Parallel and Distributed Computing, 65(6), 692-713, 2005.
- Alex Brodsky,
"An Impossibility Gap Between Width-4 and Width-5 Permutation Branching
Programs",
Information Processing Letters, 94(4), 159-164, 2005.
- Alex Brodsky, Stephane Durocher, and Ellen Gethner,
"Toward the Rectilinear Crossing Number of Kn: New Drawings,
Upper Bounds, and Asymptotics", Journal of Discrete Math, 262, 2003.
- Alex Brodsky and Nicholas Pippenger,
"Characterizations of 1-Way Quantum Finite Automata", SIAM Journal
on Computing, 31(5), 1456-1478, 2002.
- Alex Brodsky, Stephane Durocher, and Ellen Gethner,
"The Rectilinear Crossing Number of K10 is 62",
The Electronic Journal of Combinatorics, 8(1), R23, 2001.
Conference and Workshop Publications
- Alex Brodsky and Scott Lindenberg,
"Our Brothers' Keepers: Secure Routing with High Performance",
Proceedings of the 10th International Symposium on Stabilization,
Safety, and Security of Distributed Systems", 2008.
- Alex Brodsky,
"Brief Announcement: Our Brothers' Keepers: Secure Routing with High
Performance", Proceedings of the 27th Symposium on Principles of
Distributed Computing, 2008.
- Alex Brodsky and Dmitry Brodsky,
"Brief Announcement: Trinity, A Distributed Defense Against Transient
Spam-bots", Proceedings of the 26th Symposium on Principles of
Distributed Computing, 2007.
- Alex Brodsky and Dmitry Brodsky,
"A Distributed Content Independent Method for Spam Detection",
Proceedings of the 1st USENIX Workshop on Hot Topics in Understanding
Botnets, 2007.
- Alex Brodsky, Faith Ellen Fich, and Philipp Woelfel,
"Fully-Adaptive Algorithms for Long-Lived Renaming",
Proceedings of the 20th International Symposium on Distributed Computing",
LNCS 4167, 413-427, 2006.
- Jan Baekgaard Pedersen and Alex Brodsky,
"Approximating the Buffer Allocation Problem Using Epochs",
Proceedings of the 18th IASTED International Conference on Parallel and
Distributed Computing and Systems, 50-59, 2006.
- Matei David, Alex Brodsky, and Faith Ellen Fich,
"Restricted Stack Implementations"
Proceedings of the 19th International Symposium on Distributed Computing",
LNCS 3724, 137-151, 2005.
- Alex Brodsky and Faith Ellen Fich,
"Efficient Synchronous Snapshots",
Proceedings of the 23rd Annual ACM Symposium on Principles of Distributed
Computing, 70-79, 2004.
- Alex Brodsky,
"Reversible Circuit Realizations of Boolean Functions",
Proceedings of the 3rd IFIP International Conference on Theoretical
Computer Science, 2004.
- Dmitry Brodsky, Alex Brodsky, Jody Pomkoski, Shihao Gong, Michael J.
Feeley, and Norman C. Hutchinson,
"Using File-Grain Connectivity to Implement a Peer-to-Peer File System",
Proc. of the 21st IEEE Symposium on Reliable Distributed Systems --
Workshop on Peer-to-peer Reliable Distributed Systems, 318-323, 2002.
- Dmitry Brodsky, Jody Pomkoski, Alex Brodsky, Michael J. Feeley,
Norman C. Hutchinson, "Exploiting Version Immutability to Simplify File
Replication", 18th ACM Symposium on Operating Systems Principles,
(poster), October, 2001.
- Alex Brodsky, Dmitry Brodsky, Ida Chan, Yvonne Coady, Stephan Gudmundson,
Jody Pomkoski, Joon Suan Ong,
"Coping with Evolution: Aspects vs Aspirin?". OOPSLA Workshop on
Advanced Separation of Concerns, October, 2001.
- Yvonne Coady, Alex Brodsky, Dmitry Brodsky, Jody Pomkoski,
Stephan Gudmundson, Joon Suan Ong, Gregor Kiczales,
"Can AOP Support Extensibility in Client-Server Architectures?"
ECOOP 2001 - Advanced Separation of Concerns Workshop, 2001.
Manuscripts in Preparation or Submission
- Alex Brodsky and Faith Ellen, "Efficient Synchronous Snapshots",
article in preparation.
Tech Reports
- Dmitry Brodsky, Alex Brodsky, Michael J. Feeley, Norman C. Hutchinson,
"Policy Driven Replication",
UBC Computer Science Technical Report, TR-2003-15, 2003.
- Dmitry Brodsky, Jody Pomkoski, Shihao Gong, Alex Brodsky,
Michael J. Feeley, Norman C. Hutchinson,
"Mammoth: A Peer-to-Peer File System",
UBC Computer Science Technical Report, TR-2003-11, 2002.
- Dmitry Brodsky, Jody Pomkoski, Michael J. Feeley, Norman C. Hutchinson,
Alex Brodsky,
"Loosely Coupled Optimistic Replication for Highly Available, Scalable
Storage"
UBC Computer Science Technical Report, TR-2001-14, 2001.
- Dmitry Brodsky, Jody Pomkoski, Michael J. Feeley, Norman C. Hutchinson
and Alex Brodsky,
"Using Versioning to Simplify the Implementation of a Highly-Available
File System",
UBC Computer Science Technical Report, TR-2001-07, 2001.
- Alex Brodsky, Dmitry Brodsky, Ida Chan, Yvonne Coady, Jody Pomkoski,
and Gregor Kiczales,
"Aspect-Oriented Incremental Customization of Middleware Services",
UBC Computer Science Technical Report, TR-2001-06, 2001.
- Alex Brodsky,
"Light, The Universe and Parallel Radiosity",
Edinburgh Parallel Computer Centre Technical Report,
EPCC-SS96-05, 1996.
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