Selected (Mostly Recent) Publications

Research Overview

This gives a short overview of my research since 1991. The main areas cover Algorithms for Computer Networks, Computer Security, Graph algorithms, Network Flow (and applications), Parallel/Distributed algorithms, Search algorithms, and Hardware Design algorithms. Below I briefly summarize some of the main results in each area and then list publications by area.

Algorithms for Computer Networks

We consider a range of problems in this area including routing algorithms, network design, quality of service issues, efficient allocation of backup paths, and finding multiple paths of similar length. We also develop algorithms to check network security algorithms (using IPsec tunnels) for possible conflicts, and consider automatic generation of correct security policies.
  1. [N1] C. Vadrevu, R. Wang, M. Tornatore, C. Martel, and B. Mukherjee, Degraded Service Provisioning in Mixed-Line-Rate WDM Backbone Networks Using Multipath Routing, IEEE/ACM Transactions on Networking, to appear.
  2. [N2] N.Bao, M. Habib, M. Tornatore, C. Martel, B. Mukherjee, Global Versus Essential Post-Disaster Re-Provisioning in Telecom Mesh Networks, Journal of Optical Communications and Networking, vol. 7, no. 5, pp. 392-400, 2015.
  3. [N3] D. Andrei, M. Batayneh, M. Tornatore, C. Martel, and B. Mukherjee, Provisioning of Deadline-Driven Requests with Flexible Transmission Rates in WDM Mesh Networks IEEE/ACM Transactions on Networking, vol. 18, no. 2, pp. 353-366, Feb. 2010.
  4. [N4] M. Xia, M. Tornatore, C. Martel, and B. Mukherjee, Risk-Aware Provisioning for Optical WDM Mesh Networks, IEEE/ACM Transactions on Networking, vol. 19, no. 3, pp. 921-931, June 2011. 5. S. Huang, M. Xia, C. Martel, and B. Mukherjee, A Multistate Multipath Provisioning Scheme for Differentiated Failures in Telecom Mesh Networks, IEEE/OSA Journal of Lightwave Technology, vol. 28, no. 11, pp. 1585-1596, June 2010.
  5. [N5] Andrei, D. Tornatore, M. Ghosal, D. Martel, C.U. Mukherjee, B. On-Demand Provisioning of Data-Aggregation Sessions over WDM Optical Networks, In Journal of Lightwave Technology, vol. 27, no. 12, pp. 1846-1855, June 2009.
  6. [N6] D. Andrei, Hong-Hsu Yen, and M. Tornatore, C. Martel, B. Mukherjee. Integrated Provisioning of Sliding Scheduled Services over WDM Optical Networks. In Journal of Optical Communications and Networking, vol. 1, no. 2, pp. A94-A105, July 2009.
  7. [N7] M. Xia, M. Tornatore, C. Martel, and B. Mukherjee. Risk-Aware Routing for Optical Transport Networks, To appear in InfoCom 2010.
  9. [N9] Andrei, D. Tornatore, M. Ghosal, D. Martel, C.U. Mukherjee, B. On-Demand Provisioning of Data-Aggregation Requests over WDM Mesh Networks. In IEEE Globecom, , Dec 2008. page(s): 1-5. (best paper award: 1%)
  11. [N11] Ming Xia Batayneh, M. Lei Song Martel, C.U. Mukherjee, B. SLA-Aware Provisioning for Revenue Maximization in Telecom Mesh Networks. In: Global Telecommunications Conference, 2008. IEEE GLOBECOM 2008. Nov. 30 2008-Dec. 4 2008 page(s): 1-5 (37%)
  12. [N12] Ananya Das, Charles Martel, Biswanath Mukherjee, and Smita Rai. A Better Approach to Reliable Multi-Path Provisioning. In the 2007 GLOBECOM proceedings, pp. 2724-2728.
    Full, pdf
  13. [N13] Smita Rai, Omkar Deshpande, Canhui (Sam) Ou, Charles U. Martel, and Biswanath Mukherjee Reliable Multi-Path Provisioning for High-Capacity Backbone Mesh Network IEEE/ACM Transactions on Networking, 2007, Vol 15, No 4, pp. 803-812.
  14. [N14] Yanyan Yang, C. Martel, S. F. Wu. CLID: A general approach to validate security policies in a dynamic network, 10th IFIP/IEEE International Symposium on Integrated Network Management (IM 2007, Munich, Germany, May 2007
    CLID, pdf
  15. [N15] Y. Yang, C. Martel, Z. Fu, S. F. Wu. IPSec/VPN security policy correctness and assurance. Journal of High Speed Networks, vol. 15, no. 3, pp. 275-289, 2006.
  16. [N16] V. Nguyen and C. Martel. Designing Low Cost Networks with Short Routes and Low Congestion. in proceedings of the 25th IEEE INFOCOM, April 2006.
  17. [N17] C. Ou, K. Zhu, C. Martel, B. Mukherjee,. Survivable virtual concatenation for data over SONET/SDH in optical transport networks. IEEE/ACM Transactions on Networking, vol. 14, pp. 218-231, Feb., 2006.

    Authentic Publication

    We present an approach to reduce the trust required of publishers of online databases. We do this by separating the roles of owner and publisher. The owner provides only a few digital signatures to the clients. An untrusted publisher can now provide small Verification Objects that establish the authenticity and non-repudiation of answers to a database query. In [AP4] we define the basic model for Authentic Publication, show how to deal with a variety of relational database queries, and prove the security of our approach. [AP3] extends our work to XML databases, while [AP2] shows how to convert almost any data structure into an efficient authenticated version. Finally, [AP1] shows how a collection of owners can efficiently authenticate a database which combines their values into a single database. This allows users and owners to trust the results of queries on this joint database. More details and copies of the papers can be found at:
  18. the Truthsayer project
    1. [AP1] G. Nuckolls, C. Martel, and S. G. Stubblebine. Certifying data from multiple sources. Proceedings of the 17th Database Security Conference, 2003. In S. De Capitani di Vimercati et al. editors, Data and Applications Security XVII: Status and Prospects, Kluwer Academic Publishers, 2004, pp 47--60.
    2. [AP2] C. Martel, G. Nuckolls, P. Devanbu, M. Gertz, A. Kwong, and S. G. Stubblebine. A General model for authenticated data structures, Algorithmica 39:21-41 (2004).
    3. [AP3] P. Devanbu, M. Gertz, A. Kwong, C. Martel, G. Nuckolls, and S. G. Stubblebine. Flexible Authentication of XML documents. In the 8th ACM Conference on Computer and Communications Security, pp. 136-145, 2001. An expanded version will appear in Journal of Computer Security.
    4. [AP4] P. Devanbu, M. Gertz, C. Martel and S. Stubblebine. Authentic third party data publication. In Proceedings of the 14th Database Security Conference, pp. 159-170, August 2000. Also, ln Journal of Computer Security, Volume 3, number 11, 2003, pages 291-314, (titled: Authentic Publication Over the Internet).

    Graph Algorithms (with Small Worlds)

    In two recent papers we analyze the expected diameter of small-world graphs based on a model developed by Kleinberg. In [G1] we showed that Kleinberg's basic model has expected diameter O(log n) and we suggested improved routing algorithms to come closer to this bound. In [G0] we extended these results to analyze a broader range of small-world graphs. Both papers develop some new techniques for analyzing random graphs with non-uniform random arcs. In [G4] we describe and analyze an improved algorithm to increase the connectivity of a graph: given an undirected graph G and a target f, the algorithm finds the smallest set of edges which when added make the network resistant to up to f edge failures. This led to several followup papers which built on our results. In [G5] we study the structure of hamilton cycles in random graphs and suggest a strategy for solving this difficult problem on most such graphs.
    1. [GA] V. Nguyen and C. Martel. AUGMENTED GRAPH MODELS FOR SMALL-WORLD ANALYSIS WITH GEOGRAPHICAL FACTORS. In the Workshop on Analytic Algorithmics and Combinatorics (ANALCO08), pp. 213-227 (35%)
    2. [GB] A. Das, C. Martel, Stochastic Shortest Path with Unlimited Hops. In Information Processing Letters, Vol. 109, no. 5, Feb. 2009, pages 290-295.
    3. [G0] V. Nguyen and C. Martel. Analyzing and characterizing small-world graphs. To appear in the 2005 ACM-SIAM symposium on Discrete Algorithms.
      SODA version, pdf
      full version, pdf
    4. [G1] C. Martel and V. Nguyen. Analyzing Kleinberg's (and other) small-world models. In the 23rd ACM Symposium on Principles of Distributed Computing, pp. 179-188, 2004.
      pdf version
    5. [G2] C. Martel. The expected complexity of Prim's minimum spanning tree algorithm. In Information Processing Letters, vol. 81, pp. 197-201. 2002.
    6. [G3] J. Black, C. Martel, H. Qi. Graph and hashing algorithms for modern architectures: design and performance. In the 1998 Workshop on Algorithm Engineering, pp. 37-48, Saarbrucken, Germany, August 1998.
    7. [G4] D. Naor, D. Gusfield, and C. Martel. A fast algorithm for optimally increasing the edge connectivity. SIAM Journal on Computing , pp. 1139-1165, vol. 26, 4, 1997.
    8. [G5] J. Frank, C. Martel. Phase transitions in the properties of random graphs. In the Proceedings of the CP95 Workshop on Studying and Solving Really Hard problems, pp. 62-69 France, September, 1995.

    Distributed and Parallel Algorithms

    Asynchronous PRAMs

    In a PRAM all processors are assumed to work synchronously and never fail. These two assumptions make it much easier to design correct and efficient programs, but they are difficult to implement on real machines. Thus, we developed a new parallel model,the A-PRAM, to overcome these limitations. The A-PRAM is an asynchronous version of the PRAM, which also allows fail-stop errors by the processors. This new model and the style of analysis which we developed has led to a number of new and important results by my group and others.
    The founding paper which defines the model formally, [APRAM3], was published in SIAM Journal on Computing. %one of the two most prestigious journals for theoretical work, This paper also defines a metric for evaluating A-PRAM performance and shows that several fundamental problems for load balancing and synchronization can be solved efficiently. Additional work in this area builds on this paper. The most important technical result is a general synchronization primitive which allowed us to synchronize n tasks using up to n/(lognlog* n) processors and O(n) expected work. This synchronization primitive enabled us to automatically translate any oblivious PRAM program into an A-PRAM program which uses the same expected work as the original PRAM program. In [APRAM1] we improved our synchronization primitive to use up to n/(log n) processors, and we proved that this new solution was optimal.
    Our prior papers use some sort of extra hardware (such as a compare and swap instruction) as part of the translation schemes. However, in [APRAM4] we extended our work to show that if you are willing to use extra space it is possible to do a very general translation even if only atomic reads and writes are used. Earlier papers assumed that reads and writes to the global memory occur with minimal delay. This (unrealistic) assumption is relaxed in [APRAM2] where we show that similar results on translating PRAM programs to asynchronous machines still apply even if the target machine has significant latencies for accessing global memory.
    1. [APRAM1] C.U. Martel and R. Subramonian. On the complexity of certified write-all algorithms. In the 12th Conference on Foundations of Software Technology and Theoretical Computer Science, New Delhi, India, December 1992. Also, in the Journal of Algorithms, vol. 16, pp. 361-387, 1994.
    2. [APRAM2] C.U. Martel and A. Raghunathan, Asynchronous PRAMs with memory latency. In the Journal of Parallel and Distributed Computing, vol. 23, pp. 10-26, 1994.
    3. [APRAM3] C.U. Martel, A. Park, and R. Subramonian. Work optimal asynchronous algorithms for shared memory parallel computers. SIAM Journal on Computing, vol. 21, pp. 1070-1099, 1992.
    4. [APRAM4] J. Becker, C. Martel, and A. Park. General asynchrony is not expensive for PRAMs. In the proceedings of the 1991 International Parallel Processing Symposium, pp. 70-75.

    Multiple Access Broadcast Networks

    We investigated several fundamental problems for Multiple-access broadcast networks (such as Ethernets) which are in wide use. In the prioritized conflict resolution problem, each node has a priority, and we want the nodes involved in a conflict to transmit in order of their priority. In [M9] we developed an algorithm to minimize the expected delay for each node to transmit, and we proved that the expected delay achieved by our algorithm is optimal. This result requires a static set of nodes, so, in [M7,M2] we extended this result to allow new arrivals to also participate in the prioritized conflict resolution algorithm. In [M6, M3] we give a faster algorithm for prioritized conflict resolution when information can be transmitted using mini-slots. Since there are practical settings where this type of mini-slots can be used, this can be a useful improvement. Maximum finding is a classical problem where each node on the network has an arbitrary value, and we want to quickly find the largest value. In [M8] we describe an algorithm which finds the maximum in O(log n) expected time on an n node network. This improves on prior results for this problem, and we prove that our algorithm is asymptotically optimal. Networks of Workstations (NOWs) are now frequently available and can potentially be exploited as a powerful parallel machine. In [M1] we develop a novel technique for developing parallel algorithms on NOWs by exploiting the broadcast capability available on many NOWs. Our innovation is to show that even if the broadcast is unreliable (you can't be sure everyone will receive it), it can still be used to speed up a number of algorithms.
    1. [M1] J. Matthews and C. Martel. Designing parallel algorithms using unreliable broadcast. In the 1996 International Parallel Processing Symposium. pp.692-696 Honolulu, April 1996.
    2. [M2] C.U. Martel, W. M. Moh, and T. Moh. Dynamic prioritized conflict resolution on a multiple access broadcast networks. IEEE Transactions on Computers, vol. 45, 9, pp. 1074-1079, 1996.
    3. [M3] W. M. Moh, Y. Chien, C.U. Martel and T. Moh. Prioritized conflict resolution on a multiple access broadcast channel using control mini-slots. In International Journal of Computer Systems Science and Engineering, vol. 10, 4, pp. 234-243, 1996.
    4. [M4] C. Martel and J. Matthews. Randomized algorithms for efficient load balancing and fault tolerance. In Proceedings of the 1995 ACM SIGMETRICS/PERFORMANCE '95 Joint International Conference on Measurement and Modeling of Computer Systems, pp. 60-61, Ottowa, Canada, May, 1995.
    5. [M5] W. M. Moh, C.U. Martel and T. Moh. Using Multiple Access Broadcast Network Algorithms for CRCW PRAM simulations. In Seventh IASTED/ISMM International Conference on Parallel and Distributed Computing and Systems, pp. 411-415, Washington D.C., Oct. 1995.
    6. [M6] W. M. Moh, Y. Chien, C.U. Martel and T. Moh. Prioritized conflict resolution on a multiple access broadcast channel using control mini-slots. In the Proceedings of the Seventh International Conference on Parallel and Distributed Computing Systems, pp. pp. 214-221, 1994.
    7. [M7] W. M. Moh, C.U. Martel and T. Moh. A dynamic solution to prioritized conflict resolution on a multiple access channel. In the 1993 International Conference on Parallel and Distributed Systems, pp. 414-418.
    8. [M8] C.U. Martel. Maximum finding on a multiple access broadcast network. In Information Processing Letters. Vol. pp. 7-13, 1994.
    9. [M9] C.U. Martel, and M. Moh. Optimal prioritized conflict resolution on a multiple access channel. In IEEE Transactions on Computers, Vol. 10, no. 10, 1991, pp. 1102-1108.

    Network Flow Algorithms/application

    In [N1,N2] we analyzed a classic setting where a set of teams have played part of a fixed schedule of head-to-head games, and we want to determine which teams still have a chance to win (or more generally, qualify for the next phase). We proved a general theorem which shows that for a broad class of settings there is a critical score such that any team with this score or higher is in contention, and those below are eliminated (this value depends on the current standings and remaining schedule). We discuss computing this value efficiently, and also showed several settings where computing this critical score is NP-hard. In [N3] we consider settings which can be solved by a sequence of closely related network flow computations. We extend earlier work by Gallo, Grigoriadis and Tarjan which required a sequential sequence of flows, to allow an irregular sequence which allows binary search. We then show several problems which can be solved more efficiently using our techniques.
    1. [N1] D. Gusfield and C. Martel. The structure and complexity of sports elimination numbers. In Algorithmica 32:73-86 (2002).
      pdf version
    2. [N2] D. Gusfield and C. Martel. Thresholds for sports elimination numbers: algorithms and complexity. In the Proceedings of the Sixth International Workshop on Algorithms and Data Structures, Vancouver, 1999.
    3. [N3] D. Gusfield and C.U. Martel. A fast algorithm for the generalized parametric minimum cut problem and applications", Algorithmica, Vol. 7, 1992, pp. 499-519.

    Self-adjusting Search Algorithms

    We considered new algorithms for fast search in lists and trees when the storage structure adapts to reflect the current access probabilities. A key result was a new technique which uses two extra bits per key to speed up unsuccessful search in a linear list. This led to deterministic algorithms that are 3-competitive for both successful and unsuccessful search [S4, S6], and we improved the (expected) competitive constant below 2.5 using randomization [S1,S5]. In [S2,S3] we extended this to handle deletions. In [S7] we developed a a self-adjusting multi-way search tree, which provides an efficient implementation of a weighted Dictionary in a virtual memory environment.
    1. [S0] E. Lee and C. Martel When to use Splay Trees. To appear in Software: Practice and Experience.
    2. [S1] L. Hui and C.U. Martel. Randomized Competitive Algorithms for Successful and Unsuccessful search. The Computer Journal, vol. 39, 5, 427-438, 1996.
    3. [S2] L. Hui and C.U. Martel. Analyzing self-adjusting linear list algorithms with deletions and unsuccessful searches. Information Processing Letters, vol. 58, 231-236, 1996.
    4. [S3] L. Hui and C.U. Martel. Analyzing deletions in self-adjusting linear list algorithms. In Proc. of the Fifth Annual International Symposium on Algorithms and Computation,, August 1994, Beijing, China. Ed. by Ding-Zhu Du and Xiang-Sun Zhang, pp. 433-441. Lecture Notes in Computer Science, 834, Springer-Verlag.
    5. [S4] L. Hui and C.U. Martel. Unsuccessful search in self-adjusting data structures. Journal of Algorithms, vol. 15, pp. 447-481, 1993.
    6. [S5] L. Hui and C.U. Martel. Randomized Competitive Algorithms for Successful and Unsuccessful Search on Self-adjusting Linear Lists, In the Fourth Annual International Symposium on Algorithms and Computation, pp. 426-435, Hong Kong, December 1993.
    7. [S6] L. Hui and C.U. Martel. On unsuccessful search. In proceedings of the 3rd SIAM conference on Discrete Algorithms, pp. 217-227, 1992.
    8. [S7] C.U. Martel. Self-adjusting multi-way search trees. Information Processing Letters, Vol. 38, 1991, pp 135-141.

    Hardware Design

    We developed new techniques to treat parallel multiplier design as a more global optimization problem, and this produced designs which may be 10-20\% faster than the best current multipliers. We proved several properties of the structure of optimal designs, and this allowed us to find optimal designs for up to 58 bit multiplication and good though not provably optimal designs for larger problems. This work led to some changes in the design of multipliers for special purpose processors.. My (former) Ph.D student Paul Stelling was also able to extend this work to broader classes of multipliers in several followup papers.
    1. [H1] C. Martel, P. Stelling, V. Oklobdzija, and R. Ravi. Design strategies for optimal multiplier circuits. IEEE Transactions on Computers, vol. 47, 3, pp. 273-285, 1998.
    2. [H2] C. Martel, V. Oklobdzija, R. Ravi, P. Stelling. Design strategies for optimal multiplier circuits. In Proceedings of the 12th IEEE Symposium on Computer Arithmetic. pp. 42-49, England, July 1995.