Author name cluster
Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.
AAMAS Conference 2025 Conference Paper
In this work we present the idea of partitioning contestants into disjoint groups, each competing in an independent contest, with its own prize. We focus on binary contests, wherein contestants choose whether or not to participate, and show that such contest partitioning can benefit the organizer running the contest when partitioning entails a cost.
ECAI Conference 2025 Conference Paper
We consider a setting where goods are allocated to agents by way of an allocation platform (e. g. , a matching platform). An “allocation facilitator” aims to increase the overall utility/social-good of the allocation by encouraging (some of the) agents to relax (some of) their restrictions. At the same time, the advice must not hurt agents who would otherwise be better off. Additionally, the facilitator may be constrained by a “bound” (a. k. a. ‘budget’), limiting the number and/or type of restrictions it may seek to relax. We consider the facilitator’s optimization problem of choosing an optimal set of restrictions to request to relax under the aforementioned constraints. Our contributions are three-fold: (i) We provide a formal definition of the problem, including the participation guarantees to which the facilitator should adhere. We define a hierarchy of participation guarantees and also consider several social-good functions. (ii) We provide polynomial algorithms for solving various versions of the associated optimization problems, including one-to-one and many-to-one allocation settings. (iii) We demonstrate the benefits of such facilitation and relaxation, and the implications of the different participation guarantees, using extensive experimentation on three real-world datasets.
AAAI Conference 2025 Conference Paper
Multi-Robot Coverage problems have been extensively studied in robotics, planning and multi-agent systems. In this work, we consider the coverage problem when there are constraints on the proximity (e.g., maximum distance between the agents, or a blue agent must be adjacent to a red agent) and the movement (e.g., terrain traversability and material load capacity) of the robots. Such constraints naturally arise in many real-world applications, e.g. in search-and-rescue and maintenance operations. Given such a setting, the goal is to compute a covering tour of the graph with a minimum number of steps, and that adheres to the proximity and movement constraints. For this problem, our contributions are four: (i) a formal formulation of the problem, (ii) an exact algorithm that is FPT in parameters ||F||, d and ω - the set of robot formations that encode the proximity constraints, the maximum nodes degree, and the tree-width of the graph, respectively, (iii) for the case that the graph is a tree: a PTAS approximation scheme, that given an ε produces a tour that is within a 1+ ε⋅error(||F||, d)) of the optimal one, and the computation runs in time poly(n) ⋅ h(1/ε, ||F||). (iv) for the case that the graph is a tree, with k=3 robots, and the constraint is that all agents are connected: a PTAS scheme with multiplicative approximation error of 1 + O(ε), independent of d.
AAAI Conference 2025 Conference Paper
Two prominent objectives in social choice are utilitarian - maximizing the sum of agents' utilities, and leximin - maximizing the smallest agent's utility, then the second-smallest, etc. Utilitarianism is typically computationally easier to attain but is generally viewed as less fair. This paper presents a general reduction scheme that, given a utilitarian solver, produces a distribution over states (deterministic outcomes) that is leximin in expectation. Importantly, the scheme is robust in the sense that, given an approximate utilitarian solver, it produces a lottery that is approximately-leximin (in expectation) - with the same approximation factor. We apply our scheme to several social choice problems: stochastic allocations of indivisible goods, giveaway lotteries, and fair lotteries for participatory budgeting.
AAAI Conference 2025 Conference Paper
Issue salience is a major determinant in voters' decisions. Candidates and political parties campaign to shift salience to their advantage - a process termed priming. We study the dynamics, strategies and equilibria of campaign spending for voter priming in multi-issue multi-party settings. We consider both parliamentary elections, where parties aim to maximize their share of votes, and various settings for presidential elections, where the winner takes all. For parliamentary elections, we show that pure equilibrium spending always exists and can be computed in time linear in the number of voters. For two parties and all settings, a spending equilibrium exists such that each party invests only in a single issue, and an equilibrium can be computed in time that is polynomial in the number of issues and linear in the number of voters. We also show that in most presidential settings no equilibrium exists. Additional properties of optimal campaign strategies are also studied.
JAAMAS Journal 2024 Journal Article
Abstract In this work we explore the opportunities presented by partitioning contestants in contest into disjoint groups, each competing in an independent contest, with its own prize. This, as opposed to most literature on contest design, which focuses on the setting of a single “grand” (possibly multi-stage) contest, wherein all potential contestants ultimately compete for the same prize(s), with few exceptions that do consider contest partitioning, yet with conflicting preference results concerning the optimal structure to be used. Focusing on binary contests, wherein the quality of contestants’ submissions are endogenously determined, we show that contest partitioning is indeed beneficial under some condition, e. g. , whenever the number of contestants, or the prize amount, are “sufficiently large”, where the exact size requirements are a function of the partitioning cost. When partitioning does not entail any cost, we show that it is either a dominating or weakly dominating strategy, depending on the way the organizer’s expected benefit is determined. The analysis is further extended to consider partitioning where some of the sub-contests used contain a single contestant (a singleton). We conclude that contest partitioning is an avenue that contest designers can and should consider, when aiming to maximize their profit.
AAAI Conference 2023 Conference Paper
The use of virtual agents (bots) has become essential for providing online assistance to customers. However, even though a lot of effort has been dedicated to the research, development, and deployment of such virtual agents, customers are frequently frustrated with the interaction with the virtual agent and require a human instead. We suggest that a holistic approach, combining virtual agents and human operators working together, is the path to providing satisfactory service. However, implementing such a holistic customer service system will not, and cannot, be achieved using any single AI technology or branch. Rather, such a system will inevitably require the integration of multiple and diverse AI technologies, including natural language processing, multi-agent systems, machine learning, reinforcement learning, and behavioral cloning; in addition to integration with other disciplines such as psychology, business, sociology, economics, operation research, informatics, computer-human interaction, and more. As such, we believe this customer service application offers a rich domain for experimentation and application of multidisciplinary AI. In this paper, we introduce the holistic customer service application and discuss the key AI technologies and disciplines required for a successful AI solution for this setting. For each of these AI technologies, we outline the key scientific questions and research avenues stemming from this setting. We demonstrate that integrating technologies from different fields can lead to a cost-effective successful customer service center. The challenge is that there is a need for several communities, each with its own language and modeling techniques, different problem-solving methods, and different evaluation methodologies, all of which need to work together. Real cooperation will require the formation of joint methodologies and techniques that could improve the service to customers, but, more importantly, open new directions in cooperation of diverse communities toward solving joint difficult tasks.
ECAI Conference 2023 Conference Paper
Leximin is a common approach to multi-objective optimization, frequently employed in fair division applications. In leximin optimization, one first aims to maximize the smallest objective value; subject to this, one maximizes the second-smallest objective; and so on. Often, even the single-objective problem of maximizing the smallest value cannot be solved accurately. What can we hope to accomplish for leximin optimization in this situation? Recently, Henzinger et al. (2022) defined a notion of approximate leximin optimality. Their definition, however, considers only an additive approximation. In this work, we first define the notion of approximate leximin optimality, allowing both multiplicative and additive errors. We then show how to compute, in polynomial time, such an approximate leximin solution, using an oracle that finds an approximation to a single-objective problem. The approximation factors of the algorithms are closely related: an (α, ϵ)-approximation for the single-objective problem (where α ∈ (0, 1] and ϵ ≥ 0 are the multiplicative and additive factors respectively) translates into an (α2/(1 − α + α2), ϵ/(1 − α + α2))-approximation for the multi-objective leximin problem, regardless of the number of objectives. Finally, we apply our algorithm to obtain an approximate leximin solution for the problem of stochastic allocations of indivisible goods.
AAMAS Conference 2023 Conference Paper
Fair allocation of indivisible goods has been studied extensively. However, the solutions offered to date are not resilient to subsequent changes that may occur after the allocation has been decided and executed, e. g. , agents leaving the system, or additional goods are discovered. Currently, such settings require rerunning the allocation algorithm from scratch, potentially shifting most allocated goods between the agents. This can be cumbersome at best, or impossible at worst. In this paper, we study the notion of resilience, which quantifies the number of changes needed to resolve subsequent changes in the environment. We then apply it to the problem of fair allocation of indivisible goods, focusing on the EF1 and EFX solution concepts. For the EF1 solution concept, we provide constructive and efficient algorithms to restore EF1 after a simultaneous loss of goods, addition of new goods, and resignation of agents. We show that the addition of new agents cannot be resolved efficiently when the agents’ valuation may be arbitrary. When agents have identical valuations, we show how to accept new agents efficiently. For the EFX solution concept, we (mostly) prove negative results, establishing that restoring EFX may be prohibitively costly, even for agents with identical valuations.
AAAI Conference 2022 Conference Paper
We consider a setting where a large number of agents are all interested in attending some public resource of limited capacity. Attendance is thus allotted by lottery. If agents arrive individually, then randomly choosing the agents – one by one - is a natural, fair and efficient solution. We consider the case where agents are organized in groups (e. g. families, friends), the members of each of which must all be admitted together. We study the question of how best to design such lotteries. We first establish the desired properties of such lotteries, in terms of fairness and efficiency, and define the appropriate notions of strategy proofness (providing that agents cannot gain by misrepresenting the true groups, e. g. joining or splitting groups). We establish inter-relationships between the different properties, proving properties that cannot be fulfilled simultaneously (e. g. leximin optimality and strong group stratagy proofness). Our main contribution is a polynomial mechanism for the problem, which guarantees many of the desired properties, including: leximin optimality, Paretooptimality, anonymity, group strategy proofness, and adjunctive strategy proofness (which provides that no benefit can be obtained by registering additional - uninterested or bogus individuals). The mechanism approximates the utilitarian optimum to within a factor of 2, which, we prove, is optimal for any mechanism that guarantees any one of the following properties: egalitarian welfare optimality, leximin optimality, envyfreeness, and adjunctive strategy proofness.
IJCAI Conference 2022 Conference Paper
Multi-defender Stackelberg Security Games (MSSG) have recently gained increasing attention in the literature. However, the solutions offered to date are highly sensitive, wherein even small perturbations in the attacker's utility or slight uncertainties thereof can dramatically change the defenders' resulting payoffs and alter the equilibrium. In this paper, we introduce a robust model for MSSGs, which admits solutions that are resistant to small perturbations or uncertainties in the game's parameters. First, we formally define the notion of robustness, as well as the robust MSSG model. Then, for the non-cooperative setting, we prove the existence of a robust approximate equilibrium in any such game, and provide an efficient construction thereof. For the cooperative setting, we show that any such game admits a robust approximate (alpha) core, and provide an efficient construction thereof. Lastly, we show that stronger types of the core may be empty. Interestingly, the robust solutions can substantially increase the defenders' utilities over those of the non-robust ones.
AAMAS Conference 2019 Conference Paper
IJCAI Conference 2019 Conference Paper
We study temporal information design in contests, wherein the organizer may, possibly incrementally, disclose information about the participation and performance of some contestants to other (later) contestants. We show that such incremental disclosure can increase the organizer's profit. The expected profit, however, depends on the exact information disclosure structure, and the optimal structure depends on the parameters of the problem. We provide a game-theoretic analysis of such information disclosure schemes as they apply to two common models of contests: (a) simple contests, wherein contestants' decisions concern only their participation; and (b) Tullock contests, wherein contestants choose the effort levels to expend. For each of these we analyze and characterize the equilibrium strategy, and exhibit the potential benefits of information design.
IJCAI Conference 2018 Conference Paper
Motivated by applications such as stock exchanges and spectrum auctions, there is a growing interest in mechanisms for arranging trade in two-sided markets. However, existing mechanisms are either not truthful, do not guarantee an asymptotically-optimal gain-from-trade, rely on a prior on the traders' valuations, or operate in limited settings such as a single type of good. We extend the random-sampling technique used in earlier works to multi-good markets where traders have gross-substitute valuations. We show a prior free, truthful and strongly-budget-balanced mechanism which guarantees near-optimal gain from trade when the market sizes of all goods grow to infinity at a similar rate.
AAAI Conference 2018 Conference Paper
In a seminal paper, McAfee (1992) presented a truthful mechanism for double auctions, attaining asymptoticallyoptimal gain-from-trade without any prior information on the valuations of the traders. McAfee’s mechanism handles single-parametric agents, allowing each seller to sell a single unit and each buyer to buy a single unit. This paper presents a double-auction mechanism that handles multi-parametric agents and allows multiple units per trader, as long as the valuation functions of all traders have decreasing marginal returns. The mechanism is prior-free, ex-post individually-rational, dominant-strategy truthful and strongly-budget-balanced. Its gain-from-trade approaches the optimum when the market size is sufficiently large.
IJCAI Conference 2018 Conference Paper
Much of the work on multi-agent contests is focused on determining the equilibrium behavior of contestants. This capability is essential for the principal for choosing the optimal parameters for the contest (e. g. prize amount). As it turns out, many contests exhibit not one, but many possible equilibria, hence precluding contest design optimization and contestants behavior prediction. In this paper we examine a variation of the classic contest that alleviates this problem by having contestants make the decisions sequentially rather than in parallel. We study this model in the setting of a simple contest, wherein contestants only choose whether or not to participate, while their performance level is exogenously set. We show that by switching to the revised mechanism the principal can not only force her most desired pure-strategies based equilibrium to emerge, but also, at times, end up with an equilibrium offering a greater expected profit. Further, we show that in the modified contest the optimal prize can be effectively computed. The theoretical analysis is complemented by comprehensive experiments with people over Amazon Mechanical Turk. Here, we find that the modified mechanism offers great benefit for the principal, both in terms of an increased over-participation in the contest (compared to theoretical expectations) and increased average profit.
JAAMAS Journal 2015 Journal Article
Abstract We consider team-work settings where individual agents incur costs on behalf of the team. In such settings it is frequently the custom to reimburse agents for the costs they incur (at least in part) in order to promote fairness. We show, however, that when agents are self-interested, such reimbursement can result in degradation in efficiency—at times severe degradation. We thus study the relationship between efficiency and fairness in such settings, distinguishing between ex-ante and ex-post fairness. First, we analyze reimbursement policies that reimburse solely based on purchase receipts (as is customary), and show that with such policies the degradation in both efficiency and fairness can be unbounded. We thus introduce two other families of reimbursement policies. The first family guarantees optimal efficiency and ex-ante fairness, but not ex-post fairness. The second family improves (at times) on ex-post fairness, but at the expense of efficiency, thus providing a tradeoff between the two.
AAAI Conference 2015 Conference Paper
We consider the problem of fair division of a two dimensional heterogeneous good among several agents. Applications include division of land as well as ad space in print and electronic media. Classical cake cutting protocols either consider a one-dimensional resource, or allocate each agent several disconnected pieces. In practice, however, the two dimensional shape of the allotted piece is of crucial importance in many applications, e. g. , squares or bounded aspectratio rectangles are most useful for building houses as well as advertisements. We thus introduce and study the problem of envy-free two-dimensional division wherein the utility of the agents depends on the geometric shape of the allocated pieces (as well as the location and size). In addition to envyfreeness, we require that the fraction allocated to each agent be at least a certain constant that depends only on the shape of the cake and the number of agents. We focus on the case where the allotted pieces must be square and the cakes are either squares or the unbounded plane. We provide algorithms for the problem for settings with two and three agents.
JAAMAS Journal 2013 Journal Article
Abstract Crowdsourcing applications frequently employ many individual workers, each performing a small amount of work. In such settings, individually determining the reward for each assignment and worker may seem economically beneficial, but is inapplicable if manually performed. We thus consider the problem of designing automated agents for automatic reward determination and negotiation in such settings. We formally describe this problem and show that it is NP-hard. We therefore present two automated agents for the problem, based on two different models of human behavior. The first, the Reservation Price Based Agent (RPBA), is based on the concept of a RP, and the second, the No Bargaining Agent (NBA) which tries to avoid any negotiation. The performance of the agents is tested in extensive experiments with real human subjects, where both NBA and RPBA outperform strategies developed by human experts.
AIJ Journal 2013 Journal Article
AAAI Conference 2012 Conference Paper
We consider the problem of designing automated strategies for interactions with human subjects, where the humans must be rewarded for performing certain tasks of interest. We focus on settings where there is a single task that must be performed many times by different humans (e. g. answering a questionnaire), and the humans require a fee for performing the task. In such settings, our objective is to minimize the average cost for effectuating the completion of the task. We present two automated strategies for designing efficient agents for the problem, based on two different models of human behavior. The first, the Reservation Price Based Agent (RPBA), is based on the concept of a reservation price, and the second, the No Bargaining Agent (NBA), uses principles from behavioral science. The performance of the agents has been tested in extensive experiments with real human subjects, where NBA outperforms both RPBA and strategies developed by human experts.
AIJ Journal 2012 Journal Article
TCS Journal 2012 Journal Article
AAMAS Conference 2012 Conference Paper
AAMAS Conference 2010 Conference Paper
Coalitions and cooperation are key topics in multi–agent systems (MAS). They enable agents to achieve goals that theymay not have been able to achieve independently. A rangeof previous studies have found that many problems in coalitional games tend to be computationally intractable - thatis, the computational complexity grows rapidly as a functionof the number of participating agents. However, these hardness results generally require that each agent is of a differenttype. Here, we observe that in many mas settings, while thenumber of agents may grow, the number of different types ofagents remains small. We formally define the notion of agenttypes in cooperative games. We then re-examine the computational complexity of the different coalition formationproblems when assuming that the number of agent typesis fixed. We show that most of the previously hard problems become polynomial when the number of agent typesis fixed. We consider multiple different game formulationsand representations (characteristic function with subadditive utilities, crg, and graphical representations) and several different computational problems (including stability, core-emptiness, and Shapley value).
IJCAI Conference 2009 Conference Paper
This paper considers the setting wherein a group of agents (e. g. , robots) is seeking to obtain a given tangible good, potentially available at different locations in a physical environment. Traveling between locations, as well as acquiring the good at any given location consumes from the resources available to the agents (e. g. , battery charge). The availability of the good at any given location, as well as the exact cost of acquiring the good at the location is not fully known in advance, and observed only upon physically arriving at the location. However, apriori probabilities on the availability and potential cost are provided. Given such as setting, the problem is to find a strategy/plan that maximizes the probability of acquiring the good while minimizing resource consumption. Sample applications include agents in exploration and patrol missions, e. g. , rovers on Mars seeking to mine a specific mineral. Although this model captures many real world scenarios, it has not been investigated so far. We focus on the case where locations are aligned along a path, and study several variants of the problem, analyzing the effects of communication and coordination. For the case that agents can communicate, we present a polynomial algorithm that works for any fixed number of agents. For noncommunicating agents, we present a polynomial algorithm that is suitable for any number of agents. Finally, we analyze the difference between homogeneous and heterogeneous agents, both with respect to their allotted resources and with respect to their capabilities.
TCS Journal 2009 Journal Article
AAMAS Conference 2009 Conference Paper
Coalition formation is a key topic in multi–agent systems (mas). Coalitions enable agents to achieve goals that they may not have been able to achieve independently, and encourages resource sharing among agents with different goals. A range of previous studies have found that problems in coalitional games tend to be computationally complex. However, such hardness results consider the entire input as one, ignoring any structural information on the instances. In the case of coalition formation problems, this bundles together several distinct elements of the input, e. g. the agent set, the goal set, the resources, etc. In this paper we reexamine the complexity of coalition formation problems in the coalition resources game model, as a function of their distinct input elements, using the theory of parameterized complexity. The analysis shows that not all parts of the input are created equal, and that many instances of the problem are actually tractable. We show that the problems are FPT in the number of goals, implying that if the number of goals is bounded then an efficient algorithm is available. Similarly, the problems are FPT in the combination of the number of agents and resources, again implying that if these parameters are bounded, then an efficient algorithm is available. On the other hand, the problems are para-NP hard in the number of resources, implying that even if we bound the number of resources the problems (probably) remain hard. Additionally, we show that most problems are W[1]-hard in the size of the coalition of interest, indicating that there is (probably) no algorithm polynomial in all but the coalition size. The exact definitions of the parameterized complexity notions FPT, Para-NP and W[1] are provided herein.
TCS Journal 2009 Journal Article
AAMAS Conference 2008 Conference Paper
We investigate the extent to which it is possible to evaluate the probability of a particular candidate winning an election, given imperfect information about the preferences of the electorate. We assume that for each voter, we have a probability distribution over a set of preference orderings. Thus, for each voter, we have a number of possible preference orderings – we do not know which of these orderings actually represents the voters’ preferences, but we know for each one the probability that it does. We give a polynomial algorithm to solve the problem of computing the probability that a given candidate will win when the number of candidates is a constant. However, when the number of candidates is not bounded, we prove that the problem becomes #P-Hard for the Plurality, Borda, and Copeland voting protocols. We further show that even evaluating if a candidate has any chance to win is NP-Complete for the Plurality voting protocol, in the weighted voters case. We give a polynomial algorithm for this problem when the voters’ weights are equal.
AAAI Conference 2008 Conference Paper
This paper considers the problem of an agent searching for a resource or a tangible good in a physical environment, where at each stage of its search it observes one source where this good can be found. The cost of acquiring the resource or good at a given source is uncertain (a-priori), and the agent can observe its true value only when physically arriving at the source. Sample applications involving this type of search include agents in exploration and patrol missions (e. g. , an agent seeking to find the best location to deploy sensing equipment along its path). The uniqueness of these settings is that the expense of observing the source on each step of the process derives from the last source the agent explored. We analyze three variants of the problem, differing in their objective: minimizing the total expected cost, maximizing the success probability given an initial budget, and minimizing the budget necessary to obtain a given success probability. For each variant, we first introduce and analyze the problem with a single agent, either providing a polynomial solution to the problem or proving it is NP-Complete. We also introduce an innovative fully polynomial time approximation scheme algorithm for the minimum budget variant. Finally, the results for the single agent case are generalized to multi-agent settings.
SODA Conference 2006 Conference Paper
SODA Conference 2005 Conference Paper
TCS Journal 2000 Journal Article
SODA Conference 1999 Conference Paper
FOCS Conference 1997 Conference Paper
Let a text string T of n symbols and a pattern string P of m symbols from alphabet /spl Sigma/ be given. A swapped version T' of T is a length n string derived from T by a series of local swaps, (i. e. t/sup '//sub l//spl larr/t/sub l+1/ and t'/sub l+1//spl larr/t/sub l/) where each element can participate in no more than one swap. The Pattern Matching with Swaps problem is that of finding all locations i for which there exists a swapped version T' of T where there is an exact matching of P in location i of T'. It has been an open problem whether swapped matching can be done in less than O(mn) time. In this paper we show the first algorithm that solves the pattern matching with swaps problem in time O(mn). We present an algorithm whose time complexity is O(nm/sup 1/3/ log m log/sup 2/ /spl sigma/) for a general alphabet /spl Sigma/, where /spl sigma/=min(m, |/spl Sigma/|).
FOCS Conference 1996 Conference Paper
The authors consider the tolerance of data structures to memory faults. They observe that many pointer-based data structures (e. g. linked lists, trees, etc.) are highly nonresilient to faults. A single fault in a linked list or tree may result in the loss of the entire set of data. They present a formal framework for studying the fault tolerance properties of pointer-based data structures, and provide fault tolerant versions of the stack, the linked list, and the dictionary tree.
SODA Conference 1995 Conference Paper
TCS Journal 1994 Journal Article
FOCS Conference 1993 Conference Paper
An n-thread parallel program p is large-grained if in every parallel step the computations on each of the threads are complex procedures requiring numerous processor instructions. This practically relevant style of programs differs from PRAM programs in its large granularity and the possibility that within a parallel step the computations on different threads may considerably vary in size. Let M be an n-processor asynchronous parallel system, with no restriction on the degree of asynchrony and without any specialized synchronization mechanisms. It is a challenging theoretical as well as practically important problem to ensure correct execution of P on such a parallel machine. Let P be a large-grained program requiring total work W for its execution on a synchronous a-processor parallel system. We present a transformation (compilation) of P into a program C(P) which correctly and efficiently effects the computation of P on the asynchronous machine M. Under moderate assumptions on the granularity of threads and the size of the program variables, execution of C(P) requires just O(Wlog* n) expected total work, and the memory space overhead is a small multiplicative constant. >
FOCS Conference 1992 Conference Paper
The authors discuss the question of simulating synchronous computations on asynchronous systems. They consider an asynchronous system with very weak, or altogether lacking any, atomicity assumptions. The first contribution of this paper is a novel clock for asynchronous systems. The clock is a basic tool for synchronization in the asynchronous environment. It is a very robust construction and can operate in a system with no atomicity assumptions, and in the presence of a dynamic scheduler. The behavior of the clock is obtained with overwhelming probability (1-2/sup - alpha n/, alpha >0). The authors show how to harness this clock to drive a PRAM simulation on an asynchronous system. The resulting simulation scheme is more efficient than existing ones, while actually relaxing the assumptions on the underlying asynchronous system. >
FOCS Conference 1991 Conference Paper
A scheme for emulating the parallel random access machine (PRAM) on a faulty hypercube is presented. All components of the hypercube, including the memory modules, are assumed to be subject to failure. The faults may occur at any time during the emulation and the system readjusts dynamically. The scheme, which rests on L. G. Valiant's BSP model (1990), is the first to achieve optimal and work-preserving PRAM emulation on a dynamically faulty network. >