CaltechAUTHORS
  A Caltech Library Service

Optimal Interleaving on Tori

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

[img]
Preview
PDF
See Usage Policy.

424Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechPARADISE:2004.ETR059

Abstract

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)
Related URLs:
URLURL TypeDescription
http://www.paradise.caltech.edu/papers/etr059.pdfPublisherUNSPECIFIED
Group:Parallel and Distributed Systems Group
Record Number:CaltechPARADISE:2004.ETR059
Persistent URL:http://resolver.caltech.edu/CaltechPARADISE:2004.ETR059
Usage Policy:You are granted permission for individual, educational, research and non-commercial reproduction, distribution, display and performance of this work in any format.
ID Code:26088
Collection:CaltechPARADISE
Deposited By: Imported from CaltechPARADISE
Deposited On:20 Apr 2004
Last Modified:26 Dec 2012 13:53

Repository Staff Only: item control page