Scheduling Random Walks
Library Home 
Full Table of Contents 
Library Help
http://www.maa.org/mathland/mathtrek_1_22_01.html  


Ivars Peterson (MathTrek)  
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 datasharing 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 (912), College 
Languages:  English 
Resource Types:  Articles 
Math Topics:  Combinatorics, Probability 
[Privacy Policy] [Terms of Use]
© 1994 The Math Forum at NCTM. All rights reserved.
http://mathforum.org/