Algebraic Signatures for Scalable

Signatures detect changes to the data objects. Numerous schemes are known, e.g., the popular hash based SHA-1 standard. We propose a novel scheme we call algebraic signatures. We use the algebraic calculus in a Galois Field. One major consequence, new for any known signature scheme, is sure detection of limited changes of parameterized size. More precisely, we detect for sure any change that does not exceeds n-symbols for an nsymbol signature. For larger changes, the collision probability is typically insignificant, as for the other known schemes. We apply the algebraic signatures to the Scalable Distributed Data Structures (SDDSs). We filter at the SDDS client node the updates that do not actually change the records. We also manage the concurrent updates to data stored in the SDDS RAM buckets at the server nodes. We further use the scheme for the fast disk backup of these buckets. We sign our objects with 4-byte signatures, instead of 20-byte standard SHA-1 signatures that would be impractical for us. Our algebraic calculus is then also about twice as fast. We present the theory of the scheme, discuss the implementation in our SDDS-2000 prototype, overview the performance, and directions for further work