English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
  Deterministic Random Walks on the Two-Dimensional Grid

Doerr, B., & Friedrich, T. (2006). Deterministic Random Walks on the Two-Dimensional Grid. In Algorithms and Computation: 17th International Symposium, ISAAC 2006 (pp. 474-483). Berlin, Germany: Springer.

Item is

Files

show Files
hide Files
:
2006ISAAC.pdf (Any fulltext), 123KB
 
File Permalink:
-
Name:
2006ISAAC.pdf
Description:
-
OA-Status:
Visibility:
Private
MIME-Type / Checksum:
application/pdf
Technical Metadata:
Copyright Date:
-
Copyright Info:
-
License:
-

Locators

show

Creators

show
hide
 Creators:
Doerr, Benjamin1, Author           
Friedrich, Tobias1, Author           
Asano, Tetsuo1, Editor           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 Abstract: Deterministic and randomized balancing schemes are used to distribute workload evenly in networks. In this paper, we compare two very general ones: The random walk and the (deterministic) Propp machine. Roughly speaking, we show that on the two-dimensional grid, the Propp machine always has the same number of tokens on a node as does the random walk in expectation, apart from an additive error of less than eight. This constant is independent of the total number of tokens and the runtime of the two processes. However, we also show that it makes a difference whether the Propp machine serves the neighbors in a circular or non-circular order.

Details

show
hide
Language(s): eng - English
 Dates: 2007-04-252006
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 314492
Other: Local-ID: C1256428004B93B8-2E93A9601DA3F2C0C125722E004854E8-DF2006
 Degree: -

Event

show
hide
Title: Untitled Event
Place of Event: Kolkata, India
Start-/End Date: 2006-12-18

Legal Case

show

Project information

show

Source 1

show
hide
Title: Algorithms and Computation : 17th International Symposium, ISAAC 2006
Source Genre: Proceedings
 Creator(s):
Affiliations:
Publ. Info: Berlin, Germany : Springer
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 474 - 483 Identifier: ISBN: 978-3-540-49694-6

Source 2

show
hide
Title: Lecture Notes in Computer Science
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 4288 Sequence Number: - Start / End Page: - Identifier: -