Distributed Programming with Tasks

[摘要] In centralized computing we can compute a function composing a sequence of elementary functions, where the output of the $i$-th function in the sequence is the input to the $i+1$-st function in the sequence. We notice that this computation is done without creating ``side-effects'' between function invocations. Can we do the same for distributed computing -- show that a task (the analogue of a function for distributed computing) can be computed through a sequence of elementary tasks, where each process invokes the $i+1$-st task with its output from the $i$-th task? That is, show that any distributed computing model canbe associated with an \emph{iterated model} consisting of some base tasks, so that any task solvable in the model is solvable by invoking a sequence of the base tasks one after the other?This paper considers the wait-free case, and takes a significant step in enlarging the set of models for which the answer to this question is positive. This completes the proof of the outstanding conjecture stating that the read-write model equipped with the renaming task is strictly weaker than the same model equipped with the set agreement task. This was proved in DISC2006 \cite{GRH06} assuming this conjecture to be true.It was shown in PODC97 \cite{BG97}, that any task solvable in read-write shared memory, can be solved by a sequence of tasks each of which is the snapshot task $S$. Here we show that if a task $T$ is solvable when we equip the read-write model with any set of base tasks ${\cal T}$, where each member of ${\cal T}$ is solvable by set agreement, then $T$ is solvable by a sequence of tasksfrom $\{S\} \cup \{{\cal T}\}$.

[发布机构] UCLA Henry Samueli School of Engineering and Applied Science

[学科分类] 计算机科学（综合）