Universally Accessible Distributed Computing on Public, Heterogeneous Networks,
Applied to the Search for Mersenne Primes

Overview

Introduction

Approach

Model

Implementation

Results

Conclusions

Going Further

References

Acknowledgements

Appendix A: Active Jobs

Appendix B: Processing Resource Applet

Appendix C: Control Server Source Code

Appendix D: Processing Resource Source Code

Appendix E: Database Source Code

Database Source Code

setup.sql

SET SQL_MODE="NO_AUTO_VALUE_ON_ZERO";

CREATE TABLE confirmed (
    seed int(10) unsigned NOT NULL,
    `time` timestamp NOT NULL default CURRENT_TIMESTAMP,
    PRIMARY KEY  (seed)
) ENGINE=InnoDB;

CREATE TABLE jobs (
    id int(10) unsigned NOT NULL auto_increment,
    `key` varchar(36) NOT NULL,
    updated timestamp NOT NULL default CURRENT_TIMESTAMP,
    started timestamp NOT NULL default '0000-00-00 00:00:00',
    PRIMARY KEY  (id),
    UNIQUE KEY `key` (`key`)
) ENGINE=InnoDB;

CREATE TABLE segment (
    `start` bigint(20) unsigned NOT NULL,
    `end` bigint(20) unsigned NOT NULL,
    job int(10) unsigned default NULL,
    generated timestamp NULL default NULL,
    PRIMARY KEY  (`start`,`end`),
    KEY job (job)
) ENGINE=InnoDB;

CREATE TABLE workbench (
    seed int(10) unsigned NOT NULL,
    iterations int(10) unsigned NOT NULL default '0',
    job int(10) unsigned default NULL,
    residue mediumblob,
    trial_division timestamp NULL default NULL,
    PRIMARY KEY  (seed),
    KEY job (job)
) ENGINE=InnoDB DEFAULT;

CREATE VIEW mds_dist_comp.open_tasks AS
select
    mds_dist_comp.workbench.seed AS seed,
    if(isnull(mds_dist_comp.workbench.trial_division),
        'Trial Division', 'Lucas-Lehmer') AS task_type,
    mds_dist_comp.workbench.iterations AS iterations,
    mds_dist_comp.jobs.started AS started,
    timediff(now(), mds_dist_comp.jobs.started) AS total_time,
    mds_dist_comp.jobs.updated AS updated,
    timediff(now(), mds_dist_comp.jobs.updated) AS since_update,
    if((isnull(mds_dist_comp.workbench.trial_division)
            or (mds_dist_comp.workbench.iterations = 0)),
            NULL, sec_to_time((mds_dist_comp.workbench.seed
            / (mds_dist_comp.workbench.iterations
            / time_to_sec(
            timediff(mds_dist_comp.jobs.updated,
            mds_dist_comp.jobs.started))))))
        AS est_total_required,
    if((isnull(mds_dist_comp.workbench.trial_division)
            or (mds_dist_comp.workbench.iterations = 0)),
            NULL, (mds_dist_comp.jobs.started
            + interval(mds_dist_comp.workbench.seed
            / (mds_dist_comp.workbench.iterations
            / time_to_sec(
            timediff(mds_dist_comp.jobs.updated,
            mds_dist_comp.jobs.started)))) second))
        AS est_finish
from
    mds_dist_comp.workbench
    join mds_dist_comp.jobs
        on mds_dist_comp.jobs.id = mds_dist_comp.workbench.job
order by
    mds_dist_comp.workbench.seed;

ALTER TABLE `segment`
    ADD CONSTRAINT segment_ibfk_1 FOREIGN KEY (job)
        REFERENCES jobs (id) ON DELETE SET NULL;

ALTER TABLE `workbench`
    ADD CONSTRAINT workbench_ibfk_1 FOREIGN KEY (job)
        REFERENCES jobs (id) ON DELETE SET NULL;

DELIMITER $$

CREATE PROCEDURE add_seed(
    seed_prime int unsigned
)
begin

    if not exists (
        select
            *
        from
            workbench
        where
            seed = seed_prime
    )
    and not exists (
        select
            *
        from
            confirmed
        where
            seed = seed_prime
    ) then

        insert into
            workbench (
                seed
            )
        values (
            seed_prime
        );

    end if;

end$$

CREATE PROCEDURE add_sieved_primes(
    lower_bound int unsigned,
    upper_bound int unsigned,
    flags mediumblob,
    job_key varchar(36)
)
begin

    declare
        rows_affected int unsigned
    default
        0;

    declare
        byte_index int unsigned
    default
        1;

    declare
        bits tinyint unsigned;

    declare
        offset tinyint unsigned;

    if exists (
        select
            *
        from
            segment
            inner join jobs
                on segment.job = jobs.id
        where
            segment.`start` = lower_bound
            and segment.`end` = upper_bound
            and jobs.`key` = job_key
    ) then

        start transaction;

        while (byte_index <= length(flags)) do

            set bits = ascii(substring(flags, - byte_index, 1));
            set offset = 0;

            while (bits > 0) do

                if ((bits & 1) = 1) then
                    call add_seed(lower_bound + 8 * (byte_index - 1) + offset);
                end if;
                set bits = bits >> 1;
                set offset = offset + 1;

            end while;

            set byte_index = byte_index + 1;

        end while;

        update
            segment
            inner join jobs
                on segment.job = jobs.id
        set
            segment.generated = current_timestamp
        where
            segment.`start` = lower_bound
            and segment.`end` = upper_bound
            and jobs.`key` = job_key;

        delete from
            jobs
        using
            jobs
            inner join segment
                on segment.job = jobs.id
            where
                segment.`start` = lower_bound
                and segment.`end` = upper_bound
                and jobs.`key` = job_key;

        set rows_affected = row_count();

        if (rows_affected = 0) then
            rollback;
        else
            call preconfirm_mersenne_primes();
            commit;
        end if;

    end if;

end$$

CREATE PROCEDURE assign_lucas_lehmer_task(
    expiration int unsigned
)
begin

    declare
        job_id int unsigned;

    call delete_expired_jobs(expiration);

    start transaction;

    insert
        jobs (
            `key`,
            started
        )
    values (
        uuid(),
        current_timestamp
    );

    set job_id = last_insert_id();

    update
        workbench
    set
        job = job_id
    where
        job is null
        and trial_division is not null
    order by
        seed
    limit 1;

    if (row_count() = 0) then
        rollback;
    else
        commit;
    end if;

    select
        workbench.seed,
        workbench.iterations,
        workbench.residue,
        jobs.`key`
    from
        workbench
        inner join jobs
            on jobs.id = workbench.job
    where
        workbench.job = job_id;

end$$

CREATE PROCEDURE assign_sieve_task(
    expiration int unsigned,
    segment_size int unsigned
)
begin

    declare
        job_id int unsigned;

    call delete_expired_jobs(expiration);

    start transaction;

    insert
        jobs (
            `key`,
            started
        )
    values (
        uuid(),
        current_timestamp
    );

    set job_id = last_insert_id();

    if not exists (
        select
            *
        from
            segment
    ) then

        insert into
            segment (
                start,
                end,
                job
            )
        values (
            0,
            segment_size,
            job_id
        );

    elseif exists (
        select
            *
        from
            segment
        where
            job is null
            and generated is null
    ) then

        update
            segment
        set
            job = job_id
        where
            job is null
            and generated is null
        order by
            segment.`start`
        limit 1;

    else

        insert into
            segment (
                start,
                end,
                job
            )
        select
            ifnull(max(end), 0),
            ifnull(max(end), 0) + segment_size,
            job_id
        from
            segment;

    end if;

    if (row_count() = 0) then
        rollback;
    else
        commit;
    end if;

    select
        segment.start,
        segment.end,
        jobs.`key`
    from
        segment
        inner join jobs
            on jobs.id = segment.job
    where
        segment.job = job_id;

end$$

CREATE PROCEDURE assign_trial_division_task(
    expiration int unsigned
)
begin

    declare
        job_id int unsigned;

    call delete_expired_jobs(expiration);

    start transaction;

    insert
        jobs (
            `key`,
            started
        )
    values (
        uuid(),
        current_timestamp
    );

    set job_id = last_insert_id();

    update
        workbench
    set
        job = job_id
    where
        job is null
        and trial_division is null
    order by
        seed
    limit 1;

    if (row_count() = 0) then
        rollback;
    else
        commit;
    end if;

    select
        workbench.seed,
        jobs.`key`
    from
        workbench
        inner join jobs
            on jobs.id = workbench.job
    where
        workbench.job = job_id;

end$$

CREATE PROCEDURE confirm_mersenne_prime(
    seed_prime int unsigned,
    is_prime bool,
    job_key varchar(36)
)
begin

    start transaction;

    if (is_prime) then

        insert into
            confirmed (
                seed
            )
        select
            seed_prime
        from
            workbench
            inner join jobs
                on jobs.id = workbench.job
        where
            workbench.seed = seed_prime
            and jobs.`key` = job_key;

    end if;

    delete from
        workbench, jobs
    using
        workbench
        inner join jobs
            on jobs.id = workbench.job
    where
        workbench.seed = seed_prime
        and jobs.`key` = job_key;

    commit;

end$$

CREATE PROCEDURE confirm_possible_prime(
    seed_prime int unsigned,
    is_possible_prime bool,
    job_key varchar(36)
)
begin

    start transaction;

    if (not is_possible_prime) then

        delete from
            workbench
        using
            workbench
            inner join jobs
                on jobs.id = workbench.job
        where
            workbench.seed = seed_prime
            and jobs.`key` = job_key;

    else

        update
            workbench
            inner join jobs
                on jobs.id = workbench.job
        set
            workbench.trial_division = current_timestamp
        where
            workbench.seed = seed_prime
            and jobs.`key` = job_key;

    end if;

    if (row_count() = 0) then

        rollback;

    else

        delete from
            jobs
        where
            jobs.`key` = job_key;

        commit;

    end if;

end$$

CREATE PROCEDURE delete_expired_jobs(
    expiry_interval int unsigned
)
begin

    delete from
        jobs
    where
        date_add(updated, interval expiry_interval second) < current_timestamp;

end$$

CREATE PROCEDURE preconfirm_mersenne_primes()
begin

    insert
        confirmed (
            seed
        )
    select
        workbench.seed
    from
        workbench
        inner join workbench workbench2
            on ((1 << workbench.seed) - 1) = workbench2.seed
        left join confirmed
            on workbench.seed = confirmed.seed
    where
        confirmed.seed is null;

    delete from
        workbench, jobs
    using
        workbench
        inner join confirmed
            on workbench.seed = confirmed.seed
        left join jobs
            on jobs.id = workbench.job;

end$$

CREATE PROCEDURE update_lucas_lehmer_status(
    seed_prime int unsigned,
    current_iterations int unsigned,
    current_residue mediumblob,
    job_key varchar(36)
)
begin

    update
        workbench
        inner join jobs
            on jobs.id = workbench.job
    set
        workbench.iterations = current_iterations,
        workbench.residue = current_residue,
        jobs.updated = current_timestamp
    where
        workbench.seed = seed_prime
        and jobs.`key` = job_key;

end$$

DELIMITER ;