YAYehuda Afek
Yehuda Afek
*This is an algorithmically generated author record based on publicly available information.
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Research Interests
Yehuda Afek has a total of 9 co-authors. Here are the top co-authors by number of shared publications:
- Eli Gafni
Computer Science Department Univ. of California 95024 LA CA
4 shared publications - Nathan Linial
The Hebrew University of Jerusalem
3 shared publications - Adam Morrison
Tel Aviv University, Tel Aviv, Israel
2 shared publications - Benny Sudakov
ETH Zurich, Switzerland
2 shared publications - Uriel Feige
Weizmann Institute of Science, Rehovot, Israel
2 shared publications - Yakov Babichenko
Department of Mathematics Hebrew University 91904 Jerusalem Israel
2 shared publications
Latest Publications
- Open Access
A King in every two consecutive tournaments
We think of a tournament $T=([n], E)$ as a communication network where in each round of communication processor $P_i$ sends its information to $P_j$, for every directed edge $ij \in E(T)$. By Landau's theorem (1953) there is a King in $T$, i.e., a processor whose initial input reaches every other processor in two rounds or less. Namely, a processor $P_{\nu}$ such that after two rounds of communication along $T$'s edges, the initial information of $P_{\nu}$ reaches all other processors. Here we consider a more general scenario where an adversary selects an arbitrary series of tournaments $T_1, T_2,\ldots$, so that in each round $s=1, 2, \ldots$, communication is governed by the corresponding tournament $T_s$. We prove that for every series of tournaments that the adversary selects, it is still true that after two rounds of communication, the initial input of at least one processor reaches everyone. Concretely, we show that for every two tournaments $T_1, T_2$ there is a vertex in $[n]$ that can reach all vertices via (i) A step in $T_1$, or (ii) A step in $T_2$ or (iii) A step in $T_1$ followed by a step in $T_2$. }Open AccessA King in every two consecutive tournaments
We think of a tournament $T=([n], E)$ as a communication network where in each round of communication processor $P_i$ sends its information to $P_j$, for every directed edge $ij \in E(T)$. By Landau's theorem (1953) there is a King in $T$, i.e., a processor whose initial input reaches every other processor in two rounds or less. Namely, a processor $P_{\nu}$ such that after two rounds of communication along $T$'s edges, the initial information of $P_{\nu}$ reaches all other processors. Here we consider a more general scenario where an adversary selects an arbitrary series of tournaments $T_1, T_2,\ldots$, so that in each round $s=1, 2, \ldots$, communication is governed by the corresponding tournament $T_s$. We prove that for every series of tournaments that the adversary selects, it is still true that after two rounds of communication, the initial input of at least one processor reaches everyone. Concretely, we show that for every two tournaments $T_1, T_2$ there is a vertex in $[n]$ that can reach all vertices via (i) A step in $T_1$, or (ii) A step in $T_2$ or (iii) A step in $T_1$ followed by a step in $T_2$. } - 28 March 2013
- Published by Springer Nature in Distributed Computing
- Vol. 26 (4) , 243-269
Fast and scalable rendezvousing
- 28 March 2013
- Published by Springer Nature in Distributed Computing
- Vol. 26 (4) , 243-269
Fast and scalable rendezvousing
- Open Access
Musical chairs
In the {\em Musical Chairs} game $MC(n,m)$ a team of $n$ players plays against an adversarial {\em scheduler}. The scheduler wins if the game proceeds indefinitely, while termination after a finite number of rounds is declared a win of the team. At each round of the game each player {\em occupies} one of the $m$ available {\em chairs}. Termination (and a win of the team) is declared as soon as each player occupies a unique chair. Two players that simultaneously occupy the same chair are said to be {\em in conflict}. In other words, termination (and a win for the team) is reached as soon as there are no conflicts. The only means of communication throughout the game is this: At every round of the game, the scheduler selects an arbitrary nonempty set of players who are currently in conflict, and notifies each of them separately that it must move. A player who is thus notified changes its chair according to its deterministic program. As we show, for $m\ge 2n-1$ chairs the team has a winning strategy. Moreover, using topological arguments we show that this bound is tight. For $m\leq 2n-2$ the scheduler has a strategy that is guaranteed to make the game continue indefinitely and thus win. We also have some results on additional interesting questions. For example, if $m \ge 2n-1$ (so that the team can win), how quickly can they achieve victory?Open AccessMusical chairs
In the {\em Musical Chairs} game $MC(n,m)$ a team of $n$ players plays against an adversarial {\em scheduler}. The scheduler wins if the game proceeds indefinitely, while termination after a finite number of rounds is declared a win of the team. At each round of the game each player {\em occupies} one of the $m$ available {\em chairs}. Termination (and a win of the team) is declared as soon as each player occupies a unique chair. Two players that simultaneously occupy the same chair are said to be {\em in conflict}. In other words, termination (and a win for the team) is reached as soon as there are no conflicts. The only means of communication throughout the game is this: At every round of the game, the scheduler selects an arbitrary nonempty set of players who are currently in conflict, and notifies each of them separately that it must move. A player who is thus notified changes its chair according to its deterministic program. As we show, for $m\ge 2n-1$ chairs the team has a winning strategy. Moreover, using topological arguments we show that this bound is tight. For $m\leq 2n-2$ the scheduler has a strategy that is guaranteed to make the game continue indefinitely and thus win. We also have some results on additional interesting questions. For example, if $m \ge 2n-1$ (so that the team can win), how quickly can they achieve victory? - Open Access
Oblivious Collaboration
Communication is a crucial ingredient in every kind of collaborative work. But what is the least possible amount of communication required for a given task? We formalize this question by introducing a new framework for distributed computation, called {\em oblivious protocols}. We investigate the power of this model by considering two concrete examples, the {\em musical chairs} task $MC(n,m)$ and the well-known {\em Renaming} problem. The $MC(n,m)$ game is played by $n$ players (processors) with $m$ chairs. Players can {\em occupy} chairs, and the game terminates as soon as each player occupies a unique chair. Thus we say that player $P$ is {\em in conflict} if some other player $Q$ is occupying the same chair, i.e., termination means there are no conflicts. By known results from distributed computing, if $m \le 2n-2$, no strategy of the players can guarantee termination. However, there is a protocol with $m = 2n-1$ chairs that always terminates. Here we consider an oblivious protocol where in every time step the only communication is this: an adversarial {\em scheduler} chooses an arbitrary nonempty set of players, and for each of them provides only one bit of information, specifying whether the player is currently in conflict or not. A player notified not to be in conflict halts and never changes its chair, whereas a player notified to be in conflict changes its chair according to its deterministic program. Remarkably, even with this minimal communication termination can be guaranteed with only $m=2n-1$ chairs. Likewise, we obtain an oblivious protocol for the Renaming problem whose name-space is small as that of the optimal nonoblivious distributed protocol. Other aspects suggest themselves, such as the efficiency (program length) of our protocols. We make substantial progress here as well, though many interesting questions remain open.Open AccessOblivious Collaboration
Communication is a crucial ingredient in every kind of collaborative work. But what is the least possible amount of communication required for a given task? We formalize this question by introducing a new framework for distributed computation, called {\em oblivious protocols}. We investigate the power of this model by considering two concrete examples, the {\em musical chairs} task $MC(n,m)$ and the well-known {\em Renaming} problem. The $MC(n,m)$ game is played by $n$ players (processors) with $m$ chairs. Players can {\em occupy} chairs, and the game terminates as soon as each player occupies a unique chair. Thus we say that player $P$ is {\em in conflict} if some other player $Q$ is occupying the same chair, i.e., termination means there are no conflicts. By known results from distributed computing, if $m \le 2n-2$, no strategy of the players can guarantee termination. However, there is a protocol with $m = 2n-1$ chairs that always terminates. Here we consider an oblivious protocol where in every time step the only communication is this: an adversarial {\em scheduler} chooses an arbitrary nonempty set of players, and for each of them provides only one bit of information, specifying whether the player is currently in conflict or not. A player notified not to be in conflict halts and never changes its chair, whereas a player notified to be in conflict changes its chair according to its deterministic program. Remarkably, even with this minimal communication termination can be guaranteed with only $m=2n-1$ chairs. Likewise, we obtain an oblivious protocol for the Renaming problem whose name-space is small as that of the optimal nonoblivious distributed protocol. Other aspects suggest themselves, such as the efficiency (program length) of our protocols. We make substantial progress here as well, though many interesting questions remain open. - 8 May 2007
- Published by Springer Nature in Distributed Computing
- Vol. 20 (4) , 239-252
Common2 extended to stacks and unbounded concurrency
- 8 May 2007
- Published by Springer Nature in Distributed Computing
- Vol. 20 (4) , 239-252
Common2 extended to stacks and unbounded concurrency
- 1 August 1999
- Published by Elsevier in Information and Computation
- Vol. 153 (1) , 117-138
The Power of Multiobjects
- 1 August 1999
- Published by Elsevier in Information and Computation
- Vol. 153 (1) , 117-138
The Power of Multiobjects