Search

We consider collision channel without feedback in which collided packets are considered unrecoverable. For each user, the transmission of packets foHows a specific periodical pattern, called the protocol sequence. Due to the lack of feedback, the beginning of the protocol sequences cannot be synchronized and nonzero relative offsets are inevitable. It results in variation of throughput. In this paper, we investigate optimal protocol sequence sets, in the sense that the throughput variance is zero. Such protocol sequences are said to be shift-invariant (SI). The characterizing properties of SI protocol sequences are presented. We also prove that SI sequences are identifiable, meaning that the receiver is able to determine the sender of each successfully received packet without any packet header. A general construction of SI sequences that meets the lower bound on sequence length is given. Besides, we study the least periods of SI sequences, and show that the least periods must be distinct in some cases. The throughput performance is compared numerically with other protocol sequences. Index Terms--Collision channel without feedback, protocol sequences.

We consider fair resource allocation in Gaussian frequency-division broadcast channel with intersymbol interference. The goal is to allocate power and subchannels in a way such that proportional fairness is achieved. We show that the subchannel allocation problem is NP-hard. If multiple users are allowed to time-share a subchannel, the relaxed problem is equivalent to the cake cutting problem and can be efficiently solved. For the joint power and subchannel allocation problem, we propose an iterative method, which solves the power allocation problem and subchannel allocation problem alternately. Simulation results show that its performance is nearly optimal. Index Terms--Power allocation, subchannel allocation, multiuser OFDM, fairness, cake cutting.

The sum capacity of the one-sided parallel Gaussian interference channel is shown to be a concave function of user powers. Exploiting the inherent structure of the problem, we construct a numerical algorithm to compute it. Two suboptimal schemes are compared with the capacity-achieving scheme. One of the suboptimal schemes, namely iterative waterfilling, yields close-to-capacity performance when the cross link gain is small. Index Terms--Gaussian interference channels, iterative waterfilling, sum capacity.

The problem of power control and signature sequence adaptation in code-division multiple-access (CDMA) systems is studied under a game-theoretic framework. Each user tries to maximize his own utility function, which may be different from others. Sufficient conditions for the existence of an equilibrium point in this multi-objective optimization problem are identified. The methodology for analyzing this class of problems is illustrated by examples. Index Terms--Code-division multiple-access (CDMA) systems, game theory, Nash equilibrium, power control, signature sequence.

Fractional repetition (FR) codes are a class of repair efficient erasure codes that can recover a failed storage node with both optimal repair bandwidth and complexity. In this paper, we study the minimum distance of FR codes, which is the smallest number of nodes whose failure leads to the unrecoverable loss of the stored file. We derive a new upper bound on the minimum distance of FR codes, which is tighter than the Singleton bound and a Singleton-like bound that takes locality into account. Based on regular graphs and combinatorial designs, several families of FR codes with optimal minimum distance are obtained. [ABSTRACT FROM AUTHOR]

Symbol-pair codes are block codes when considering the pair-metric, and are designed to protect against pair-errors occur in the pair-read vector which consisting of overlapping pairs of symbols. A code that achieves the analog of Singleton bound for symbol-pair codes is called a maximum distance separable (MDS) symbol-pair code. The contribution of this letter is twofold. First, we give a lower bound of minimum pair-distance of repeated-root constacyclic codes in terms of minimum Hamming distance, which extends the lower bound given by Chen, Lin and Liu. Second, we give three new classes of MDS symbol-pair codes. As we know, for an MDS symbol-pair code with a fixed minimum pair-distance, the larger the code length of the code has, the higher the code rate is. The first class of MDS symbol-pair codes we show has unbounded code length and the other two classes of MDS symbol-pair codes have larger code lengths than the code lengths of existing MDS symbol-pair codes under the same minimum pair-distance 6. [ABSTRACT FROM AUTHOR]

Conflict-avoiding codes (CACs) were introduced by Levenshtein as a single-channel transmission scheme for a multiple-access collision channel without feedback. When the number of simultaneously active source nodes is less than or equal to the weight of a CAC, it is able to provide a hard guarantee that each active source node transmits at least one packet successfully within a fixed time duration, no matter what the relative time offsets between the source nodes are. In this article, we extend CACs to multichannel CACs for providing such a hard guarantee over multiple orthogonal channels. Upper bounds on the number of codewords for multichannel CACs of weights three and four are derived, and constructions that are optimal with respect to these bounds are presented. [ABSTRACT FROM AUTHOR]

In this paper, we introduce an $n$ -channel multilevel imperfect secret sharing problem, which can be regarded as a generalization of secret sharing and a variation of multilevel diversity coding. In this model, a discrete memoryless source (DMS) is encoded into $n$ encoded messages. To measure the secrecy of the system, we introduce a security level for each subset of encoded messages. In the paper, we focus on the $n$ -channel symmetric multilevel imperfect secret sharing (SMISS) problem, i.e., the security levels of all the subsets with the same cardinality are identical. First, we explicitly characterize the coding rate regions for 2-channel and 3-channel SMISS problems. However, it is difficult to characterize the explicit rate region for a general $n$ , since the complexity of designing optimal coding schemes can grow with $n$ exponentially. Nevertheless, we put forward an inner bound and an outer bound on the rate region of the general $n$ -channel SMISS problem. Moreover, we consider two special cases, i.e., the Two-SMISS problem and the linear SMISS problem, and prove that the inner and outer bounds are tight for these two problems, respectively. [ABSTRACT FROM AUTHOR]

A locally repairable code (LRC) is a linear code such that every code symbol can be recovered by accessing a small number of other code symbols. In this paper, we study bounds and constructions of LRCs from the viewpoint of parity-check matrices. Firstly, a simple and unified framework based on parity-check matrix to analyze the bounds of LRCs is proposed, and several new explicit bounds on the minimum distance of LRCs in terms of the field size are presented. In particular, we give an alternate proof of the Singleton-like bound for LRCs first proved by Gopalan et al. Some structural properties on optimal LRCs that achieve the Singleton-like bound are given. Then, we focus on constructions of optimal LRCs over the binary field. It is proved that there are only five classes of possible parameters with which optimal binary LRCs exist. Moreover, by employing the proposed parity-check matrix approach, we completely enumerate all these five classes of optimal binary LRCs attaining the Singleton-like bound in the sense of equivalence of linear codes. [ABSTRACT FROM AUTHOR]

The partially collaborative repair of multiple node failures in distributed storage systems is investigated. An exact-repair code is constructed using a bilinear form, which achieves the minimum-bandwidth partially collaborative repair (MBPCR) point. When the storage capacity is minimum, the problem of repairing multi-node failures using a Maximum Distance Separable (MDS) array code is also investigated. The minimum-storage partially collaborative repair (MSPCR) problem with same number of repairing and reconstruction nodes has been studied before. In this paper, the scenario where the number of repairing nodes is greater than that of reconstruction nodes and the storage capacity is already minimal for partial collaboration is considered. An MDS array code is constructed, which asymptotically achieves the MSPCR point. Further, we show that the given code construction could not always have a regular collaborative structure. [ABSTRACT FROM AUTHOR]

Fractional repetition (FR) codes form a special class of minimum bandwidth regenerating codes by providing uncoded repairs via a table-based repair model. For a given file size, it is desirable to design FR codes that minimize the reconstruction degree, which is defined as the number of storage nodes required for data retrieval. In this paper, we first consider a lower bound on the reconstruction degree of FR codes obtained by Silberstein and Etzion. We present several families of FR codes that attain this lower bound, which are derived from combinatorial designs and regular graphs. We further provide a new lower bound on the reconstruction degree of FR codes, which is tighter than the existing one. Moreover, we show that for an FR code with reconstruction degree achieving the lower bounds, the corresponding dual code attains upper bounds on the supported file size. [ABSTRACT FROM AUTHOR]

We consider a single-hop wireless sensor network in which each sensor node has an individual elastic data stream to transmit to each other node. We refer to this traffic pattern as unicast in this paper. The network has multiple slotted channels available for the data transmissions. To guarantee successful unicast within a bounded delay, we consider deterministic schemes that pre-assign each node a periodic schedule sequence to schedule transmitting and receiving at each time slot. The sequence period should be minimized since it upper bounds the unicast delay. We have investigated both synchronous TDMA sequences and asynchronous sequences. Since accurate time synchronization is difficult to achieve in sensor networks, we mainly present analysis and design for asynchronous sequences. In this paper, for a group-based channel assignment, we present a lower bound on the common period and propose a sequence construction method by which the period can achieve the same order as the lower bound. We also analyze optimal transmitting and receiving probabilities for two random schemes and compare their frequency utilization efficiency. Finally, unicast delay and energy consumption performance are compared by simulations. [ABSTRACT FROM AUTHOR]

The problem of exact-repair regenerating codes against eavesdropping attack is studied. The eavesdropping model we consider is that the eavesdropper has the capability to observe the data involved in the repair of a subset of $\ell $ nodes. An $(n,k,d,\ell)$ secure exact-repair regenerating code is an $(n,k,d)$ exact-repair regenerating code that is secure under this eavesdropping model. It has been shown that for some parameters $(n,k,d,\ell)$ , the associated optimal storage-bandwidth tradeoff curve, which has one corner point, can be determined. The focus of this paper is on characterizing such parameters. We establish a lower bound $\hat {\ell }$ on the number of wiretap nodes, and show that this bound is tight for the case $k = d = n-1$. [ABSTRACT FROM AUTHOR]

Erasure coding is widely used for massive storage in data centers to achieve high fault tolerance and low storage redundancy. Since the cross-rack communication cost is often high, it is critical to design erasure codes that minimize the cross-rack repair bandwidth during failure repair. In this paper, we analyze the optimal trade-off between storage redundancy and cross-rack repair bandwidth specifically for data centers, subject to the condition that the original data can be reconstructed from a sufficient number of any non-failed nodes. We characterize the optimal trade-off curve under functional repair, and propose a general family of erasure codes called rack-aware regenerating codes (RRC), which achieve the optimal trade-off. We further propose exact repair constructions of RRC that have minimum storage redundancy and minimum cross-rack repair bandwidth, respectively. We show that (i) the minimum storage redundancy constructions support a wide range of parameters and have cross-rack repair bandwidth that is strictly less than that of the classical minimum storage regenerating codes in most cases, and (ii) the minimum cross-rack repair bandwidth constructions support all the parameters and have less cross-rack repair bandwidth than that of the minimum bandwidth regenerating codes for almost all of the parameters. [ABSTRACT FROM AUTHOR]

Distributed storage systems that deploy erasure codes can provide better features such as lower storage overhead and higher data reliability. In this paper, we focus on fractional repetition (FR) codes, which are a class of storage codes characterized by the features of uncoded exact repair and minimum repair bandwidth. We study the duality of FR codes and investigate the relationship between the supported file size of an FR code and its dual code. Based on the established relationship, we derive an improved dual bound on the supported file size of FR codes. We further show that FR codes constructed from t -designs are optimal when the size of the stored file is sufficiently large. Moreover, we present the tensor product technique for combining FR codes and elaborate on the file size hierarchy of resulting codes. [ABSTRACT FROM AUTHOR]

Array codes are used widely in data storage systems such as redundant array of independent disks. The row-diagonal parity (RDP) codes and EVENODD codes are two popular double-parity array codes. The increasing capacity of hard disks demands better fault tolerance by using array codes with three or more parity disks. Although many extensions of RDP and EVENODD codes have been proposed, their main drawback is high decoding complexity. In this paper, we propose a unified form of RDP and EVENODD codes under which RDP codes can be treated as shortened EVENODD codes. Moreover, an efficient decoding algorithm based on an LU factorization of a Vandermonde matrix is proposed. The LU decoding method is applicable to all the erasure patterns of RDP and EVENODD codes with three parity columns. It is also applicable to the erasure decoding of RDP and EVENODD codes with more than three parity columns when the number of continuous surviving parity columns is no less than the number of erased information columns and the first parity column has not failed. The proposed efficient decoding algorithm is also applicable to other Vandermonde array codes, with less decoding complexity than that of the existing method. [ABSTRACT FROM AUTHOR]

Since the proof in 1982, by Tsfasman Vladut and Zink of the existence of algebraic-geometric (AG) codes with asymptotic performance exceeding the Gilbert--Varshamov (G--V) bound, one of the challenges in coding theory has been to provide explicit constructions for these codes. In a major step forward during 1995-1996, Garcia and Stichtenoth (G--S) provided an explicit description of algebraic curves, such that AG codes constructed on them would have performance better than the G--V bound. We present here the first low-complexity algorithm for obtaining the generator matrix for AG codes on the curves of G--S. The symbol alphabet of the AG code is the finite field of [q.sup.2], [q.sup.2] [is greater than or equal to] 49, elements. The complexity of the algorithm, as measured in terms of multiplications and divisions over the finite field GF [(q.sup.2)], is upper-bounded by [[[N log.sub.q](N)].sup.3] where N is the length of the code. An example of code construction using the above algorithm is presented. By concatenating the AG code with short binary block codes, it is possible to obtain binary codes with asymptotic performance close to the G--V bound. Some examples of such concatenation are included. Index Terms--Algebraic-geometric (AG) codes, concatenated codes, function field tower, Gilbert--Varshamov (G--V) bound.

We consider a hierarchical cellular system, which consists of a macrolayer and a microlayer. The macrocells accommodate fast mobile users. However, if we direct too many mobile users to the macrocells, the system capacity is low. On the other hand, the microcells are designed to increase capacity, but they cause a large number of handoffs. The aim is to maximize the system capacity while keeping the amount of handoff small. We minimize the handoff rate by a fuzzy layer selection algorithm, which makes use of the past cell dwell times of a user and the channel occupancy of the target cell. To maximize the capacity, we propose a distributed channel assignment algorithm to dynamically allocate the channels among the two layers. Exchange of information is allowed between neighboring macrocells. The state of channel assignment in a macrocell and its interfering cells are tabulated in a channel allocation table, which provides all information required in the integrated resource allocation scheme. The performance is evaluated by simulation and compared with the popular layer selection scheme known as the threshold method. Index Terms--Channel assignment, fuzzy logic, hierarchical cellular systems, layer selection, macrocell/microcell.

A description of how places split in an asymptotically optimal tower of function fields studied by Garcia and Stichtenoth is provided and an exact count of the number of places of degree one is given. This information is useful in the setting up of generator matrices for algebraic-geometry codes constructed over this function field tower. These long codes have performance that asymptotically improves upon the Gilbert-Varshamov bound. Index Terms--Agebraic-geometry (AG) codes, function field tower, Garcia-Stichtenoth tower.

Distributed storage systems can store data with erasure coding to maintain data availability with low storage redundancy. One class of erasure coding is based on regenerating codes, which provably minimize the amount of data transferred for failure repair and realize the optimal tradeoff between the storage redundancy and the amount of traffic transferred for repair. Typical regenerating codes often require surviving storage nodes to encode their stored data for repair. In this paper, we study a framework called proxy-assisted regeneration, which offloads the repair process to a centralized proxy. We extend the previous applied work on proxy-assisted regeneration by providing theoretical validation. Specifically, we study a special class of regenerating codes called proxy-assisted minimum storage regenerating (PMSR) codes, which enable uncoded repair without the need of encoding in surviving nodes, while preserving the minimum storage redundancy and minimum amount of traffic transferred for repair. We formally prove the existence of PMSR codes for two configurations: 1) repairing single-node failures under double fault tolerance and 2) repairing double-node failures under triple fault tolerance. We also provide a semi-deterministic PMSR code construction for repairing single-node failures under double fault tolerance. [ABSTRACT FROM AUTHOR]

The problem of characterizing the fundamental tradeoff between storage and repair bandwidth of exact-repair regenerating codes against a passive eavesdropper is studied. The eavesdropper is assumed to be capable of observing the data stored in a fixed number of nodes and the data involved in the repair of these nodes. In this paper, the tradeoff for regenerating codes with small parameters is characterized, and then, the results are extended to some general settings. [ABSTRACT FROM PUBLISHER]

We study the transmission cost of repair in a distributed storage system, where storage nodes are connected together through an arbitrary network topology, and there is a cost in the use of the network link. Contrary to the classical model, where there exists a link between a pair of storage node, in our repair model there might not exist a link between some pairs of storage nodes or it might be expensive to use. For that, we propose surviving nodes cooperation in repair, meaning that the surviving nodes as the intermediate nodes combine their received packets with their own stored packets and then transmit coded packets towards the new node. We show that surviving node cooperation can reduce the repair-cost, the sum of the costs for transmitting repairing data between the surviving nodes and the new node. For the system that allows surviving node cooperation, we find the minimum-cost codes in repair by firstly deriving a lower bound of the repair-cost through an optimization problem and then proposing achievable codes. We show the gain of the proposed codes in reducing the repair-cost in some scenarios. Copyright © 2016 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

In distributed storage systems, regenerating codes can achieve the optimal tradeoff between storage capacity and repair bandwidth. However, a critical drawback of existing regenerating codes, in general, is the high coding and repair complexity, since the coding and repair processes involve expensive multiplication operations in finite field. In this paper, we present a design framework of regenerating codes, which employ binary addition and bitwise cyclic shift as the elemental operations, named BASIC regenerating codes. The proposed BASIC regenerating codes can be regarded as a concatenated code with the outer code being a binary parity-check code, and the inner code being a regenerating code utilizing the binary parity-check code as the alphabet. We show that the proposed functional-repair BASIC regenerating codes can achieve the fundamental tradeoff curve between the storage and repair bandwidth asymptotically of functional-repair regenerating codes with less computational complexity. Furthermore, we demonstrate that the existing exact-repair product-matrix construction of regenerating codes can be modified to exact-repair BASIC product-matrix regenerating codes with much less encoding, repair, and decoding complexity from the theoretical analysis, and with less encoding time, repair time, and decoding time from the implementation results. [ABSTRACT FROM AUTHOR]

This paper investigates the linear network coding problem for erasure broadcast channel with user feedback. An innovative linear network code is shown to be uniformly optimal for the system. In general, determining the existence of innovative packets is proved to be NP-complete. When the finite field size is larger than the number of users, innovative packets always exist and the problem of finding an innovative encoding vector with smallest Hamming weight is considered. The corresponding decision problem is shown to be NP-complete. Optimal and approximate network coding algorithms for maximizing the sparsity of encoding vectors are designed. [ABSTRACT FROM AUTHOR]

Binary maximum distance separable (MDS) array codes are widely used in storage systems. EVENODD code and row-diagonal parity (RDP) code are two well-known binary MDS array codes with two parity columns. The Blaum–Bruck–Vardy (BBV) code is an extension of the double-erasure-correcting EVENODD code. It is known that the BBV code is always MDS for three parity columns, and sufficient conditions for up to eight parity columns to be MDS are also known. However, the MDS condition for more than eight parity columns is an open problem since then. In this letter, we study the MDS condition of BBV code and give a sufficient MDS condition of the BBV code with more than eight parity columns. [ABSTRACT FROM PUBLISHER]

Fractional repetition (FR) codes are a family of repair-efficient storage codes that provide exact and uncoded node repair at the minimum bandwidth regenerating point. The advantageous repair properties are achieved by a tailor-made two-layer encoding scheme which concatenates an outer maximum-distance-separable (MDS) code and an inner repetition code. In this study, the authors generalise the application of FR codes and propose heterogeneous fractional repetition (HFR) code, which is adaptable to the scenario where the repetition degrees of coded packets are different. The authors provide explicit code constructions by utilising group divisible designs, which allow the design of HFR codes over a large range of parameters. The constructed codes achieve the system storage capacity under random access repair and have multiple repair alternatives for node failures. Further, the authors take advantage of the systematic feature of MDS codes and present a novel design framework of HFR codes, in which storage nodes can be wisely partitioned into clusters such that data reconstruction time can be reduced when contacting nodes in the same cluster. [ABSTRACT FROM AUTHOR]

In distributed storage systems (DSS), the storage costs and download costs with different storage nodes, in general, can be different. In such heterogeneous storage systems, how to establish a fundamental tradeoff between system storage cost and system repair cost is investigated. We formulate the problem of establishing the tradeoff between system storage cost and system repair cost as a bi-objective linear programming problem subject to the min-cut constraint of information flow graphs. We give a tight min-cut bound for heterogeneous DSSs with general setting. Moreover, we show that the tradeoff between system storage cost and system repair cost of some special heterogeneous DSSs can be established in polynomial time. Copyright © 2014 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

In practical large-scale distributed storage systems, node failures are unavoidable. It is therefore desirable to quickly recreate the failed nodes in order to maintain the system integrity. In this letter, we consider a family of erasure codes that provide uncoded repair, where the failed node is regenerated by transfer of data without extra arithmetic operations. We introduce flexible fractional repetition (FFR) code, of which the coding scheme is a concatenation of an outer MDS code and an inner repetition code. Our proposed codes are applicable to the heterogeneous network environment where node storage capacities and packet repetition degrees vary in a wide range. We present explicit constructions of FFR codes by utilizing combinatorial designs. We further propose a heuristic code construction. Evaluation results show that FFR codes outperform regenerating codes in node repair efficiency. [ABSTRACT FROM PUBLISHER]

In a point-to-point communication system, which consists of a sender, a receiver, and a set of noiseless channels, the sender wishes to transmit a private message to the receiver through the channels, which may be eavesdropped by a wiretapper. The set of wiretap sets is arbitrary. The wiretapper can access any one but not more than one wiretap set. From each wiretap set, the wiretapper can obtain some partial information about the private message, which is measured by the equivocation of the message given the symbols obtained by the wiretapper. The security strategy is to encode the message with some random key at the sender. Only the message is required to be recovered at the receiver. Under this setting, we define an achievable rate tuple consisting of the size of the message, the size of the key, and the equivocation for each wiretap set. We first prove a tight rate region when both the message and the key are required to be recovered at the receiver. Then, we extend the result to the general case when only the message is required to be recovered at the receiver. Moreover, we show that even if stochastic encoding is employed at the sender, the message rate cannot be increased. [ABSTRACT FROM PUBLISHER]

Index coding (IC), which can be regarded as a special class of network coding, deals with the problem of sending a number of packets to a group of receivers, each of which requests one packet and may have some other packets in its cache. This paper generalizes the IC problem in that both the packet requested by a receiver and the packets in its cache can be linear combinations of the packets. To minimize the number of transmissions required, a heuristic algorithm based on the idea of partitioning the users into coding groups is designed. To realize this idea, a polynomial time algorithm to determine whether a set of users form a coding group over the binary field or a field with a size larger than the number of users is constructed. For users that form a coding group, the corresponding encoding vector can be also found. A lower bound is derived in order to evaluate the performance of the heuristic algorithm. Numerical results show that the number of transmissions required by the heuristic algorithm and the lower bound both grow roughly linearly with the number of users, and the heuristic algorithm outperforms some benchmark algorithms. [ABSTRACT FROM PUBLISHER]

The distance profiles of linear block codes can be employed to design variational coding scheme for encoding message with variational length and getting lower decoding error probability by large minimum Hamming distance, where one example is in the design of transport format combination indicators (TFCIs) in CDMA. Considering convenience for encoding, we focus on the distance profiles with respect to cyclic subcode chains (DPCs) of cyclic codes over $GF(q)$ with length n$ such that \gcd(n, q)=1$. In this paper, the optimum DPCs and the corresponding optimum cyclic subcode chains are investigated on the punctured second-order Reed–Muller code for increasing message length, where two standards on the optimums are studied according to the rhythm of increase. Ignoring the dimension profile, the device will coincide with that of TFCI. [ABSTRACT FROM AUTHOR]

In order to provide fault-tolerance and guarantee reliability, data redundancy should be introduced in distributed storage systems. The emerging coding techniques for storage such as fractional repetition codes, provide the required redundancy more efficiently than the conventional replication scheme. In this letter, we extend the construction of fractional repetition codes and present a new coding scheme, termed general fractional repetition codes. The proposed codes can be applied to storage systems in which the storage capacities of nodes may be different. Based on a combinatorial structure known as group divisible design, the new code construction is available for a large set of parameters. The performance of the proposed codes is evaluated by a metric called node repair alternativity, which measures the number of different subsets of nodes that enable the repair of a specific failed node. [ABSTRACT FROM PUBLISHER]

In vehicular collision avoidance systems, safety messages are broadcast by mobile users periodically on the highway to all of their neighbors within hearing range. These safety messages are time sensitive and have stringent delay requirements. Conventional carrier-sense multiple access, where users must content with channel access, is not suitable for this kind of application. In this paper, we propose using protocol sequences to broadcast safety messages. Protocol sequences are deterministic 0–1 sequences. Each user reads out the 0's and 1's of the assigned protocol sequence periodically and transmits a packet in a time slot if and only if the sequence value is equal to 1. It requires no time synchronization among the users. We compare the delay performance with an ALOHA-type random access scheme and show that the delay can, in fact, be reduced by employing protocol sequences instead. [ABSTRACT FROM PUBLISHER]

In this paper we investigate the identification and synchronization problems on a multiple access collision channel. Following Massey's lead, solutions to these problems are addressed by protocol sequences. This paper considers two different levels of user synchroneity: frame-synchronous access and slot-synchronous access. For the identification problem, we study user-detectable sequences. These are sequences with the cross-correlation property that allows each active user be detected within a bounded delay basing only on the channel activity information observed. Furthermore, we investigate the synchronization problem for delay-detectable sequences under the slot-synchronous access assumption. The goal of the synchronization problem is to determine the offset relations among all the active users. Sequences that allow such determination can be viewed as a special subset of user-detectable sequences. For both of these sequence families, it is desirable that the sequence length should be as short as possible. Hence, it is important to derive the minimum sequence lengths for these respective families. This is an extremely difficult open problem. Nevertheless, lower and upper bounds on these minimum lengths are presented in this paper under different levels of synchroneity assumptions. In addition, the performance of these sequences is demonstrated via numerical simulation. [ABSTRACT FROM PUBLISHER]

One of the design objectives in distributed storage system is the minimization of the data traffic during the repair of failed storage nodes. By repairing multiple failures simultaneously and cooperatively rather than successively and independently, further reduction of repair traffic is made possible. A closed-form expression of the optimal tradeoff between the repair traffic and the amount of storage in each node for cooperative repair is given. We show that the points on the tradeoff curve can be achieved by linear cooperative regenerating codes, with an explicit bound on the required finite-field size. The proof relies on a max-flow-min-cut-type theorem from combinatorial optimization for submodular flows. Two families of explicit constructions are given. [ABSTRACT FROM AUTHOR]

In this paper, we investigate lattice network codes (LNCs) constructed from Eisenstein integer based lattices. Quantization and encoding algorithms over Eisenstein integers are first introduced. Then, a union bound estimation (UBE) of the decoding error probability is derived when the shaping region of the LNC is a product of regular hexagons. Next, the Gaussian reduction algorithm is generalized to be applicable to complex lattices over Eisenstein integers such that an optimal coefficient vector can be found in the two-transmitter single-relay system. Based on the UBE, design criteria for optimal LNCs with minimum decoding error probability are formulated and applied to construct both Gaussian integer and Eisenstein integer based good LNCs from rate-1/2 feed-forward convolutional codes by Complex Construction A. The constructed codes provide up to 7.65 dB nominal coding gains over Rayleigh fading channels. Furthermore, we introduce the construction of LNCs from linear codes by Complex Construction B. The nominal coding gains and error performance of the LNCs thus constructed are explicitly analyzed. Examples show that the LNCs constructed by Complex Construction B provide a better tradeoff between code rate and nominal coding gain. [ABSTRACT FROM AUTHOR]

Strongly conflict-avoiding codes (SCACs) are used in the slot-asynchronous multiple-access collision channel without feedback to guarantee that each active user can send at least one packet successfully in the worst case within a fixed period of time. The number of codewords in an SCAC is the number of potential users that can be supported. In this paper, a general upper bound on the size of SCAC is derived. We further improve the upper bound if the code has some special structure, called equi-difference, and we show this bound is asymptotically tight. [ABSTRACT FROM AUTHOR]

A channel is asynchronous if all users can start to transmit at an arbitrary point in time. Protocol sequences are used for multiple access in the collision channel without feedback. In this paper, we consider protocol sequence sets with the property that each user is able to successfully send at least one packet in each sequence period for the asynchronous channel. Such sequence sets are said to be completely irrepressible (CI). We analyze the class of CI sequences with the minimum number of ones in each period and derive lower bound on the minimum period. Moreover, if the sequence structure satisfies some technical conditions, which are called equi-difference, we improve the lower bound and present a construction that asymptotically meets this lower bound. We also show that the deterministic sequences proposed in this paper yield better performance in terms of average delay than the random approach. [ABSTRACT FROM PUBLISHER]