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.
Publications
- [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.
- [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.
- [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.
- [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.
- [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.
- [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.
- [N7] M. Xia, M. Tornatore, C. Martel, and B. Mukherjee.
Risk-Aware Routing for Optical Transport Networks, To appear in InfoCom 2010.
- [N8] S. Huang, Charles Martel, and Biswanath Mukherjee.
SURVIVABLE MULTIPATH PROVISIONING WITH DIFFERENTIAL DELAY CONSTRAINT IN TELECOM MESH NETWORKS. In INFOCOM 2008, pp. 191-195.
- [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%)
.
- [N10] D. Andrei, M. Batayneh, C. Martel, and B. Mukherjee.
PROVISIONING OF DEADLINE-DRIVEN REQUESTS WITH FLEXIBLE TRANSMISSION RATES IN DIFFERENT WDM NETWORK ARCHITECTURES.
In Proceedings of OFC, Feb. 2008, pages: 1-3
- [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%)
- [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
- [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.
- [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
- [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.
- [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.
- [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:
- the Truthsayer project
Publications
- [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.
- [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).
- [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.
- [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.
Publications
- [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%)
- [GB] A. Das, C. Martel, Stochastic Shortest Path with Unlimited Hops. In Information Processing Letters, Vol. 109, no. 5, Feb. 2009, pages 290-295.
- [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
- [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
- [G2] C. Martel. The expected complexity of Prim's minimum spanning
tree algorithm. In Information Processing Letters, vol. 81, pp.
197-201. 2002.
- [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.
- [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.
- [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.
Publications
- [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.
- [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.
- [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.
- [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.
Publications
- [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.
- [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.
- [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.
- [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.
- [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.
- [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.
- [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.
- [M8] C.U. Martel. Maximum finding on a multiple access broadcast
network. In Information Processing Letters. Vol.
pp. 7-13, 1994.
- [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.
Publications
- [N1] D. Gusfield and C. Martel. The structure and complexity of
sports elimination numbers. In Algorithmica 32:73-86 (2002).
pdf version
- [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.
- [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.
- [S0] E. Lee and C. Martel
When to use Splay Trees. To appear in Software: Practice and Experience.
- [S1] L. Hui and C.U. Martel. Randomized Competitive Algorithms for
Successful and Unsuccessful search. The Computer Journal, vol.
39, 5, 427-438, 1996.
- [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.
- [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.
- [S4] L. Hui and C.U. Martel. Unsuccessful search in self-adjusting
data structures.
Journal of Algorithms, vol.
15, pp. 447-481, 1993.
- [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.
- [S6] L. Hui and C.U. Martel. On unsuccessful search. In
proceedings of the 3rd SIAM conference on Discrete Algorithms, pp.
217-227, 1992.
- [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.
- [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.
- [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.