Accountable Web-computing

We develop a computationally lightweight scheme. for enhancing security when sharing a massive "bag of tasks" on the Web, by enabling the tasks owner to keep track of which "volunteer" computed which tasks. The scheme combines a directory that dynamically assigns names to volunteers, who can arrive and depart at will, with a directly computed task allocation function (TAF) that assigns tasks to each volunteer-name from a reserved "sub-bag." We design a methodology for constructing easily computed additive TAFs (ATAFs), which assign each volunteer-name υ a base task B_υ and a stride S_υ and then index every sub-bag by an arithmetic progression: B_υ, B_υ+S_υ, B_υ+2S_υ, .... The scheme ensures that faster volunteers are always assigned smaller strides, thereby simplifying the management of the memory where tasks reside. We seek to simplify memory management further by striving for ATAFs whose strides S_υ grow slowly as a function of υ. We present a sequence of ATAFs whose strides grow progressively slower; with only modest concomitant increase in computational complexity: The sequence ranges from easily computed ATAFs whose strides grow exponential v, to slightly more complex ATAFs whose strides grow quadratically to somewhat complex ATAFs whose strides grow subquadratically.