Eli Gafni
Research Subjects
Research Interests
Eli Gafni has a total of 21 co-authors. Here are the top co-authors by number of shared publications:
- Yehuda Afek
The Blavatnik School of Computer Science Tel-Aviv University Israel
4 shared publications - Nathan Linial
The Hebrew University of Jerusalem
3 shared publications - Benny Sudakov
ETH Zurich, Switzerland
2 shared publications - Sergio Rajsbaum
Instituto de Matemáticas, Universidad Nacional Autónoma de México, Mexico, Mexico
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$. } - Open Access
The Life in 1-Consensus
This paper introduces the atomic Write and Read Next ($\text{WRN}_{k}$) deterministic shared memory object, that for any $k\ge3$, is stronger than read-write registers, but is unable to implement $2$-processor consensus. In particular, it refutes the conjecture claiming that every deterministic object of consensus number $1$ is computationally equivalent to read-write registers.Open AccessThe Life in 1-Consensus
This paper introduces the atomic Write and Read Next ($\text{WRN}_{k}$) deterministic shared memory object, that for any $k\ge3$, is stronger than read-write registers, but is unable to implement $2$-processor consensus. In particular, it refutes the conjecture claiming that every deterministic object of consensus number $1$ is computationally equivalent to read-write registers. - 5 November 2015
- Published by Springer Nature
- p. 140-153
Elastic Configuration Maintenance via a Parsimonious Speculating Snapshot Solution
- 5 November 2015
- Published by Springer Nature
- p. 140-153
Elastic Configuration Maintenance via a Parsimonious Speculating Snapshot Solution
- 1 January 2015
- Published by Elsevier in Theoretical Computer Science
- Vol. 561, 122-133
Linear space bootstrap communication schemes
- 1 January 2015
- Published by Elsevier in Theoretical Computer Science
- Vol. 561, 122-133
Linear space bootstrap communication schemes
- 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. - 3 November 2009
- Published by Springer Nature in Distributed Computing
- Vol. 22 (3) , 185-195
The k-simultaneous consensus problem
- 3 November 2009
- Published by Springer Nature in Distributed Computing
- Vol. 22 (3) , 185-195
The k-simultaneous consensus problem
- 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 April 2002
- Published by Springer Nature in Distributed Computing
- Vol. 15 (2) , 87-96
An adaptive collect algorithm with applications
- 1 April 2002
- Published by Springer Nature in Distributed Computing
- Vol. 15 (2) , 87-96
An adaptive collect algorithm with applications
- 1 May 1990
- Published by Defense Technical Information Center (DTIC)
Atomic Snapshots of Shared Memory
An atomic snapshot memory is a shared data structure allowing concurrent processes to store information in a collection of shared registers, all of which may be read in a single atomic scan operation. This paper presents three wait-free implementations of atomic snapshot memory. Two constructions implement wait-free single-writer atomic snapshot memory from wait-free atomic single-writer, n-reader registers. A third construction implements a wait-free n-writer atomic snapshot memory from n-writer, n-reader registers. The first implementation uses unbounded (integer) fields in these registers, while the other implementations use only bounded registers. (kr)
- 1 May 1990
- Published by Defense Technical Information Center (DTIC)
Atomic Snapshots of Shared Memory
An atomic snapshot memory is a shared data structure allowing concurrent processes to store information in a collection of shared registers, all of which may be read in a single atomic scan operation. This paper presents three wait-free implementations of atomic snapshot memory. Two constructions implement wait-free single-writer atomic snapshot memory from wait-free atomic single-writer, n-reader registers. A third construction implements a wait-free n-writer atomic snapshot memory from n-writer, n-reader registers. The first implementation uses unbounded (integer) fields in these registers, while the other implementations use only bounded registers. (kr)