Drexel dragonThe Math ForumDonate to the Math Forum

The Math Forum Internet Mathematics Library

Scheduling Random Walks

_____________________________________
Library Home || Full Table of Contents || Suggest a Link || 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-2014 Drexel University. All rights reserved.
http://mathforum.org/
The Math Forum is a research and educational enterprise of the Goodwin College of Professional Studies.The Math Forum is a research and educational enterprise of the Drexel University School of Education.