Jiang, Anxiao (Andrew) and Cook, Matthew and Bruck, Jehoshua (2004) Optimal Interleaving on Tori. California Institute of Technology . (Unpublished) http://resolver.caltech.edu/CaltechPARADISE:2004.ETR059
See Usage Policy.
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechPARADISE:2004.ETR059
We study t-interleaving on two-dimensional tori, which is defined by the property that any connected subgraph with t or fewer vertices in the torus is labelled by all distinct integers. It has applications in distributed data storage and burst error correction, and is closely related to Lee metric codes. We say that a torus can be perfectly t-interleaved if its t-interleaving number – the minimum number of distinct integers needed to t-interleave the torus – meets the spherepacking lower bound. We prove the necessary and sufficient conditions for tori that can be perfectly t-interleaved, and present efficient perfect t-interleaving constructions. The most important contribution of this paper is to prove that the t-interleaving numbers of tori large enough in both dimensions, which constitute by far the majority of all existing cases, is at most one more than the sphere-packing lower bound, and to present an optimal and efficient t-interleaving scheme for them. Then we prove some bounds on the t-interleaving numbers for other cases, completing a general picture for the t-interleaving problem on 2-dimensional tori.
|Item Type:||Report or Paper (Technical Report)|
|Group:||Parallel and Distributed Systems Group|
|Usage Policy:||You are granted permission for individual, educational, research and non-commercial reproduction, distribution, display and performance of this work in any format.|
|Deposited By:||Imported from CaltechPARADISE|
|Deposited On:||20 Apr 2004|
|Last Modified:||26 Dec 2012 13:53|
Repository Staff Only: item control page