Reliable internet-based master-worker computing in the presence of malicious workers
SourceParallel Processing Letters
Google Scholar check
MetadataShow full item record
We consider a Master-Worker distributed system where a master processor assigns, over the Internet, tasks to a collection of n workers, which are untrusted and might act maliciously. In addition, a worker may not reply to the master, or its reply may not reach the master, due to unavailabilities or failures of the worker or the network. Each task returns a value, and the goal is for the master to accept only correct values with high probability. Furthermore, we assume that the service provided by the workers is not freefor each task that a worker is assigned, the master is charged with a work-unit. Therefore, considering a single task assigned to several workers, our objective is to have the master processor to accept the correct value of the task with high probability, with the smallest possible amount of work (number of workers the master assigns the task). We probabilistically bound the number of faulty processors by assuming a known probability p >1/2 of any processor to be faulty. Our work demonstrates that it is possible to obtain, with provable analytical guarantees, high probability of correct acceptance with low work. In particular, we first show lower bounds on the minimum amount of (expected) work required, so that any algorithm accepts the correct value with probability of success 1 - ε, where ε >1 (e.g., 1/n). Then we develop and analyze two algorithms, each using a different decision strategy, and show that both algorithms obtain the same probability of success 1 - ε, and in doing so, they require similar upper bounds on the (expected) work. Furthermore, under certain conditions, these upper bounds are asymptotically optimal with respect to our lower bounds. © 2012 World Scientific Publishing Company.
Showing items related by title, author, creator and subject.
Samaras, George S. (Institute of Electrical and Electronics Engineers Inc., 2002)Mobile computing is distributed computing that involves elements whose location changes in the course of computation. Elements may be software components such as mobile agents or moving objects-data or hardware such as ...
Neofytou, Marios S.; Tanos, Vasilios; Constantinou, Ioannis P.; Kyriacou, Efthyvoulos C.; Pattichis, Marios S.; Pattichis, Constantinos S. (2015)The paper presents the development of a computeraided diagnostic (CAD) system for the early detection of endometrial cancer. The proposed CAD system supports reproducibility through texture feature standardization, ...
Grid Computing : Second European AcrossGrids Conference, AxGrids 2004, Nicosia, Cyprus, January 28-30, 2004. Revised Papers European Across, Grids Conference; Dikaiakos, Marios D.; European Across, Grids Conference; Dikaiakos, Marios D.; SpringerLink (Online service); European Across, Grids Conference (2004)