4.4 Article

Applying the dynamics of evolution to achieve reliability in master-worker computing

Journal

CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE
Volume 25, Issue 17, Pages 2363-2380

Publisher

WILEY
DOI: 10.1002/cpe.3104

Keywords

performing tasks; Internet-based computing; evolutionary dynamics; reinforcement learning; algorithmic mechanism design

Funding

  1. Cyprus Research Promotion Foundation [TPiE/PiLambdaHPO/0609(BE)/05]
  2. National Science Foundation [CCF-0937829, CCF-1114930]
  3. Comunidad de Madrid [S2009TIC-1692, MODELICO-CM]
  4. Spanish PRODIEVO grant
  5. Spanish RESINEE grant
  6. MICINN [TEC2011-29688-C02-01]
  7. National Natural Science Foundation of China [61020106002]
  8. Direct For Computer & Info Scie & Enginr
  9. Division of Computing and Communication Foundations [1114930] Funding Source: National Science Foundation
  10. Direct For Computer & Info Scie & Enginr
  11. Division of Computing and Communication Foundations [1114809] Funding Source: National Science Foundation

Ask authors/readers for more resources

We consider Internet-based master-worker task computations, such as SETI@home, where a master process sends tasks, across the Internet, to worker processes; workers execute and report back some result. However, these workers are not trustworthy, and it might be at their best interest to report incorrect results. In such master-worker computations, the behavior and the best interest of the workers might change over time. We model such computations using evolutionary dynamics, and we study the conditions under which the master can reliably obtain task results. In particular, we develop and analyze an algorithmic mechanism based on reinforcement learning to provide workers with the necessary incentives to eventually become truthful. Our analysis identifies the conditions under which truthful behavior can be ensured and bounds the expected convergence time to that behavior. The analysis is complemented with illustrative simulations. Copyright (c) 2013 John Wiley & Sons, Ltd.

Authors

I am an author on this paper
Click your name to claim this paper and add it to your profile.

Reviews

Primary Rating

4.4
Not enough ratings

Secondary Ratings

Novelty
-
Significance
-
Scientific rigor
-
Rate this paper

Recommended

Article Statistics & Probability

Detecting and classifying outliers in big functional data

Oluwasegun Taiwo Ojo, Antonio Fernandez Anta, Rosa E. Lillo, Carlo Sguera

Summary: This study introduces two new outlier detection methods, "Semifast-MUOD" and "Fast-MUOD", which are based on the existing MUOD method. Evaluation results demonstrate significant improvements in outlier detection and computational time for the proposed methods, with Fast-MUOD particularly suitable for big and dense functional datasets.

ADVANCES IN DATA ANALYSIS AND CLASSIFICATION (2022)

Article Multidisciplinary Sciences

Beyond Dunbar circles: a continuous description of social relationships and resource allocation

Ignacio Tamarit, Angel Sanchez, Jose A. Cuesta

Summary: This paper discusses resource allocation problems in human relationship patterns using a new formalism that allows for continuous values of resource costs. The study shows that there is a characteristic parameter eta, analogous to the ratio of relationships between adjacent circles in the discrete case, which has a value similar to 6. The findings suggest the existence of a universal feature in how humans manage relationships, and that online personal networks mirror offline relationship structures.

SCIENTIFIC REPORTS (2022)

Article Multidisciplinary Sciences

Ethnic markers and the emergence of group-specific norms: an experiment

Juan Ozaita, Andrea Baronchelli, Angel Sanchez

Summary: Visible markers have minimal impact on promoting cooperation, calling for further research.

SCIENTIFIC REPORTS (2022)

Article Computer Science, Information Systems

Automated identification of network anomalies and their causes with interpretable machine learning: The CIAN methodology and TTrees implementation

Mohamed Moulay, Rafael Garcia Leiva, Pablo J. Rojo Maroni, Fernando Diez, Vincenzo Mancuso, Antonio Fernandez Anta

Summary: CIAN is a practical and interpretable ML methodology designed to automate the identification of performance anomalies in cellular networks, using unsupervised learning and combining multiple ML algorithms and data analysis tools. Experimental results show that TTrees implementation of CIAN can automatically identify and accurately classify network anomalies, facilitating precise troubleshooting actions.

COMPUTER COMMUNICATIONS (2022)

Article Economics

Paid and hypothetical time preferences are the same: lab, field and online evidence

Pablo Branas-Garza, Diego Jorrat, Antonio M. Espin, Angel Sanchez

Summary: The use of real decision-making incentives in economic experiments remains controversial. This study analyzes data from lab experiments in Spain and field and online experiments in Nigeria and the UK, finding that the use of hypothetical or real payments has minimal impact on the elicitation of short-term and long-term discounting.

EXPERIMENTAL ECONOMICS (2023)

Article Multidisciplinary Sciences

The effectiveness of prosocial policies: Gender differences arising from social norms

Antonio Cabrales, Ryan Kendall, Angel Sanchez

Summary: This study examines policies aimed at reducing negative externalities and explores their differential impact on genders. Through a driving experiment, it is found that slower driving speeds are the safest option, while faster speeds have higher potential payoffs but also higher accident probabilities. The study further reveals that policies utilizing different framing and endogenously determined punishment mechanisms are only effective for female drivers.

PLOS ONE (2022)

Article Economics

Social interaction and negotiation outcomes: An experimental approach*

Pablo Branas-Garza, Antonio Cabrales, Guillermo Mateu, Angel Sanchez, Angela Sutan

Summary: This study experimentally examines the impact of pre-play social interactions on negotiations, including conversations, food, and beverages. The results show that none of these interaction components significantly improve negotiation outcomes compared to no interaction. The study also finds no superiority of interaction in terms of trust and reciprocity.

JOURNAL OF BEHAVIORAL AND EXPERIMENTAL ECONOMICS (2023)

Article Multidisciplinary Sciences

Triadic influence as a proxy for compatibility in social relationships

Miguel Ruiz-Garcia, Juan Ozaita, Maria Pereda, Antonio Alfonso, Pablo Branas-Garza, Jose A. Cuesta, Angel Sanchez

Summary: Networks of social interactions are crucial for civilizations, but the quantitative understanding of them is still limited. This study examines real social networks in 13 schools, involving over 3,000 students and 60,000 relationships. The triadic influence metric is introduced to measure the impact of nearest neighbors, which outperforms personal traits in predicting relationship signs.

PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA (2023)

Article Multidisciplinary Sciences

Network coevolution drives segregation and enhances Pareto optimal equilibrium selection in coordination games

Miguel A. Gonzalez Casado, Angel Sanchez, Maxi San Miguel

Summary: In this work, the authors assess the role of the adaptation of the interaction network among agents in reaching global coordination and equilibrium selection. They find that the system exhibits fragmentation before reaching full coordination, but coevolution enhances the selection of payoff-dominant equilibrium in a coordination game with risk. Moreover, there is an intermediate range of plasticity values where the system fully coordinates on a single component network.

SCIENTIFIC REPORTS (2023)

Article Statistics & Probability

Multivariate functional outlier detection using the fast massive unsupervised outlier detection indices

Oluwasegun Taiwo Ojo, Antonio Fernandez Anta, Marc G. G. Genton, Rosa E. E. Lillo

Summary: This article introduces the definitions and properties of the fast massive unsupervised outlier detection (FastMUOD) indices in functional data. FastMUOD detects outliers by calculating amplitude, magnitude, and shape indices for each curve to target the corresponding types of outliers. Several methods adapting FastMUOD to outlier detection in multivariate functional data are proposed, including applying FastMUOD on the components of the multivariate data and using random projections. Furthermore, these techniques are tested on various simulated and real multivariate functional datasets. Compared with the state of the art in multivariate functional OD, the use of random projections showed the most effective results with similar, and in some cases improved, OD performance. Based on the proportion of random projections that flag each multivariate function as an outlier, a new graphical tool called the magnitude-shape-amplitude (MSA) plot is proposed for visualizing the magnitude, shape, and amplitude outlyingness of multivariate functional data.
Article Humanities, Multidisciplinary

Disentangling material, social, and cognitive determinants of human behavior and beliefs

Denis Tverskoi, Andrea Guido, Giulia Andrighetto, Angel Sanchez, Sergey Gavrilets

Summary: In social interactions, human decision-making, attitudes, and beliefs about others are influenced by factors such as cognitive processes, social influences, and cost-benefit considerations. This study aims to understand these dynamics by using mathematical modeling and an online behavioral experiment. The results show that personal norms and conformity with peers have the largest impact on decision-making, while material benefits and normative expectations have smaller effects. Messaging can change these dynamics by decreasing personal norms and increasing conformity. The study highlights the importance of understanding the dynamics of personal beliefs and beliefs about others in social behavior.

HUMANITIES & SOCIAL SCIENCES COMMUNICATIONS (2023)

Article Multidisciplinary Sciences

A reinforcement learning approach to explore the role of social expectations in altruistic behavior

Rosendo Castanon, Fco. Alberto Campos, Jose Villar, Angel Sanchez

Summary: This paper proposes an agent-based model that utilizes the Bush-Mosteller reinforcement learning algorithm to investigate the role of social expectations in the emergence of altruistic behavior. The model is compared with experimental results, and the findings suggest that a stimuli model based on empirical and normative expectations has potential in understanding decision-making processes in contexts where cooperative behavior is relevant.

SCIENTIFIC REPORTS (2023)

Article Multidisciplinary Sciences

On the interplay of hierarchies, conflicts, and cooperation: An experimental approach

Pablo Lozano, Alberto Antonioni, Angel Sanchez

Summary: This study uses online human experiments to investigate the effects of hierarchical structures on cooperation and conflict within groups. The results show that cooperation can be maintained through dyadic conflicts that punish noncooperators, leading to stable hierarchical groups with high levels of cooperation. These findings align with earlier theoretical models and provide insights into the relationship between hierarchy, cooperation, and conflict.

PNAS NEXUS (2023)

Article Multidisciplinary Sciences

On the interplay of hierarchies, conflicts, and cooperation: An experimental approach

Pablo Lozano, Alberto Antonioni, Angel Sanchez

Summary: This study used online human experiments to investigate the effects of hierarchy on cooperation and conflict within groups. The results showed that cooperation can be maintained through participating in conflicts, leading to stable hierarchical groups with high levels of cooperation.

PNAS NEXUS (2023)

Article Multidisciplinary Sciences

Structural measures of personal networks predict migrants' cultural backgrounds: an explanation from Grid/Group theory

Jose Luis Molina, Juan Ozaita, Ignacio Tamarit, Angel Sanchez, Christopher McCarty, H. Russell Bernard

Summary: Culture and social structure are intertwined phenomena observable in personal networks, and can be predicted by specific combinations of personal network structural measures such as closeness, clustering, betweenness, and average degree. The findings support the theory of Grid/Group that emphasizes the interdependence of social structural and cultural features.

PNAS NEXUS (2022)

No Data Available