RELIABLE INTERNET-BASED MASTER-WORKER COMPUTING IN THE PRESENCE OF MALICIOUS WORKERS
Abstract
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.
A conference version of this work appeared as [12]. This work is partially supported by the Cyprus Research Promotion Foundation Grant TΠE/ΠΔHPO(BE)/0609/05, Comunidad de Madrid grant S2009TIC-1692, and Spanish MICINN grant TIN2008–06735-C02-01.
References
- I. Abraham, D. Dolev, R. Goden, and J. Y. Halpern. Distributed computing meets game theory: Robust mechanisms for rational secret sharing and multiparty computation. In Proc. of PODC 2006, pages 53–62 . Google Scholar
-
N. Alon and J. H. Spencer , The Probabilistic Method , 2nd edn. ( J. Wiley and Sons , 2000 ) . Crossref, Google Scholar - D. P. Anderson. BOINC: A system for public-resource computing and storage. In Proc. of GRID 2004, pages 4–10 . Google Scholar
- D. P. Anderson, E. Korpela, and R. Walton. High-performance task distribution for volunteer computing. In Proc. of e-Science 2005, pages 196–203 . Google Scholar
- D. Blough and G. Sullivan. A comparison for voting strategies for fault-tolerant distributed systems. In Proc. of SRDS 1990, pages 136–145 . Google Scholar
- Siam Journal on Computing 27(5), 1457 (1998), DOI: 10.1137/S0097539793255527. Crossref, ISI, Google Scholar
- SIAM Journal on Computing 28(2), 433 (1998), DOI: 10.1137/S0097539796310102. Crossref, ISI, Google Scholar
- SIAM Journal on Computing 23(5), 1001 (1994), DOI: 10.1137/S0097539791195877. Crossref, ISI, Google Scholar
- A. Fernández Anta, C. Georgiou, and M. A. Mosteiro. Cost-sensitive Mechanisms for Internet-based Computing. In Proc. of NCA 2008, pages 315–324 . Google Scholar
- A. Fernández Anta, C. Georgiou, and M. A. Mosteiro. Algorithmic Mechanisms for Internet-based Master-Worker Computing with Untrusted and Selfish Workers. In Proc. of IPDPS 2010 . Google Scholar
- Theoretical Computer Science 333(3), 433 (2005). Crossref, ISI, Google Scholar
- A. Fernández, C. Georgiou, L. López, and A. Santos. Reliably Executing Tasks in the Presence of Untrusted Entities. In Proc. of SRDS 2006, pages 39–50 . Google Scholar
- IEEE Transactions on Information Theory 40(2), 579 (1994). Crossref, ISI, Google Scholar
- IEEE Transactions on Information Theory 34, 176 (1988). Crossref, ISI, Google Scholar
-
Ch. Georgiou and A. A. Shvartsman , Do-All Computing in Distributed Systems: Cooperation in the Presence of Adversity ( Springer , 2008 ) . Crossref, Google Scholar - N. Goyal, G. Kindler, and M. Saks. Lower bounds for the noisy broadcast problem. In Proc. of FOCS 2005, pages 40–52 . Google Scholar
- J. Grid Comput. 7, 501 (2009), DOI: 10.1007/s10723-009-9131-6. Crossref, ISI, Google Scholar
- Random Structures and Algorithms 5(3), 453 (1994), DOI: 10.1002/rsa.3240050306. Crossref, ISI, Google Scholar
- D. Kondo, F. Araujo, P. Malecot, P. Domingues, L. Silva. G. Fedak, and F. Cappello. Characterizing Result Errors in Internet Desktop Grids. In Proc. of Euro-Par 2007, pages 361–371 . Google Scholar
- K. M. Konwar, S. Rajasekaran, and A. A. Shvartsman. Robust Network Supercomputing with Malicious Processes. In Proc. of DISC 2006, pages 474–488 . Google Scholar
- Computing in Science and Engineering 3(1), 78 (2001). Crossref, ISI, Google Scholar
- IEEE Transactions on Reliability 40(5), 593 (1991), DOI: 10.1109/24.106783. Crossref, ISI, Google Scholar
- SIAM Journal on Discrete Mathematics 19(1), 96 (2005), DOI: 10.1137/S0895480103434063. Crossref, ISI, Google Scholar
- ACM Transactions on Programming Languages and Systems 4(3), 382 (1982), DOI: 10.1145/357172.357176. Crossref, ISI, Google Scholar
-
M. Mitzenmacher and E. Upfal , Probability and Computing: Randomized Algorithms and Probabilistic Analysis ( Cambridge University Press , 2005 ) . Crossref, Google Scholar - Journal of Parallel and Distributed Computing 66(3), 419 (2006), DOI: 10.1016/j.jpdc.2005.10.011. Crossref, ISI, Google Scholar
- R. Reischuk and B. Schmeltz. Reliable computation with noisy circuits and decision trees – A general n log n lower bound. In Proc. of FOCS 1991, pages 602–611 . Google Scholar
- Future Generation Computer Systems 18(4), 561 (2002), DOI: 10.1016/S0167-739X(01)00077-2. Crossref, ISI, Google Scholar
- Theoretical Computer Science 321(1), 149 (2004), DOI: 10.1016/j.tcs.2003.07.001. Crossref, ISI, Google Scholar
- M. Yurkewych, B. N. Levine, and A. L. Rosenberg. On the cost-ineffectiveness of redundancy in commercial P2P computing. In Proc. of CCS 2005, pp. 280–288 . Google Scholar


