What is a Model Problem?

It is common for a discipline, especially one that is just getting its wits about itself, to adopt some shared, well-defined problems for teaching and study. Often known as model systems or type problems, they provide a way to compare methods and results, work out new techniques on standard examples, and set a minimum standard of capability for new participants. In time, a reasonable approach to some of these problems becomes the price of admission to get serious consideration of a new technique. Model problems also provide a pre-debugged source of educational exercises. Biology, for example, has

  • Drosophila melanogaster (the fruit fly)
  • Rattus Norwegicus (the lab rat)
  • Escherichia coli (the digestive bacterium)

Each of these is part of the common language of discourse in the field. Each provides a familiar concrete instance that illustrates an important set of issues. This allows discussions to start from shared knowledge of the basic example and proceed expeditiously to the result, theory, or technique of current interest. Closer to home, computer science has model problems in many areas. Familiar examples include

  • Algorithms and Data Structures: sort, search, greatest common divisor, prime integers, set, stack, queue
  • Synchronization: reader/writer, producer/consumer, dining philosophers, cigarette smokers
  • Programming Methodology: eight queens, tower of Hanoi
  • Formal Specifications: telegraph, lift (elevator, on the west side of the Atlantic), library
  • Combinatoric Optimization: travelling salesman

At this site, we propose several model problems for self-adaptation, discuss the interesting design problems they raise, and show how some of the work in the community addresses each of them. Our intention is to stimulate a discussion about these problems, potential additional problems, and the criteria for choosing problems and evaluating or comparing solutions. To that end, this is a living site. We will attempt to incorporate comments and suggestions, along with short sketches of solutions. We are open to suggestions about how longer solutions or comparison of alternative solutions should be handled.