Selected publications of Gadi Taubenfeld

(The list does not include versions of conference papers that have beed accepted for journal publications.)

From Bezout’s Identity to space-optimal election in anonymous memory systems

Proceedings of the 39th annual symposium on principles of distributed computing (PODC 2020),
Virtual event, Italy, August 2020.
E. Godard, D. Imbs, M. Raynal and G. Taubenfeld

pdf

Fully anonymous consensus and set agreement algorithms

Proceedings of the 8th international conference on networked systems (NETYS 2020),

Virtual event, Morocco, June 2020.
M. Raynal and G. Taubenfeld

pdf  video-presentation

Leader-based De-anonymization of an Anonymous Read/Write Memory
Theoretical Computer Science 836 (October 2020) 110--123
(Preliminary versions of the results appeared in NETYS 2009 and SIROCCO 2010)

E. Godard, D. Imbs, M. Raynal and G. Taubenfeld

pdf   PublisherVersion (download free until October 3, 2020)

The computational structure of progress conditions and shared objects
Distributed Computing (2020) 33:103--123

(Preliminary versions of the results appeared in OPODIS 2009 and DISC 2010)
G. Taubenfeld
fullversion.pdf   Publisher's
version

Mutual exclusion in fully anonymous shared memory systems

Information Processing Letters, Volume 158, June 2020.
M. Raynal and G. Taubenfeld

pdf

Genome wide epigenetic modifications as a shared memory consensus problem

arXiv:2005.06502 (May 2020). Also, in BDA 2018
S. Rashid, G. Taubenfeld, and Z. Bar-Joseph

pdf

Fully anonymous shared memory algorithms

arXiv:1909.05576 (Sept 2019). Also, brief Announcement in SSS 2019

(Pisa, Italy, October 2019).
M. Raynal and G. Taubenfeld

fullVersion.pdf

Optimal memory-anonymous symmetric deadlock-free mutual exclusion
Proceedings of the 38th annual symposium on principles of distributed computing (PODC 2019),
Toronto, Canada, July 2019.

Z. Aghazadeh, D. Imbs, M. Raynal, G. Taubenfeld and P. Woelfel

pdf

Set agreement power is not a precise characterization for oblivious deterministic anonymous objects

26th International colloquium on structural information and communication complexity (SIROCCO 2019),

L'Aquila, Italy, July 2019. In: LNCS 11639, 293--308 (2019)
G. Taubenfeld

pdf

Anonymous read/write memory: leader election and de-anonymization

26th International colloquium on structural information and communication complexity (SIROCCO 2019),

L'Aquila, Italy, July 2019.  In: LNCS 11639, 246--261 (2019)
E. Godard, D. Imbs, M. Raynal and G. Taubenfeld

pdf

Mutex-based de-anonymization of an anonymous read/write memory

Proceedings of the 7th international conference on networked systems (NETYS 2019),

Morocco, June 2019.
E. Godard, D. Imbs, M. Raynal and G. Taubenfeld

pdf

Waiting in concurrent algorithms

Computing (2019) 101:39--57

(Also in: LNCS 9944, 2016, 345--360, NETYS 2016)
G. Taubenfeld

confVersion.pdf  fullVersion.pdf  publisher's link

Set agreement and renaming in the presence of contention-related crash failures

20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2018),

Tokyo, Japan, November 2018. In: LNCS 11201 (2018)
A. Durand, M. Raynal and G. Taubenfeld

fullVersion.pdf

Distributed Computing Pearls
Morgan&Claypool Publishers. 124 pages. May 2018.

G. Taubenfeld

Website  Morgan&Claypool   Amazon   Google

A closer look at fault tolerance
Theory of Computing Systems 62(5) :1085--1108, July 2018
(Also in: Proceedings of PODC 2012, 261--270)

G. Taubenfeld

confVersion.pdf   fullVersion.pdf   publisher's link

Weak Failures: Definitions, Algorithms and Impossibility Results

Proceedings of the 6th international conference on networked systems (NETYS 2018),

Essaouira, Morocco, May 2018.
G. Taubenfeld

pdf

Mutual exclusion algorithms with constant RMR complexity and wait-free exit code
Proceedings of the 21st international conference on principles of distributed systems  (OPODIS 2017),

Lisboa, Portugal, December 2017.
R. Dvir and G. Taubenfeld

pdf

Coordination without prior agreement
Proceedings of the 36th annual symposium on principles of distributed computing (PODC 2017),
Washington, DC, USA, July 2017.

G. Taubenfeld

pdf

Contention-sensitive data structures and algorithms

Theoretical Computer Science, 677 (May 2017) 41–55

(Also in: LNCS 5805, 2009, 157--171, DISC 2009)
G. Taubenfeld

confVersion.pdf     fullVersion.pdf   online link

Fair synchronization

Journal of Parallel and Distributed Computing 97:1--10, November 2016

(Also in: LNCS 8205, 2013, 179--193, DISC 2013)
G. Taubenfeld

confVersion.pdf     fullVersion.pdf   online link

Distributed universality
Algorithmica 76:502--535, October 2016

(Also in: LNCS 8878, 2014, 469--484, OPODIS 2014)
M. Raynal, J. Stainer and G. Taubenfeld

confVersion.pdf    fullVersion.pdf   online link

The computability of relaxed data structures: queues and stacks as examples
Distributed Computing 29(5):395--407, October 2016

(Also in: LNCS 9439, 2015, 414--428, SIROCCO 2015)
N. Shavit and G. Taubenfeld
confVersion.pdf   fullversion.pdf   online link   ppt

A closer look at concurrent data structures and algorithms
Distributed computing column of the Bulletin of the European Association

for Theoretical Computer Science (BEATCS), February 2015
G. Taubenfeld
pdf

Tight space bounds for l-exclusion
Distributed Computing 27:3 (2014) 165--179

(Also in: LNCS 6950 Springer Verlag 2011, 110--124, DISC 2011)

G. Taubenfeld

pdf

Computing with infinitely many processes

Information and Computation 233 (2013) 12--31

(Also in: LNCS 1914 Springer Verlag 2000, 164--178, DISC 2000)

M. Merritt and G. Taubenfeld

fullVersion.pdf

Weak read/write Registers

Proc. of the 14th international conf. on distributed computing and networking (ICDCN 2013),

Mumbai, India, January 2013. In: LNCS 7730 Springer Verlag 2013, 423--427
G. Taubenfeld

pdf

On the performance of distributed lock-based synchronization

ACM Operating  Systems Review  45 (2): 28-37 (2011).

Also in: Proc. of the 12th international conf. on distributed computing and networking (ICDCN 2011),

Bangalore, India, January 2011. In: LNCS 6522 Springer Verlag 2011, 131--142
Y. Lubowich and G. Taubenfeld

fullVersion.pdf

The computational structure of progress conditions

Proceedings of the 24th international symposium on distributed computing (DISC 2010),

Cambridge, Massachusetts, September 2010. In: LNCS 6343 Springer Verlag 2010, 221--235
G. Taubenfeld

confVersion.pdf    fullVersion.pdf

On asymmetric progress conditions
Proceedings of the 29th annual symposium on principles of distributed computing (PODC 2010),
Zurich, Switzerland, July 2010, 55--64

D. Imbs, M. Raynal and G. Taubenfeld

pdf

On the computational power of shared objects
Proceedings of the 13th international conference on principles of distributed systems  (OPODIS 2009),

Nimes, France, December 2009. In: LNCS 5923 Springer Verlag 2009, 270--284 (Best paper award)
G. Taubenfeld

pdf

Group renaming
Proceedings of the 12th international conference on principles of distributed systems (OPODIS 2008),

Luxor, Egypt, December 2008. In: LNCS 5401 Springer Verlag 2008, 58--72
Y. Afek, I. Gamzu, I. Levy, M. Merritt and G. Taubenfeld

pdf

Shared memory synchronization
Distributed computing column of the Bulletin of the European Association

for Theoretical Computer Science (BEATCS), October 2008
G. Taubenfeld
pdf
Concurrent programming, mutual exclusion (1965; Dijkstra)
Encyclopedia of Algorithms (2008) 188--191
G. Taubenfeld
pdf

Sequentially consistent versus linearizable counting networks
Distributed Computing 21:4 (2008) 249--269

M. Mavronicolas, M. Merritt and G. Taubenfeld

pdf     podc99.ps

Efficient transformations of obstruction-free algorithms into non-blocking algorithms
Proceedings of the 21st international symposium on distributed computing,

Lemesos, Cyprus, September 2007. In: LNCS 4731 Springer Verlag 2007, 450--464
G. Taubenfeld

pdf     ppt

The notion of a timed register and its application to indulgent synchronization
Proceedings of the 19th
ACM Symposium on Parallelism in Algorithms and Architectures,

San Diego, CA, USA June 2007

Michel Raynal and G. Taubenfeld

pdf

Computing in the presence of timing failures
Proceedings of the 26th IEEE international conference on distributed computing systems,

Lisboa, Portugal, July 2006

G. Taubenfeld

pdf

Synchronization algorithms and concurrent programming
Pearson Education / Prentice Hall. May 2006. 433 pages

G. Taubenfeld

website

Tight bounds for shared memory systems accessed by Byzantine processes
Distributed Computing 18:2 (2005) 99--109

N. Alon, M. Merritt, O. Reingold, G. Taubenfeld and R. N. Wright

pdf

The Black-White Bakery Algorithm
Proceedings of the 18th international symposium on distributed computing,

Amsterdam, the Netherlands, October 2004. In: LNCS 3274 Springer Verlag 2004, 56--70
G. Taubenfeld

pdf

Objects shared by Byzantine processes
Distributed Computing 16:1 (2003) 37--48

D. Malkhi, M. Merritt, M. Reiter and G. Taubenfeld

pdf

Resilient Consensus for Infinitely Many Processes
Proceedings of the 17th international symposium on distributed computing,
Italy, October 2003. In: LNCS 2848 Springer Verlag 2003, 1--15

M. Merritt and G. Taubenfeld

pdf

Automatic discovery of mutual exclusion algorithms
Proceedings of the 17th international symposium on distributed computing,
Italy, October 2003. In: LNCS 2848 Springer Verlag 2003, 136--150

Y. Bar-David and G. Taubenfeld

pdf

Public data structures: counters as a special case
Theoretical Computer Science 289:1 (2002) 401--423

H. Brit, S. Moran, and G. Taubenfeld

pdf

The concurrency hierarchy, and algorithms for unbounded concurrency
Proceedings of the 20th annual symposium on principles of distributed computing,
Newport, August 2001, 161--169

E. Gafni, M. Merritt and G. Taubenfeld

pdf

The power of multi-objects
Information and Computation 153 (1999) 117--138

Y. Afek, M. Merritt, and G. Taubenfeld

pdf

Constructing a reliable test&set bit
IEEE Transactions on Parallel and Distributed Systems 10:3 (1999) 252--265

F. Stomp, and G. Taubenfeld

pdf

Fairness of shared objects
Proceedings of the 12th international symposium on distributed computing,
Greece, September 1998. In: LNCS 1499 Springer Verlag 1998, 303--317

M. Merritt and G. Taubenfeld

ps

Time-adaptive algorithms for synchronization
SIAM Journal on Computing 26:2 (1997) 539--556

R. Alur, H. Attiya, and G. Taubenfeld

pdf

A lower bound on wait-free counting
Journal of Algorithms 24, 1--19 (1997)

S. Moran, and G. Taubenfeld

pdf

Disentangling Multi-object Operations
Proceedings of the 16th annual symposium on principles of distributed computing,
Santa Barbara, CA, August 1997, 111--120

Y. Afek, M. Merritt, G. Taubenfeld and D. Touitou

pdf

The wakeup problem
SIAM Journal on Computing 25:6 (1996) 1332--1357

M.J. Fischer, S. Moran, S. Rudich, and G. Taubenfeld

pdf

Fast timing-based algorithms
Distributed Computing 10:1 (1996) 1--10

R. Alur, and G. Taubenfeld

pdf

Concurrent counting
Journal of Computer and System Sciences 53:1 (1996) 61--78

S. Moran, G. Taubenfeld, and I. Yadin

pdf

Contention-free complexity of shared memory algorithms
Information and Computation 126:1 (1996) 62--73

R. Alur, and G. Taubenfeld

pdf

Possibility and impossibility results in a shared memory environment
Acta Informatica 33: (1996) 1--20

G. Taubenfeld, and S. Moran

pdf

Computing with faulty shared objects
Journal of the ACM 42:6 (1995) 1231--1274

Y. Afek, D.S. Greenberg, M. Merritt, and G. Taubenfeld

pdf

A connection between random variables and latin k-cubes
Discrete Mathematics 146 (1995) 313--320

R. Michel, G. Taubenfeld, and A. Berman

pdf

Impossibility results in the presence of multiple faulty processes
Information and Computation 113:2 (1994) 173-198

G. Taubenfeld, S. Katz, and S. Moran

pdf  (from FST-TCS9, Bangalore, India 1989)

Atomic m-register operations
Distributed Computing 7: (1994) 213--221

M. Merritt, and G. Taubenfeld

pdf

Speeding Lamport's fast mutual exclusion algorithm
Information Processing Letters 45 (1993) 137--142

M. Merritt, and G. Taubenfeld

pdf

Knowledge in shared memory systems
Distributed Computing 7:2 (1993) 99--109

M. Merritt, and G. Taubenfeld

pdf

Space-efficient asynchronous consensus without shared memory initialization
Information Processing Letters 45 (1993) 101--105

M.J. Fischer, S. Moran, and G. Taubenfeld

pdf

How to share an object: A fast timing-based solution
Proceedings of the 5th IEEE Symposium on Parallel and Distributed Processing,
Dallas, Texas, December 1993, 470--477

R. Alur, and G. Taubenfeld

conf.pdf    full.pdf

Benign failures models for shared memory
Proceedings of the 7th International workshop on distributed algorithms,
Switzerland, September 1993. In: LNCS 725 Springer Verlag 1993, 69--83

Y. Afek, M. Merritt, and G. Taubenfeld

pdf

Choice coordination with multiple alternatives
Proceedings of the 6th International workshop on distributed algorithms,
Haifa, Israel, November 1992. In: LNCS 647 Springer Verlag 1992, 54--68

D.S. Greenberg, G. Taubenfeld, and Da-Wei Wang

pdf

Results about fast mutual exclusion
Proceedings of the 13th IEEE Real-Time Systems Symposium,
Phoenix, Arizona, December 1992, 12--21

R. Alur, and G. Taubenfeld

On the nonexistence of resilient consensus protocols
Information Processing Letters 37 (1991) 285--289

G. Taubenfeld

pdf

Initial failures in distributed computations
International Journal of Parallel Programming 18:4 (1989) 255--276

G. Taubenfeld, S. Katz, and S. Moran

pdf (a bit corrupted)

Leader election in the presence of n-1 initial failures
Information Processing Letters 33 (1989) 25--28

G. Taubenfeld

Script: A communication abstraction mechanism and its verification
Science of Computer Programming 6 (1986) 35--88

N. Francez, B. Hailpern, and G. Taubenfeld

pdf

What processes know: definitions and proof methods
Proceedings of the 5th annual symposium on principles of distributed computing,
Calgary, Canada, August 1986, 249--262

S. Katz, and G. Taubenfeld

pdf