Scheduling Random Walks
Library Home || Full Table of Contents || Library Help
|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 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|
|Math Topics:||Combinatorics, Probability|
© 1994- The Math Forum at NCTM. All rights reserved.