Home Maintained by HueStones
SourceForge.net Logo Make a donation

MBound - A Memory Bound Pricing Function


Please note: MBound implementation and associated table files are provided with PennyPost solely for educational purposes to be used for learning about memory bound functions. No commercial use of this algorithm is implied or suggested. To use this algorithm for any other purpose you may need permission from Microsoft.

MBound is a memory bound PricingFunction proposed by Cynthia Dwork, Andrew Goldberg, Moni Naor.
More details about this algorithm can be found here and the complete Java implementation is here.

MBound requires two fixed-forever tables of 32-bit unsigned random integers. One of the tables is 16MB and the other 1KB. To make your implementation of memory bound compatible with PennyPost you will need to use the table definitions downloadable here. These are released under the LGPL version 3.

Sample java code to read these files is as below:
import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.DataInputStream;
import java.io.DataOutputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;

 /**
 * This class uses longs (64 bits) instead of integers (32-bits) because JAVA
 * does not support unsigned integers, so the only way to store a 32 bit
 * unsigned number is inside a long. NOTE: All calculations are done assuming
 * only 32 bits in the long value
 */

public final class SampleTableLoader {
    /**
     * Size of T is 2^22 i.e. 16 MBytes
     */

    public static final int m_iSizeOfArrayT = 0x400000;

    /**
     * Size of A is 256
     */

    public static final int m_iSizeOfArrayA = 256;

    /**
     * The fixed-forever array - will be populated by populateFixedArrays() This
     * array requires 16 MB and dominates the space needs of our memory-bound
     * function.
     *
     * Keeping them static means there will be only one for all objects this is
     * OK as once populated these are only to be read from and never written
     * into.
     */

    public static long[] m_fixedArrayT = new long[m_iSizeOfArrayT];
    public static long[] m_fixedArrayA0 = new long[m_iSizeOfArrayA];

    /**
     * Populates T(m_fixedArrayT) and A0(m_fixedArrayA0) from files
     */

    public synchronized void populateFixedArrays() {
        if (m_bFixedArraysPopulated)
            return;

        // both these are loaded from the jar or classpath and located
        // inside the "tab" folder within the jar or classpath
        final String fileNameT = "tab/functionT.dat";
        final String fileNameA = "tab/functionA.dat";

        DataInputStream in;
        in = new DataInputStream(new BufferedInputStream(getClass()
                .getClassLoader().getResourceAsStream(fileNameT)));

        try {
            for (int i = 0; i < m_iSizeOfArrayT; i++) {
                m_fixedArrayT[i] = in.readInt() & 0xFFFFFFFFL;
            }
        } catch (IOException e) {
            throw new IllegalArgumentException(e);
        } finally {
            try {
                in.close();
            } catch (IOException e) {
            }
        }

        in = new DataInputStream(new BufferedInputStream(getClass()
                .getClassLoader().getResourceAsStream(fileNameA)));

        try {
            for (int i = 0; i < m_iSizeOfArrayA; i++) {
                m_fixedArrayA0[i] = in.readInt() & 0xFFFFFFFFL;
            }
        } catch (IOException e) {
            //TODO: Handle this exception as appropriate
        } finally {
            try {
                in.close();
            } catch (IOException e) {
            }
        }
    }
}



CategoryImplementationDocs
Creative Commons License
Penny Post Documentation by Aliasgar Lokhandwala is licensed under a Creative Commons Attribution-Non-Commercial-Share Alike 3.0 License.
Valid XHTML 1.0 Transitional :: Valid CSS :: Powered by Wikka Wakka Wiki
Page was generated in 1.4515 seconds