My research interests include algorithms relating to communication and
routing problems in Parallel, Distributed and Mobile Computing
environments. In the Dynamic Data Distribution problem we design
algorithms for constructing communication substructures in a network
required for balancing push and pull activity so that global
communication is minimized. In the Compact Routing Problem we seek
tradeoffs between memory and stretch for compact routing with
topology-independent node names (both in directed and undirected
graphs). In the Hypercube Permutation Routing problem we minimize the
number of communication steps for parallel-routing an arbitrary
permutation in a hypercube. The Deadlock-Free Routing problem
requires that we minimize the number of buffers required per node to
ensure deadlock-freedom in arbitrary networks. In the Structural
Graceful Degradation problem we design interconnection structures that
exhibit structural properties of fault-tolerance and
graceful-degradation for pipeline networks. These problems are
presented more formally in the papers below.
Research Papers:
Compact Routing with
Name-Independence, by Marta Arias, Lenore J. Cowen, Kofi A. Laing,
Rajmohan Rajaraman, and Orjeta Taka. SIAM Journal on Discrete
Mathematics, Volume 20 Issue 3, pages 705--726 (2006). Online
at SIAM. Conference
Paper in Proceedings of the 15th Annual ACM Symposium on
Parallelism in Algorithms and Architectures (SPAA 2003). Pages
184-192. San Diego, California. SPAA'03 Talk
(PDF).
Compact Roundtrip
Routing with Topology-Independent Node Names, by Marta Arias,
Lenore J. Cowen and Kofi A. Laing. Journal of Computing and System
Sciences. Volume 74(5), Aug 2008, pages 775 -- 795. Conference Paper in
Proceedings of the 22nd Annual ACM Symposium on Principles of
Distributed Computing (PODC 2003). Pages 43-52. Boston,
Massachusetts.
Gracefully
Degradable Pipeline Networks, by Robert Cypher and Ambrose Laing.
Proceedings of the 11th International Parallel Processing Symposium
(IPPS'97). Pages 55-64. Geneva, Switzerland.