Selected Recent Talks
September. 2004 - Martel

Small Worlds

  • [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, July, 2004.
    In this paper we show that Kleinberg's basic model has expected diameter O(log n) and we suggest improved routing algorithms to come closer to this bound.
  • powerpoint for this talk

    Authentic Publication

  • Integrity critical databases, such as financial information used in high-value decisions, are frequently published over the internet. Publishers of such data must satisfy the integrity, authenticity, and non-repudiation requirements of end clients. Providing this protection over public data networks is costly. This is partly because building and running secure systems is hard. In practice, large systems cannot be verified to be secure and are frequently penetrated. The negative consequences of a system intrusion at the data publisher can be severe. The problem is further complicated by data and server replication to satisfy availability and scalability requirements. We aim to reduce the trust required of the publisher of large, infrequently updated databases. To do this, we separate the roles of data owner and data publisher. With a few trusted digital signatures on the part of the owner, an untrusted publisher can use techniques based on Merkle hash trees to provide authenticity and non-repudiation of the answer to a database query. More info is at:
  • Authentic Publication Website
  • powerpoint for this talk