World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

RELIABLE INTERNET-BASED MASTER-WORKER COMPUTING IN THE PRESENCE OF MALICIOUS WORKERS

    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 ) . CrossrefGoogle 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
    • C. Dwork, J. Halpern and O. Waarts, Siam Journal on Computing 27(5), 1457 (1998), DOI: 10.1137/S0097539793255527. Crossref, ISIGoogle Scholar
    • W. S. Evans and N. Pippenger, SIAM Journal on Computing 28(2), 433 (1998), DOI: 10.1137/S0097539796310102. Crossref, ISIGoogle Scholar
    • U. Feigeet al., SIAM Journal on Computing 23(5), 1001 (1994), DOI: 10.1137/S0097539791195877. Crossref, ISIGoogle 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
    • A. Fernándezet al., Theoretical Computer Science 333(3), 433 (2005). Crossref, ISIGoogle 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
    • P. Gács and A. Gál, IEEE Transactions on Information Theory 40(2), 579 (1994). Crossref, ISIGoogle Scholar
    • R. G. Gallanger, IEEE Transactions on Information Theory 34, 176 (1988). Crossref, ISIGoogle Scholar
    • Ch.   Georgiou and A. A.   Shvartsman , Do-All Computing in Distributed Systems: Cooperation in the Presence of Adversity ( Springer , 2008 ) . CrossrefGoogle 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
    • E. M. Heien, D. P. Anderson and K. Hagihara, J. Grid Comput. 7, 501 (2009), DOI: 10.1007/s10723-009-9131-6. Crossref, ISIGoogle Scholar
    • C. Kenyon and V. King, Random Structures and Algorithms 5(3), 453 (1994), DOI: 10.1002/rsa.3240050306. Crossref, ISIGoogle 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
    • E. Korpelaet al., Computing in Science and Engineering 3(1), 78 (2001). Crossref, ISIGoogle Scholar
    • A. Kumar and K. Malik, IEEE Transactions on Reliability 40(5), 593 (1991), DOI: 10.1109/24.106783. Crossref, ISIGoogle Scholar
    • E. Kushilevitz and Y. Mansour, SIAM Journal on Discrete Mathematics 19(1), 96 (2005), DOI: 10.1137/S0895480103434063. Crossref, ISIGoogle Scholar
    • L. Lamport, R. Shostak and M. Pease, ACM Transactions on Programming Languages and Systems 4(3), 382 (1982), DOI: 10.1145/357172.357176. Crossref, ISIGoogle Scholar
    • M.   Mitzenmacher and E.   Upfal , Probability and Computing: Randomized Algorithms and Probabilistic Analysis ( Cambridge University Press , 2005 ) . CrossrefGoogle Scholar
    • M. Paquette and A. Pelc, Journal of Parallel and Distributed Computing 66(3), 419 (2006), DOI: 10.1016/j.jpdc.2005.10.011. Crossref, ISIGoogle 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
    • L. Sarmenta, Future Generation Computer Systems 18(4), 561 (2002), DOI: 10.1016/S0167-739X(01)00077-2. Crossref, ISIGoogle Scholar
    • M. Szegedy and X. Chen, Theoretical Computer Science 321(1), 149 (2004), DOI: 10.1016/j.tcs.2003.07.001. Crossref, ISIGoogle 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