CS 269S, Spring 2014: Theory Seminar
ICS Building, Room 243, 1pm
April 11, 2013:

Asynchronous adaptive task allocation

Sotirios Kentros

We present a randomized algorithm for asynchronous task allocation, also known as the write-all or do-all problem. Our algorithm has work complexity of O(n + k2log3k) with high probability, where n is the number of tasks and k is the number of processes that participate in the computation. This is the first adaptive solution for the write-all problem that has work n plus some additive term which depends only on the number of participating processes k and not the size of the problem n.

(Joint work with Chadi Kari, Aggelos Kiayias, and Alexander Russell.)