Drexel dragonThe Math Forum

The Math Forum Internet Mathematics Library

Scheduling Random Walks

Library Home || Full Table of Contents || Library Help

Visit this site: http://www.maa.org/mathland/mathtrek_1_22_01.html

Author:Ivars Peterson (MathTrek)
Description: Among networked computers, some sort of software scheduler must regulate data flow, but proving that a given scheduler not only prevents conflicts but also performs its duties efficiently can be surprisingly difficult. Computer scientists have found that analyzing even simple data-sharing cases can be troublesome. One important scheduling problem is equivalent to moving two tokens, each one at the start of a different infinite string of random digits. At each tick of a clock, the scheduler chooses which of the tokens to move one digit to the right, always making sure that the tokens never end up on the same number at the same time. Can the scheduler keep the tokens going forever along their own strings without ever having both tokens simultaneously on, say, 7?

Levels: High School (9-12), College
Languages: English
Resource Types: Articles
Math Topics: Combinatorics, Probability

[Privacy Policy] [Terms of Use]

Home || The Math Library || Quick Reference || Search || Help

© 1994- The Math Forum at NCTM. All rights reserved.