The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
Recently, we challenged the belief that randomized Byzantine agreement protocols are inefficient, by designing, implementing and assessing the performance of a stack of protocols of that type [3]. That assessment lead us to a set of properties desirable for Byzantine asynchronous binary consensus protocols: (1) Strong validity . if all correct processes propose the same value v, the decision is v...
Distributed Greedy Coloring is an interesting and intuitive variation of the standard Coloring problem. It still consists in coloring in a distributed setting each node of a given graph in such a way that two adjacent nodes do not get the same color, but it adds a further constraint. Given an order among the colors, a coloring is said to be greedy if there does not exist a node for which its associated...
There is a proliferation of models for distributed computing, consisting of both shared memory and message passing paradigms. Different communities adopt different variants as the “standard” model for their research setting. Since subtle changes in the communication model can result in significant changes to the solvability/unsolvability or to the complexity of various problems, it becomes imperative...
This brief announcement focuses on interoperability of software transactions with ad hoc nonblocking algorithms. Specifically, we modify arbitrary nonblocking operations so that (1) they can be used both inside and outside transactions, (2) external uses serialize with transactions, and (3) internal uses succeed if and only if the surrounding transaction commits. Interoperability enables seemless...
Fault-tolerant systems often require a means by which independent processes or processors can arrive at an exact mutual agreement of some kind. The work announced in this note studies the continuous consensus problem, which is a general tool for enabling actions that are performed at the same time at different sites of the system to be consistent with one another (e.g., mutual exlusion, firing squad...
We describe a distributed algorithm for convex constrained optimization in networks without any consistent naming infrastructure. The algorithm produces an approximately feasible and near-optimal solution in time polynomial in the network size, the inverse of the permitted error, and a measure of curvature variation in the dual optimization problem. It blends, in a novel way, gossip-based information...
In the standard message passing models it is assumed that the identity of a sender is known to the receiver. In practice, this often is not the case, due to impersonation attacks by malicious adversaries. Various impersonation attack schemes have been extensively investigated in the context of network security or cryptography, in particular for peep-to-peer and sensor networks [4,5]. Here, we study...
We characterize Perfectly Secure Message Transmission (PSMT) between two nodes S and R in directed wire model, assuming that n wires are directed from S to R (also termed as top band) and u wires are directed from R to S (also termed as bottom band). A mixed adversary (tb, tf ) controls tb wires...
In the deferred update technique for database replication, a number of database replicas are used to implement a single serializable database interface. Its main idea consists in executing all operations of a transaction initially on a single database replica. Transactions that do not change the database state can commit locally to the replica they executed, but other transactions must be globally...
DISC 2006 marked the 20th anniversary of the DISC conferences. We list below the special events that took place during DISC 2006, together with some information and perspectives on the past and future of DISC.
A guided tour through the labyrinth of my thoughts, from the Bakery Algorithm to arbiter-free marked graphs. This exercise in egotism is by invitation of the DISC 20th Anniversary Committee. I take no responsibility for the choice of topic.
I first became involved in Distributed Computing Theory around 1978 or 1979, as a new professor at Georgia Tech. Looking back at my first few years in the field, approximately 1979-1982, I see that they were tremendously exciting, productive, and fun. I collaborated with, and learned from, many leaders of the field, including Mike Fischer, Jim Burns, Michael Merritt, Gary Peterson, Danny Dolev, and...
Encryption is a fundamental building block for computer and communications technologies. Existing encryption methods depend for their security on unproven assumptions. We propose a new model, the Limited Access model for enabling a simple and practical provably unbreakable encryption scheme. A voluntary distributed network of thousands of computers each maintain and update random pages, and act as...
In many large-scale distributed systems the users have only incomplete information about the system. We outline game theoretic approaches that are used to model such incomplete information settings.
As broadcasting is one of the primary functions in radio networks, fast algorithms for performing it are of considerable interest. A radio network consists of stations that can act at any a given time step either as transmitters or as receivers. Given a deployment of the stations, the reception conditions can be modeled by a graph, where the existence of an edge between two nodes indicates that transmissions...
After presenting a personal view of distributed computing (of course, being personal, this view is partial and questionable), this invited talk will address distributed computing problems that have recently received attention in the literature. For each of them, the talk presents the problem, results from the community, results from the author (and his co-authors), and questions that remain open....
We present the first optimally resilient, bounded, wait-free implementation of a distributed atomic register, tolerating Byzantine readers and (up to one-third of) Byzantine servers, without the use of unproven cryptographic primitives or requiring communication among servers. Unlike previous (non-optimal) solutions, the sizes of messages sent to writers depend only on the actual number of active...
We describe and analyze a 3-state one-way population protocol for approximate majority in the model in which pairs of agents are drawn uniformly at random to interact. Given an initial configuration of x’s, y’s and blanks that contains at least one non-blank, the goal is for the agents to reach consensus on one of the values x or y. Additionally, the value chosen should be the majority non-blank initial...
We consider the problem of designing scalable and robust information systems based on multiple servers that can survive even massive denial-of-service (DoS) attacks. More precisely, we are focusing on designing a scalable distributed hash table (DHT) that is robust against so-called past insider attacks. In a past insider attack, an adversary knows everything about the system up to some time point...
We present a model of a mobile ad-hoc network in which nodes can move arbitrarily on the plane with some bounded speed. We show that without any assumption on some topological stability, it is impossible to solve the geocast problem despite connectivity and no matter how slowly the nodes move. Even if each node maintains a stable connection with each of its neighbours for some period of time, it is...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.