Traditional trajectory planning methods are challenged by high-dimensional robot navigation, particularly in handling high-velocity obstacles and computation efficiency. This paper introduces a novel approach leveraging Dynamic Control Barrier Functions (DCBF) to address these issues. The proposed method ensures safety and precise obstacle avoidance in dynamic environments, demonstrated through superior performance in mobile manipulator experiments. Key contributions include the design of efficient DCBF functions, real-time trajectory planning under dynamic conditions, and validation of the algorithm's effectiveness, offering a significant advancement for mobile manipulators in complex work settings.

LZ4 data compression algorithm is the current state-of-art compression algorithm in the high speed compression algorithm class, and has been adopted and integrated by lots modern high-speed data storage systems. We propose a fast lossless compression algorithm, named LZ4r. A new format of the data sequence is designed, and by integrating it into the proposed algorithm, a better compression ratio than LZ4 is achieved. Numerous evaluation tests are conducted with different sets of data corpus. The results consistently show that LZ4r gains a significant improvement in compression ratio than LZ4, with a similar high compression speed. Although LZ4r is slower than LZ4 in decompression speed, the decompression speed of LZ4r is still fast enough not to reduce the overall performance of the system. Thus, LZ4r can become a practical and competitive alternative or replacement of LZ4 in many high-speed data storage systems to improve the overall performance and lower the overall cost. More details about LZ4r algorithm design and performance evaluation can be found at [1].

We propose a high-speed lossless data compression algorithm, named SnappyR. Improved upon Snappy, we design new structures of the literal and the match tokens to achieve better compression ratio than Snappy. Numerous benchmarks are conducted on different sets of data corpus. The evaluations consistently show that SnappyR provides a better compression ratio comparing to Snappy, as well as LZ4, and better than LZO in most cases. Although a little slower than Snappy, the compression and decompression speeds of SnappyR are still much higher than entropy encoding based compression algorithms, such as ZSTD, deflate or Zlib. Thus, SnappyR can become another viable replacement or alternative to Snappy, LZ4 or LZO for computing and storage systems and applications, where high-speed lossless data compression is needed. More details about SnappyR algorithm design and performance evaluation can be found at [1].

Measuring perceptual color differences (CDs) is of great importance in modern smartphone photography. Despite the long history, most CD measures have been constrained by psychophysical data of homogeneous color patches or a limited number of simplistic natural photographic images. It is thus questionable whether existing CD measures generalize in the age of smartphone photography characterized by greater content complexities and learning-based image signal processors. In this article, we put together so far the largest image dataset for perceptual CD assessment, in which the photographic images are 1) captured by six flagship smartphones, 2) altered by Photoshop, 3) post-processed by built-in filters of the smartphones, and 4) reproduced with incorrect color profiles. We then conduct a large-scale psychophysical experiment to gather perceptual CDs of 30,000 image pairs in a carefully controlled laboratory environment. Based on the newly established dataset, we make one of the first attempts to construct an end-to-end learnable CD formula based on a lightweight neural network, as a generalization of several previous metrics. Extensive experiments demonstrate that the optimized formula outperforms 33 existing CD measures by a large margin, offers reasonable local CD maps without the use of dense supervision, generalizes well to homogeneous color patch data, and empirically behaves as a proper metric in the mathematical sense. Our dataset and code are publicly available at https://github.com/hellooks/CDNet.

Measures for visual color differences (CDs) are pivotal in hardware and software upgrading of modern smartphone photography. Towards this goal, we construct currently the largest database for visual CDs of smartphone photography. Our database consists of 15, 335 natural images 1) captured by six latest flagship smartphones, 2) altered by Photoshop®, 3) post-processed by built-in filters of smartphones, and 4) reproduced with incorrect color profiles. Moreover, we conduct a large-scale psychophysical experiment to gather visual CDs of 30, 000 image pairs from 20 human subjects in a well-designed laboratory environment. Last, we apply our human-rated database to compare a total of 27 classical and recent CD metrics. We show that existing metrics are limited in assessing CDs of smartphone photography, and point out promising future directions of learning-based CD metrics.

In data storage systems, it is crucial to protect data from loss due to failures. Erasure codes lay the foundation of this protection, enabling systems to reconstruct lost data when components fail. Erasure codes can, however, impose significant performance overhead in two core operations: encoding, where parity is calculated from newly written data, and decoding, where data is reconstructed after failures. This paper focuses on improving the performance of encoding, the more frequent operation. We observed that CPU cache efficiency has great impact on the encoding performance and proposed several encoding scheduling algorithms to optimize the use of cache memory. We call the technique XOR-scheduling and demonstrate how it applies to a wide variety of existing erasure codes. To illustrate the generality of this technique, we have conducted a performance evaluation of scheduling these codes on a variety of platforms and shown that XOR-scheduling significantly improves upon the conventional approach. Hence, we believe that XOR-scheduling has great potential to have wide impact in practical storage systems.

Finite fields are widely used in constructing error-correcting codes and cryptographic algorithms. In practice, error-correcting codes use small finite fields to achieve high-throughput encoding and decoding. Conversely, cryptographic systems employ considerably larger finite fields to achieve high levels of security. We focus on developing efficient software implementations of arithmetic operations in reasonably large finite fields as needed by secure storage applications. In this article, we study several arithmetic operation implementations for finite fields ranging from GF (2 32 ) to GF (2 128 ). We implement multiplication and division in these finite fields by making use of precomputed tables in smaller fields, and several techniques of extending smaller field arithmetic into larger field operations. We show that by exploiting known techniques, as well as new optimizations, we are able to efficiently support operations over finite fields of interest. We perform a detailed evaluation of several techniques, and show that we achieve very practical performance for both multiplication and division. Finally, we show how these techniques find applications in the implementation of HAIL, a highly available distributed cloud storage layer. Using the newly implemented arithmetic operations in GF (2 64 ), HAIL improves its performance by a factor of two, while simultaneously providing a higher level of security.

Recent studies show hard disk drives fail much more often in real systems than specified in their data-sheets, and RAID-5 may not be able to provide necessary reliability for practical systems. It is desirable to have disk arrays and clustered storage systems with higher data redundancy, such as RAID-6. Meanwhile, latest research also indicates that sector failures become a threat to data reliability in storage systems. As a result, disk failures in RAID-6 systems become complex, and call for efficient decoding approaches to recover data when disk failures take place. This paper proposes a simple and efficient decoding algorithm to reconstruct data from disk failures for RAID-6 systems. First, for many well known RAID-6 codes, we provide the conditions to determine the recoverability of disk failures by using Tanner graph. The covered RAID-6 codes include X-code, EVENODD, and RDP. Then, a generic failure decoding algorithm called SCAN algorithm is derived. The SCAN algorithm is able to efficiently reconstruct data for any recoverable disk failures. Extensive performance evaluation shows the SCAN algorithm achieves higher performance than Matrix Method, another general decoding algorithm. Hence, the SCAN algorithm is an attractive decoding algorithm to be integrated into RAID-6 systems.called entire disk failure.

Generalized Reed Solomon (GRS) codes are widely used for reliability applications in computer systems like data storage and communications and thus, efficiency in encoding and decoding of GRS codes is very important for system performance. Though GRS codes provide enormous flexibility, they are computationally expensive since calculations happen in Galois fields. In this paper, we present an algorithm to reduce the number of field multiplications in the encoding process of the GRS codes by selecting good values of α and ω, the parameters of a GRS code. These values are usually set to some default value but by finding good values for these parameters using our algorithm we present here, we can impose a structure on the encoding matrix which enables significant reduction in the number of multiplications to enable efficient encoding. Our method provides from 25% to over 90% reduction in the number of multiplications depending on the code attributes.

As storage systems grow in size and complexity, various hardware and software component failures inevitably occur, resulting in disk malfunction in failures, as well as silent errors. Existing techniques and schemes overcome the failures and silent errors in a separate fashion. In this paper, we advocate using the STAR code as a unified and systematic mechanism to simultaneously tolerate failures on one disk and silent errors on another. By exploring the unique geometric structure of the STAR code, we propose a novel efficient decoding algorithm - EEL. Both theoretical and experimental performance evaluations show that EEL constantly outperforms a naive Try-and-Test approach by large factors in overall decoding throughput.

Since the inception of direct access magnetic storage about 55 years ago, data storage has both benefited from and given rise to extraordinary progress in many technological areas, including materials science, tribology, servo control and actuation, and signal processing and coding. The number of data bits that can be stored in a unit area - the areal recording density - has increased by eight orders of magnitude for harddisk magnetic storage, with compound annual growth rates at times exceeding 100%. Moreover, the cost of this form of storage has dropped by about seven orders of magnitude. For this reason, data storage has been one of the main enablers of the information technology revolution. According to a recent estimation by the technology analysis firm IDC, the amount of data created worldwide has now started to exceed the capacity of storage that is physically available. This so-called digital universe is forecasted to grow explosively and reach more than 1021bytes (1 ZB) in 2011.

In large storage systems, it is crucial to protect data from loss due to failures. Erasure codes lay the foundation of this protection, enabling systems to reconstruct lost data when components fail. Erasure codes can however impose significant performance overhead in two core operations: encoding, where coding information is calculated from newly written data, and decoding, where data is reconstructed after failures. This paper focuses on improving the performance of encoding, the more frequent operation. It does so by scheduling the operations of XOR-based erasure codes to optimize their use of cache memory. We call the technique XOR-scheduling and demonstrate how it applies to a wide variety of existing erasure codes. We conduct a performance evaluation of scheduling these codes on a variety of processors and show that XOR-scheduling significantly improves upon the traditional approach. Hence, we believe that XOR-scheduling has great potential to have wide impact in practical storage systems.

Proper data placement schemes based on erasure correcting codes are one of the most important components for a highly available data storage system. For such schemes, low decoding complexity for correcting (or recovering) storage node failures is essential for practical systems. In this paper, we describe a new coding scheme, which we call the STAR code, for correcting triple storage node failures (erasures). The STAR code is an extension of the double-erasure-correcting EVENODD code and a modification of the generalized triple-erasure-correcting EVENODD code. The STAR code is an Maximum Distance Separable (MDS) code and thus is optimal in terms of node failure recovery capability for a given data redundancy. We provide detailed STAR code decoding algorithms for correcting various triple node failures. We show that the decoding complexity of the STAR code is much lower than those of existing comparable codes; thus, the STAR code is practically very meaningful for storage systems that need higher reliability.

Efficient key distribution is an important problem for secure group communications. The communication and storage complexity of multicast key distribution problem has been studied extensively. In this paper, we propose a new multicast key distribution scheme whose computation complexity is significantly reduced. Instead of using conventional encryption algorithms, the scheme employs MDS codes, a class of error control codes, to distribute multicast key dynamically. This scheme drastically reduces the computation load of each group member compared to existing schemes employing traditional encryption algorithms. Such a scheme is desirable for many wireless applications where portable devices or sensors need to reduce their computation as much as possible due to battery power limitations. Easily combined with any key-tree-based schemes, this scheme provides much lower computation complexity while maintaining low and balanced communication complexity and storage complexity for secure dynamic multicast key distribution.

In the past few years, all manner of storage applications, ranging from disk array systems to distributed and wide-area systems, have started to grapple with the reality of tolerating multiple simultaneous failures of storage nodes. Unlike the single failure case, which is optimally handled with RAID Level-5 parity, the multiple failure case is more difficult because optimal general purpose strategies are not yet known. Erasure Coding is the field of research that deals with these strategies, and this field has blossomed in recent years. Despite this research, the decades-old Reed- Solomon erasure code remains the only space-optimal (MDS) code for all but the smallest storage systems. The best performing implementations of Reed-Solomon coding employ a variant called Cauchy Reed-Solomon coding, developed in the mid 1990’s [4]. In this paper, we present an improvement to Cauchy Reed-Solomon coding that is based on optimizing the Cauchy distribution matrix. We detail an algorithm for generating good matrices and then evaluate the performance of encoding using all implementations Reed- Solomon codes, plus the best MDS codes from the literature. The improvements over the original Cauchy Reed-Solomon codes are as much as 83% in realistic scenarios, and average roughly 10% over all cases that we tested.

Erasure codes provide space-optimal data redundancy to protect against data loss. A common use is to reliably store data in a distributed system, where erasure-coded data are kept in different nodes to tolerate node failures without losing data. In this paper, we propose a new approach to maintain ensure-encoded data in a distributed system. The approach allows the use of space efficient k-of-n erasure codes where n and k are large and the overhead n-k is small. Concurrent updates and accesses to data are highly optimized: in common cases, they require no locks, no two-phase commits, and no logs of old versions of data. We evaluate our approach using an implementation and simulations for larger systems.

We consider a fault-tolerant distributed storage system that protects data on k disks using a systematic linear (n, k) MDS code. In such a system, updates to data blocks require corresponding updates to check blocks. Concurrent fault-prone access by multiple writers can drive the system into an inconsistent state with reduced tolerance for disk failures. We show tight bounds on the erasure recoverability of an (n, k) MDS code in this scenario. The bounds depend not just on the minimum distance of the code, but also on the maximum number of concurrent faulty writers and the manner in which they attempt to update the check blocks (one at a time/all at once)

Virtually all known results of broadcast scheduling have assumed that channels are reliable without data corruption or loss. This assumption, however, is far from reality. In fact, data loss imposes severe impact on broadcast performance, as briefly shown in [9]. In this paper, we study how to systematically derive optimal broadcast schedules for random-loss channels. The key idea is to employ proper MDS codes in the schedules. We show that the proposed scheme can achieve optimal performance, in terms of expected delivery time, and is much more robust to variations of channel loss probabilities, compared to those not using codes. In addition, we study the effect of basic schedule unit and conclude that the impact is prominent when data loss presents

The broadcast domain of wireless communication is very effective in distributing information to large audiences. In this work, an efficient data broadcast has been scheduled from a server to many clients using the broadcast disk model and a simple two-channel broadcast model are examined to present some interesting scheduling results for this model.

A scheme based on priority encoded transmission (PET), in which a movie is encoded and transmitted in parallel over multiple layers is presented in this paper. Clients can "tune in" to a suitable number of layers according to their bandwidth constraints, and begin watching the movie with commensurate delays. This scheme is extended to layered PET transmissions over multiple channels to support heterogeneous clients. The schemes can be implemented both using MDS block codes or the recently discovered fountain codes. For a movie of segments the layers and the channels will be having an algorithm to determine the optimal channel-to-layer mapping

A novel solution to the reliable multicast problem is the "digital fountain" approach, in which data is encoded with an erasure protection code before transmission, and receivers can recover the original data after receiving enough distinct encoded data. This solution, however, is not desirable for streaming media schemes in which it is preferable for parts of a movie to be available for consumption before the entire movie is received. Earlier work has proposed the use of Unequal Error Protection (UEP) codes, which permit some parts of the movie to be recovered before others. Unfortunately, a straightforward implementation of this solution can incur prohibitive coding complexity.

Many applications, including web transfers, software distribution, video-on-demand, and peer-to-peer data downloads, require the retrieval of structured documents consisting of multiple components like images, video, and text. Large systems using these applications may be made more scalable by using efficient data distribution techniques like multicast, and by enabling clients to retrieve data from multiple servers in parallel.In this paper we propose a new technique for parallel retrieval of structured documents from multiple servers using priority encoded transmission, which allows some subsets of a transmission to be reconstructed before others. We discuss the application of this technique to bulk and streaming media distribution, and provide performance results from trace-based simulations.

Rate control, in conjunction with congestion control, is important and necessary to maintain both the stability of the overall network and high quality of individual data transfer flows. We study stable rate control algorithms for streaming data, based on control theory. We introduce various control rules to maintain both sending rate and receiver buffer stability. We also propose an adaptive two-state control mechanism to ensure the rate control algorithms are compatible with TCP traffics. Extensive experimental results are shown to demonstrate the effectiveness of the rate control algorithms.

We propose and analyze a new multicast scheme for delivering on-demand streaming data using unequal protection codes. The scheme allows an end user to join only one multicast channel for a data stream at any time to play out the requested data stream from its beginning after a fixed initial playout delay. The scheme tolerates packet loss during transmission, and thus, significantly reduces the cost of implementing a reliable multicast network layer to ensure delivery of all packets. Meanwhile, resource usage of the scheme, including server computing bandwidth, network bandwidth, and client's buffer space, is determined only by the original data stream length and the initial playout delay, but is independent of either the number or the arrival pattern of individual end-user requests. Thus, the scheme is totally scalable with the number of end users, fully utilizing the data delivery efficiency of a multicast network. The scheme also uses resources efficiently, e.g., with an initial playout delays of 30 s and 60 s, multicasting a 2 h video using this scheme needs only about 5.5 and 4.8 times, respectively, the server computing bandwidth and network bandwidth of those for a single unicast delivery of the same original data stream.

Server bandwidth has been identified as a major bottleneck in large video-on-demand (VoD) systems. Using multicast delivery to serve popular content helps increase scalability by making efficient use of server bandwidth. In addition, recent research has focused on proactive schemes in which the server periodically multicasts popular content without explicit requests from clients. Proactive schemes are attractive because they consume bounded server bandwidth irrespective of client arrival rate. In this work, we describe Fuzzycast, a scalable periodic multicast scheme that uses simple techniques to provide video on demand at reasonable client start-up times while consuming optimal server bandwidth. We present a theoretical analysis of its bandwidth and client buffer requirements and prove its optimality. We study the effect of variable bitrate (VBR) media on Fuzzycast performance and propose a simple extension to transmit VBR media over constant-rate channels. Finally, we solve the problem of partitioning a transmission over multiple multicast groups by considering it as a specific instance of a more widely encountered resource trade-off.

In this paper, we propose and analyze a new multicast scheme for delivering on-demand streaming data using UEP UnEqual Protection codes. The scheme allows an end user to join the multicast channel for adata stream at ,any time to play out the requested data stream from its beginning after a fixed amount of initial delay time. Resource usage of the scheme, including server computing bandwidth,network bandwidth and client's buffer space, is only determined by the original data stream length and the initial playout delay, butindependent of either the number or the arrival pattern of individual end user requests. Thus the scheme is totally scalable with the number of end users, fully utilizing the data delivery efficiency of a multicast network.The scheme also use resources efficiently, e.g., with an initial delay of 30 and 60 seconds respectively, multicasting a 2-hour video using this scheme needs respectively about 5.5 and 4.8 times server computing bandwidth and network bandwidth of that for a single unicast delivery of the same original data stream.In addition, the scheme also tolerates packet loss transmission, thus significantly reduces the cost of implementing a reliable multicast network layer to ensure delivery of all packets.

The RAIN project is a research collaboration between Caltech and NASA-JPL on distributed computing and data-storage systems for future spaceborne missions. The goal of the project is to identify and develop key building blocks for reliable distributed systems built with inexpensive off-the-shelf components. The RAIN platform consists of a heterogeneous cluster of computing and/or storage nodes connected via multiple interfaces to networks configured in fault-tolerant topologies. The RAIN software components run in conjunction with operating system services and standard network protocols. Through software-implemented fault tolerance, the system tolerates multiple node, link, and switch failures, with no single point of failure. The RAIN-technology has been transferred to Rainfinity, a start-up company focusing on creating clustered solutions for improving the performance and availability of Internet data centers. In this paper, we describe the following contributions: 1) fault-tolerant interconnect topologies and communication protocols providing consistent error reporting of link failures, 2) fault management techniques based on group membership, and 3) data storage schemes based on computationally efficient error-control codes. We present several proof-of-concept applications: a highly-available video server, a highly-available Web server, and a distributed checkpointing system. Also, we describe a commercial product, Rainwall, built with the RAIN technology.

We present a new class of MDS (maximum distance separable) array codes of size n/spl times/n (n a prime number) called X-code. The X-codes are of minimum column distance 3, namely, they can correct either one column error or two column erasures. The key novelty in X-code is that it has a simple geometrical construction which achieves encoding/update optimal complexity, i.e., a change of any single information bit affects exactly two parity bits. The key idea in our constructions is that all parity symbols are placed in rows rather than columns.

We present a class of array code of size n/spl times/l, where l=2n or 2n+1, called B-Code. The distances of the B-Code and its dual are 3 and l-1, respectively. The B-Code and its dual are optimal in the sense that i) they are maximum-distance separable (MDS), ii) they have an optimal encoding property, i.e., the number of the parity bits that are affected by change of a single information bit is minimal, and iii) they have optimal length. Using a new graph description of the codes, we prove an equivalence relation between the construction of the B-Code (or its dual) and a combinatorial problem known as perfect one-factorization of complete graphs, thus obtaining constructions of two families of the B-Code and its dual, one of which is new. Efficient decoding algorithms are also given, both for erasure correcting and for error correcting. The existence of perfect one-factorizations for every complete graph with an even number of nodes is a 35 years long conjecture in graph theory. The construction of B-Codes of arbitrary odd length will provide an affirmative answer to the conjecture.

Distributed voting is an important problem in reliable computing. In an N Modular Redundant (NMR) system, the N computational modules execute identical tasks and they need to periodically vote on their current states. In this paper, we propose a deterministic majority voting algorithm for NMR systems. Our voting algorithm uses error-correcting codes to drastically reduce the average case communication complexity. In particular, we show that the efficiency of our voting algorithm can be improved by choosing the parameters of the error-correcting code to match the probability of the computational faults. For example, consider an NMR system with 31 modules, each with a state of m bits, where each module has an independent computational error probability of 10/sup -3/. 1, this NMR system, our algorithm can reduce the average case communication complexity to approximately 1.0825 m compared with the communication complexity of 31 m of the naive algorithm in which every module broadcasts its local result to all other modules. We have also implemented the voting algorithm over a network of workstations. The experimental performance results match well the theoretical predictions.