Reliable internet-based master-worker computing in the presence of malicious workers
Ημερομηνία
2012Source
Parallel Processing LettersVolume
22Issue
1Google Scholar check
Keyword(s):
Metadata
Εμφάνιση πλήρους εγγραφήςΕπιτομή
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 free for 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.
Collections
Cite as
Related items
Showing items related by title, author, creator and subject.
-
Conference Object
Mobile commerce: Vision and challenges (location and its management)
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 ...
-
Article
Computer-aided diagnosis in hysteroscopic imaging
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, ...
-
Article
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)