Chicago Journal of Theoretical (2003)
Pankaj Agarwal, Andrew Goldberg, Ketan Mulmuley, Eric Allender, Georg Gottlob, Gil Neiger, ...
We present a Logspace, many-one reduction from the undirected Abstract-1 s--t connectivity problem to its complement. This shows that SL = coSL.
Common Knowledge and Consistent Simultaneous Coordination (2000)
There is a very close relationship between common knowledge and simultaneity in synchronous distributed systems. The analysis of several well-known problems in terms of common knowledge has lead to...
Detection of Global State Predicates. (1998)
This paper examines algorithms for detecting when a property phi holds during the execution of a distributed system. The properties considered are expresses over the state of the system and are not...
Causal Memory: Definitions, Implementation and Programming (1998)
Mustaque Ahamad, Gil Neiger, James E. Burns, Prince Kohli, Phillip W. Hutto
The abstraction of a shared memory is of growing importance in distributed computing systems. Traditional memory consistency ensures that all processes agree on a common order of all operations on...
Implementing and Programming Weakly Consistent Memories (1995)
Gil Neiger, Umakishore Ramachandran, Karsten Schwan, Divyakant Agrawal, Gil Neiger Umakishore Ramachandran
this paper, we assume that the data is shared by DRF programs, and this allows us to develop more efficient schemes for maintaining causal consistency. In this chapter, we first modify the vector...
Causal Memory Meets the Consistency and Performance Needs of Distributed Applications! (1995)
Mustaque Ahamad, Ranjit John, Prince Kohli, Gil Neiger
In order to provide acceptable performance in large scale distributed systems, shared data must be cached at or close to nodes where it is accessed. Maintaining the consistency of such cached data is...
Causal Memory: Definitions, Implementation and Programming (1994)
Mustaque Ahamad, Gil Neiger, James E. Burns, Prince Kohli, Phillip W. Hutto
The abstraction of a shared memory is of growing importance in distributed computing systems. Traditional memory consistency ensures that all processes agree on a common order of all operations on...
The Complexity of Almost-Optimal Coordination (1993)
The problem of fault-tolerant coordination is fundamental in distributed computing. In the past, researchers have considered the complexity of achieving optimal simultaneous coordination under...
The Complexity of Almost-Optimal Coordination (1993)
The problem of fault-tolerant coordination is fundamental in distributed computing. In the past, researchers have considered the complexity of achieving optimal simultaneous coordination under...
The Complexity of Almost-Optimal Coordination (1993)
The problem of fault-tolerant coordination is fundamental in distributed computing. In the past, researchers have considered the complexity of achieving optimal simultaneous coordination under...
The Complexity of Almost-Optimal Coordination (1993)
The problem of fault-tolerant coordination is fundamental in distributed computing. In the past, researchers have considered the complexity of achieving optimal simultaneous coordination under...
Distributed Consensus Revisited (1993)
Distributed Consensus is a classical problem in distributed computing. It requires the correct processors in a distributed system to agree on a common value despite the failure of other processors....
Distributed Consensus Revisited (1993)
Distributed Consensus is a classical problem in distributed computing. It requires the correct processors in a distributed system to agree on a common value despite the failure of other processors....
Distributed Consensus Revisited (1993)
Distributed Consensus is a classical problem in distributed computing. It requires the correct processors in a distributed system to agree on a common value despite the failure of other processors....
Distributed Consensus Revisited (1993)
Distributed Consensus is a classical problem in distributed computing. It requires the correct processors in a distributed system to agree on a common value despite the failure of other processors....
Space-Efficient Atomic Snapshots in Synchronous Systems (1993)
We consider the problem of implementing an atomic snapshot memory in synchronous distributed systems. An atomic snapshot memory is an array of memory locations, one per processor. Each processor may...
The Power of Processor Consistency (1993)
Mustaque Ahamad, Rida A. Bazzi, Ranjit John, Prince Kohli, Gil Neiger
Shared memories that provide weaker consistency guarantees than the traditional sequentially consistent or atomic memories have been claimed to provide the key to building scalable systems. One...
Using Knowledge to Optimally Achieve Coordination in Distributed Systems (1993)
The problem of coordinating the actions of individual processors is fundamental in distributed computing. Researchers have long endeavored to find efficient solutions to a variety of problems...
Simplifying Fault-Tolerance: Providing the Abstraction of Crash Failures (1993)
ion of Crash Failures Rida A. Bazzi y Gil Neiger GIT--CC--93/12 February 16, 1993 Abstract The difficulty of designing fault-tolerant distributed algorithms increases with the severity of failures...
A Characterization of Scalable Shared Memories (1993)
Prince Kohli, Gil Neiger, Mustaque Ahamad
The traditional consistency requirements of shared memory are expensive to provide both in large scale multiprocessor systems and also in distributed systems that implement a shared memory...
A Characterization of Scalable Shared Memories (1993)
Prince Kohli, Gil Neiger, Mustaque Ahamad
The traditional consistency requirements of shared memory are expensive to provide both in large scale multiprocessor systems and also in distributed systems that implement a shared memory...
A Characterization of Scalable Shared Memories (1993)
Prince Kohli, Gil Neiger, Mustaque Ahamad
The traditional consistency requirements of shared memory are expensive to provide both in large scale multiprocessor systems and also in distributed systems that implement a shared memory...
A Characterization of Scalable Shared Memories (1993)
Prince Kohli, Gil Neiger, Mustaque Ahamad
The traditional consistency requirements of shared memory are expensive to provide both in large scale multiprocessor systems and also in distributed systems that implement a shared memory...
A Characterization of Scalable Shared Memories (1993)
Kohli, Prince, Neiger, Gil, Ahamad, Mustaque
The traditional consistency requirements of shared memory are expensive to provide both in large scale multiprocessor systems and also in distributed systems that implement a shared memory...
Simplifying Fault-Tolerance: Providing the Abstraction of Crash Failures (1993)
Bazzi, Rida Adnan, Neiger, Gil
The difficulty of designing fault-tolerant distributed algorithms increases with the severity of failures that an algorithm must tolerate. This paper considers methods that automatically translate...
Using Knowledge to Optimally Achieve Coordination in Distributed Systems (1993)
Neiger, Gil, Bazzi, Rida Adnan
The problem of coordinating the actions of individual processors is fundamental in distributed computing. Researchers have long endeavored to find efficient solutions to a variety of problems...
Distributed Consensus Revisited (1993)
Distributed Consensus is a classical problem in distributed computing. It requires the correct processors in a distributed system to agree on a common value despite the failure of other processors....
Space-Efficient Atomic Snapshots in Synchronous Systems (1993)
We consider the problem of implementing an atomic snapshot memory in synchronous distributed systems. An atomic snapshot memory is an array of memory locations, one per processor. Each processor may...
Causal Memory: Definitions, Implementation, and Programming (1993)
Ahamad, Mustaque, Neiger, Gil, Kohli, Prince, Burns, James Edward, Hutto, Phillip W.
The abstraction of a shared memory is of growing importance in distributed computing systems. Traditional memory consistency ensures that all processes agree on a common order of all operations on...
The Complexity of Almost-Optimal Coordination (1993)
Bazzi, Rida Adnan, Neiger, Gil
The problem of fault-tolerant coordination is fundamental in distributed computing. In the past, researchers have considered the complexity of achieving optimal simultaneous coordination under...
Structured Derivations of Consensus Algorithms for Failure Detectors (1970)
Jiong Yang, Gil Neiger, Eli Gafni
In a seminal paper, Chandra and Toueg showed how unreliable failure detectors could allows processors to achieve consensus in asynchronous message passing systems. Since then, other researchers have...