log in  |  register  |  feedback?  |  help  |  web accessibility
Logo
Distributed Programming and Timestep Stochastic Simulation
Friday, September 28, 2012, 1:00-2:00 pm Calendar
  • You are subscribed to this talk through .
  • You are watching this talk through .
  • You are subscribed to this talk. (unsubscribe, watch)
  • You are watching this talk. (unwatch, subscribe)
  • You are not subscribed to this talk. (watch, subscribe)
Abstract

My research, in general, is concerned with correctness and performance of distributed systems and network protocols. This talk will outline recent work and future directions in two areas, namely, correct distributed programming and timestep stochastic simulation.

Correct distributed programming:  This is a practical and rigorous method to write correct distributed programs (aka multi-threaded programs). The intended external behavior of a distributed program is defined by a so-called service program. The service program has special structure that makes it easy to understand. The service program, say B, of a program A is used instead of A when writing a program C that makes use of A. The notion of A-implements-B is formalized as correctness properties of the distributed program of A and B-inverse. If the properties hold, then in any program C that uses B, breplacing B by A preserves all the correctness properties of C. Assertional reasoning is used to establish correctness properties, thus accounting for all possible variations in the execution speeds of threads.

Timestep stochastic simulation:  Packet-level simulation (e.g., NS, OPNET) is the de facto method for performance evaluation of computer networks, but it is horribly slow for realistic network speeds and sizes. Timestep stochastic simulation is a method to generate sample paths of computer networks at a fraction of the cost of packet-level simulation. It generates the evolution of the system state S(t) on a sample path in time steps of size δ. At each step, the probability distribution Pr[S(t + δ)|S(t)] is obtained analytically and the new state S(t + δ) is sampled from this distribution. Because packet transmissions are replaced by time steps, sample paths are generated at a fraction of the cost, thereby enabling performance evaluation of networks of realistic size and speeds.

This talk is organized by Jeff Foster