Kim P. Kihlstrom
Research Interests

I am interested in all areas of distributed systems, including intrusion tolerance, survivability, security, and fault tolerance. The objective of my research is to design intrusion tolerant distributed systems that are able to provide useful services despite malicious intrusions that subvert one or more processors, and despite faults or accidents that damage some portion of the system. The projects that I have worked on include:

The Starfish System
Byzantine Fault Detectors
The SecureRing Group Communication System
The Immune System
Secure Auction Service

The Starfish System

Main Starfish Website

Starfish System

The Starfish system is a new system currently under development that provides intrusion tolerance for middleware applications operating in a distributed asynchronous system. The Starfish system contains a central, highly secure and tightly coupled "body." This body is augmented by "arms" that are less tightly coupled and that have less stringent security guarantees, each of which can be removed from the body if a significant security breach occurs. New arms can be "grown" as needed. The Starfish system is a collaborative effort with Professor Priya Narasimhan of Carnegie Mellon University.

Starfish are known to have small bodies, out of which spring forth a varying number of arms, which break off when damaged. These arms subsequently heal and re-grow.

Current Westmont Students:

Previous Westmont Students:

  • Robin Elliott
  • Kelsey Marshman
  • Aaryn Smith

Summer research students 2008

  • Joel Stewart
  • Adrian Rogers
  • Toby Lounsbury
  • Mike Magnuson
  • Stephen Raub
  • Daniel Shank
  • Brad Jensen
  • Kerby Johnson
  • Chris Phillips
  • Chris Ritchey
  • Ben LaBarbera

Publications: (* indicates Westmont student authors)

Starfish System Website at Carnegie Mellon University

Byzantine Fault Detectors

Consensus is a fundamental problem in distributed computing. It is impossible to achieve consensus in an asynchronous distributed system that is subject to even one crash fault. However, if the asynchronous model is augmented by an unreliable fault detector, consensus can be solved in an asynchronous distributed system that is subject to crash faults. We extended this result to asynchronous distributed systems that are subject to Byzantine faults by defining two new classes of Byzantine fault detectors. We developed an algorithm that uses a Byzantine fault detector to solve the consensus problem in an asynchronous distributed system in which less than one-third of the processes exhibit Byzantine faults.

Publications:

The SecureRing Group Communication System

SecureRing System

The SecureRing group communication protocols provide reliable ordered message delivery and group membership services despite Byzantine faults such as might be caused by modifications to the programs of a group member following illicit access to, or capture of, a group member. The protocols multicast messages to groups of processors within an asynchronous distributed system and deliver messages in a consistent total order to all members of the group. They ensure that correct members agree on changes to the membership, that correct processors are eventually included in the membership, and that processors that exhibit detectable Byzantine faults are eventually excluded from the membership. To provide these message delivery and group membership services, the protocols make use of an unreliable Byzantine fault detector.

Publications:

The Immune System

Immune System

The Immune system aims to provide survivability to CORBA applications transparently, enabling them to continue to operate despite intrusions or accidents that damage the underlying distributed system, or faults that occur within the system. The Immune system can protect an existing unmodified CORBA application, running over an unmodified commercial ORB, against arbitrary faults, including those that arise from malicious attacks within the system. Every object within the CORBA application is actively replicated by the Immune system, with majority voting applied on incoming invocations and responses to each replica of the object. The Immune system exploits the stringent guarantees of the SecureRing protocols to enable the majority voting to be effective, even when processors within the network and objects within the application become corrupted. The Immune system is a collaborative effort with Professor Priya Narasimhan of Carnegie Mellon University.

Publications:

Secure Auction Service

Auction System

The secure open-outcry auction service is designed to operate correctly and reliably despite malicious auctioneers and bidders. At the beginning of an auction, the auctioneer announces the item being auctioned and the closing time of the auction. Periodically, the auctioneer also announces the current time. Bidders submit bids to the auctioneer, who announces each bid. At the close of the auction, the autioneer announces the winning bid and winning bidder. The auctioneer is replicated, and all communication is performed by the SecureRing protocols. The use of these mechanisms ensure that all bidders receive the same auction information, and that bidders cannot masquerade as other bidders or deny having submitted a bid.

Publications:

  • K. P. Kihlstrom, N. Narasimhan, L. E. Moser and P. M. Melliar-Smith, A Secure Auction Service, in Proceedings of the IASTED International Conference on Parallel and Distributed Computing and Systems, Anaheim, California, August 2001, pp. 599-604

Other Interests

In addition to research in distributed systems, I am also interested in computer science education, and in exploring the connections between computer science and the Christian faith. Here is a general paper that I have written on these connections:

  • K. P. Kihlstrom, "Perspectives on Faith, Learning, the Liberal Arts, and Computer Science" [pdf]

Topics of particular interest to me are:

Social and gender issues in computer science
Limits of knowledge in distributed systems and the human condition

Social and gender issues in computer science

Computer scientists are often stereotyped as asocial beings who can not communicate and are happy only when sitting at a computer writing code or playing games. How can we follow God's calling to community in a computer science program? How can we equip students with the interpersonal skills that they need for a productive career? How will we attract and retain students in computer science programs, particularly female, ethnically diverse, and economically disadvantaged students?

The percentage of women in computer science is small, and does not appear to be increasing. Why is this true, and how can we effect change? What issues are involved, and how can they be addressed? What curricular and programmatic changes can be made to encourage women and other under-represented students to pursue computer science?

Publications:

Limits of knowledge in distributed systems and the human condition

In a seminal work in distributed computer systems, Halpern and Moses[1] wrote, "distributed knowledge corresponds to knowledge that is ‘distributed’ among the members of a group, while common knowledge corresponds to a fact being ‘publicly known.’" They demonstrated that, while being highly desirable, common knowledge is unattainable in any practical distributed system. This limit on knowledge attainable in a distributed system provides insight into the larger picture of the human condition. In I Corinthians 13:12 we read "for now we see in a mirror dimly, but then face to face." While God’s view is perfect and complete in knowledge, we as limited humans cannot attain common knowledge in this life. We are exploring these ideas more fully; through a study of scripture, through further reading on knowledge in distributed systems, and through readings in philosophy and theology.

Previous Westmont Student:

  • Matthew Kaddatz

[1] Halpern, J. Y. and Moses, Y., Knowledge and Common Knowledge in a Distributed Environment, Journal of the ACM 37:3, 1990, pp. 549-587