TY - GEN
T1 - Distributed Cooperation and Adversity
T2 - PCK50: Principles of Computing and Knowledge: Paris C. Kanellakis Memorial Workshop
AU - Georgiou, Chryssis
AU - Russell, Alexander
AU - Shvartsman, Alex A.
N1 - DBLP License: DBLP's bibliographic metadata records provided through http://dblp.org/ are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.
PY - 2003
Y1 - 2003
N2 - The problem of cooperatively performing a collection of tasks in a decentralized setting where the computing medium is subject to adversarial perturbations is one of the fundamental problems in distributed computing. Such perturbations can be caused by processor failures, unpredictable delays, and communication breakdowns. To develop efficient distributed solutions for computation problems ranging from distributed search such as SETI to parallel simulation and multi-agent collaboration, it is important to understand efficiency trade-offs characterizing the ability of p processors to cooperate on t-tasks in the presence of adversity. This paper surveys recent results grouped by the following topics: (i) failure-sensitive bounds for distributed cooperation problems for synchronous processors subject to crash failures, (ii) bounds on redundant work for distributed cooperation when individual asynchronous processors may experience prolonged absence of communication, and (in) competitive analysis of cooperative work performed by groups of asynchronous processors, when the groups may be fragmented and merged during the computation. These research results are motivated by the earlier work of the third author with Paris C. Kanellakis at Brown University.
AB - The problem of cooperatively performing a collection of tasks in a decentralized setting where the computing medium is subject to adversarial perturbations is one of the fundamental problems in distributed computing. Such perturbations can be caused by processor failures, unpredictable delays, and communication breakdowns. To develop efficient distributed solutions for computation problems ranging from distributed search such as SETI to parallel simulation and multi-agent collaboration, it is important to understand efficiency trade-offs characterizing the ability of p processors to cooperate on t-tasks in the presence of adversity. This paper surveys recent results grouped by the following topics: (i) failure-sensitive bounds for distributed cooperation problems for synchronous processors subject to crash failures, (ii) bounds on redundant work for distributed cooperation when individual asynchronous processors may experience prolonged absence of communication, and (in) competitive analysis of cooperative work performed by groups of asynchronous processors, when the groups may be fragmented and merged during the computation. These research results are motivated by the earlier work of the third author with Paris C. Kanellakis at Brown University.
KW - Competitive analysis
KW - Distributed algorithms
KW - Fault-tolerance
KW - Partitionable networks
KW - Performing tasks
KW - Scheduling
KW - Work complexity
UR - http://www.scopus.com/inward/record.url?scp=0141929290&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0141929290&partnerID=8YFLogxK
U2 - 10.1145/778348.778358
DO - 10.1145/778348.778358
M3 - Conference contribution
AN - SCOPUS:0141929290
SN - 1581136048
T3 - Principles of Computing and Knowledge: Paris C. Kanellakis Memorial Workshop
SP - 60
EP - 71
BT - Principles of Computing and Knowledge
Y2 - 8 June 2003 through 8 June 2003
ER -