The Experts below are selected from a list of 6288 Experts worldwide ranked by ideXlab platform
W. Zhao - One of the best experts on this subject based on the ideXlab platform.
-
guaranteeing Synchronous Message deadlines with the timed token medium access control protocol
IEEE Transactions on Computers, 1994Co-Authors: G. Agrawal, B. Chen, W. Zhao, S. DavariAbstract:We study the problem of guaranteeing Synchronous Message deadlines in token ring networks where the timed token medium access control protocol is employed. Synchronous bandwidth, defined as the maximum time for which a node can transmit its Synchronous Messages every time it receives the token, is a key parameter in the control of Synchronous Message transmission. To ensure the transmission of Synchronous Messages before their deadlines, Synchronous capacities must be properly allocated to individual nodes. We address the issue of appropriate allocation of the Synchronous capacities. Several Synchronous bandwidth allocation schemes are analyzed in terms of their ability to satisfy deadline constraints of Synchronous Messages. We show that an inappropriate allocation of the Synchronous capacities could cause Message deadlines to be missed, even if the Synchronous traffic is extremely low. We propose a scheme, called the normalized proportional allocation scheme, which can guarantee the Synchronous Message deadlines for Synchronous traffic of up to 33% of available utilization. >
-
local Synchronous capacity allocation schemes for guaranteeing Message deadlines with the timed token protocol
International Conference on Computer Communications, 1993Co-Authors: G. Agrawal, B. Chen, W. ZhaoAbstract:The problem of guaranteeing Synchronous Message deadlines in communication networks using the timed token medium access control protocol is studied. To ensure the transmission of Synchronous Messages before their deadlines, Synchronous capacities must be properly allocated to individual nodes. A class of local Synchronous capacity allocation schemes, which allocate the Synchronous capacity to a node without using information about Messages on the other nodes, is developed, analyzed, and evaluated in terms of the ability of the schemes to guarantee Message deadlines. It is shown that one of the local allocation schemes proposed can achieve the same performance as that of the best global allocation scheme known to date. >
-
optimal Synchronous capacity allocation for hard real time communications with the timed token protocol
Real-Time Systems Symposium, 1992Co-Authors: B. Chen, G. Agrawal, W. ZhaoAbstract:The authors study the problem of transmitting Synchronous Messages before their deadlines in communication networks where the timed token medium access control protocol is employed. Synchronous capacity, defined as the maximum time for which a node can transmit its Synchronous Message every time it receives the token, is a key parameter in the control of Synchronous Message transmission. To ensure the transmission of Synchronous Messages before their deadlines, Synchronous capacities must be property allocated to individual nodes. The authors develop and analyze an optimal Synchronous capacity allocation scheme. An optimal scheme can allocate the Synchronous capacities in such a way that the Synchronous Message deadlines are guaranteed if there exists any allocation scheme that can do so. The optimality of the allocation scheme proposed here is formally proved, and the bounds for its worst case achievable utilization are derived. >
-
Guaranteeing Synchronous Message deadlines with the timed token protocol
[1992] Proceedings of the 12th International Conference on Distributed Computing Systems, 1992Co-Authors: G. Agrawal, B. Chen, W. Zhao, S. DavariAbstract:The problem of guaranteeing Synchronous Message deadlines in token ring networks in which the timed token medium access control protocol is used is discussed. Synchronous capacity, defined as the maximum time for which a node can transmit its Synchronous Messages every time it receives the token, is a key parameter in the control of Synchronous Message transmission. To ensure the transmission of Synchronous Messages before their deadlines, Synchronous capacities must be properly allocated to individual nodes. Several Synchronous capacity allocation schemes are analyzed in terms of their ability to satisfy deadline constraints of Synchronous Messages. It is shown that an inappropriate allocation of the Synchronous capacities could cause Message deadlines to be missed, even if the Synchronous traffic is extremely low. The normalized proportional allocation scheme, which can guarantee the Synchronous Message deadlines for Synchronous traffic of up to 33% of available utilization is proposed.
Sijing Zhang - One of the best experts on this subject based on the ideXlab platform.
-
Testing the Schedulability of Synchronous Traffic for the Timed Token Medium Access Control Protocol
Real-Time Systems, 2002Co-Authors: Sijing Zhang, Alan Burns, Ahmed Mehaoua, E. Stewart Lee, Hongji YangAbstract:One of the key issues related to guaranteeing Synchronous Message deadlines in a timed token network (such as fiber distributed data interface) where the timed token medium access control protocol is used is the schedulability test of Synchronous traffic (i.e., testing whether or not all Synchronous Messages can be transmitted before their deadlines, under a given setting of network parameters). Much work has been done on how to assign network parameters appropriately in order to guarantee timely transmission of Synchronous traffic. As a result quite a few Synchronous bandwidth allocation schemes and some good guidelines on selection of the target token rotation time have been proposed. In contrast, limited research has been conducted on how to effectively test whether or not given network parameters can guarantee timely transmission of all Synchronous Messages (of a considered Synchronous Message set) before their deadlines. The previous testing methods for Synchronous Message schedulability only provide a sufficient (but not necessary) test and therefore fail to always keep effective for any Synchronous Message set considered. In this paper, we propose two testing methods for determining the schedulability of a Synchronous Message set with Message deadlines no longer than periods. The proposed tests perform better than any previous test in the sense that they are both sufficient and necessary. Some numerical examples are given to compare different testing methods, all of which have demonstrated the superiority of the proposed tests to other existing testing methods.
-
efficient global allocation of Synchronous bandwidths for hard real time communication with the timed token mac protocol
Embedded and Real-Time Computing Systems and Applications, 1999Co-Authors: Sijing Zhang, E S LeeAbstract:This paper presents an efficient global Synchronous bandwidth allocation (SBA) scheme for guaranteeing Synchronous Message deadlines in a timed token network (such as FDDI) where the timed token medium access control (MAC) protocol is used. A local SBA scheme allocates Synchronous bandwidth to a node using only information available locally to that node while a global scheme uses network wide information from all nodes. A local SBA scheme may be preferred for practical use to a global one due to its lower network management overhead. However, a global SBA scheme can greatly outperform a local scheme due to a more appropriate allocation resulted from the more complete global information. That is, use of a global SBA scheme may largely enhance the network ability of guaranteeing Synchronous traffic. The global scheme proposed in this paper outperforms all existing SBA schemes for guaranteeing Synchronous Messages with deadlines equal to periods. Numerical examples are given to demonstrate the superiority of the proposed scheme to previously-proposed SBA schemes.
-
Testing the feasibility of Synchronous bandwidth allocation for time-critical communication in FDDI networks
Proceedings of Sixth International Conference on Computer Communications and Networks, 1997Co-Authors: Sijing Zhang, Tee-hiang Cheng, K.r. Subramanian, Liren ZhangAbstract:One of the key issues related to deadline guarantees of Synchronous Messages in FDDI networks is the feasibility test of Synchronous bandwidth allocation (SBA). Much work has been done on how to allocate Synchronous bandwidth properly in order to guarantee Synchronous Messages transmission before their deadlines, and as a result quite a few SBA schemes have been proposed. In contrast, limited research has been done on how to effectively test the feasibility of a given allocation of Synchronous bandwidths (i.e., whether or not a given allocation can guarantee the Synchronous Message set considered), and the existing approach cannot always give an effective test and may even produce wrong testing results. This paper presents an algorithm of polynomial time worst-case complexity which ensures the correctness and effectiveness of the testing for any given Synchronous Message set with Message deadlines equal to periods.
-
An efficient and practical local Synchronous bandwidth allocation scheme for the timed-token MAC protocol
Proceedings of IEEE INFOCOM '96. Conference on Computer Communications, 1996Co-Authors: Sijing Zhang, Alan Burns, A. WellingsAbstract:This paper is concerned with deadline guarantees of Synchronous Messages with deadlines equal to periods, in a timed token ring network such as FDDI where the timed token medium access control (MAC) protocol is used. The timed token protocol guarantees a bounded access time and an average bandwidth for Synchronous traffic. However, this guarantee alone, though necessary, is insufficient for guaranteeing the transmission of Synchronous Messages before their deadlines. To ensure timely delivery, the Synchronous bandwidth must be carefully allocated to individual nodes. We propose and analyse an efficient and practical local Synchronous bandwidth allocation (SBA) scheme. The new scheme performs better than any previously published as it calculates the Synchronous bandwidth such that during the Message period, the total Synchronous transmission time definitely available (when judged only by local information) is exactly equal to the transmission time required. Our scheme also differs significantly from previously reported ones by explicitly taking into account the Synchronous bandwidth allocation for Message sets whose minimum Message deadlines (D/sub min/) are less than twice the target token rotation time (TTRT), and consequently can apply to any Synchronous Message set (with D/sub min/>TTRT). The feasibility of the allocations produced by the proposed scheme and the worst case achievable utilisation of the scheme are also discussed.
-
an optimal Synchronous bandwidth allocation scheme for guaranteeing Synchronous Message deadlines with the timed token mac protocol
IEEE ACM Transactions on Networking, 1995Co-Authors: Sijing Zhang, Alan BurnsAbstract:This paper investigates the inherent timing properties of the timed-token medium access control (MAC) protocol necessary to guarantee Synchronous Message deadlines in a timed token ring network such as, fiber distributed data interface (FDDI), where the timed-token MAC protocol is employed. As a result, an exact upper bound, tighter than previously published, on the elapse time between any number of successive token arrivals at a particular node has been derived. Based on the exact protocol timing property, an optimal Synchronous bandwidth allocation (SBA) scheme named enhanced MCA (EMCA) for guaranteeing Synchronous Messages with deadlines equal to periods in length is proposed. This scheme is an enhancement on the previously published MCA scheme.
Achour Mostefaoui - One of the best experts on this subject based on the ideXlab platform.
-
on composition and implementation of sequential consistency
International Symposium on Distributed Computing, 2016Co-Authors: Matthieu Perrin, Achour Mostefaoui, Matoula Petrolia, Claude JardAbstract:It has been proved that to implement a linearizable shared memory in Synchronous Message-passing systems it is necessary to wait for a time proportional to the uncertainty in the latency of the network for both read and write operations, while waiting during read or during write operations is sufficient for sequential consistency. This paper extends this result to crash-prone aSynchronous systems. We propose a distributed algorithm that builds a sequentially consistent shared memory abstraction with snapshot on top of an aSynchronous Message-passing system where less than half of the processes may crash. We prove that it is only necessary to wait when a read/snapshot is immediately preceded by a write on the same process. We also show that sequential consistency is composable in some cases commonly encountered: 1) objects that would be linearizable if they were implemented on top of a linearizable memory become sequentially consistent when implemented on top of a sequential memory while remaining composable and 2) in round-based algorithms, where each object is only accessed within one round.
-
on composition and implementation of sequential consistency
arXiv: Distributed Parallel and Cluster Computing, 2016Co-Authors: Matthieu Perrin, Achour Mostefaoui, Matoula Petrolia, Claude JardAbstract:To implement a linearizable shared memory in Synchronous Message-passing systems it is necessary to wait for a time linear to the uncertainty in the latency of the network for both read and write operations. Waiting only for one of them suffices for sequential consistency. This paper extends this result to crash-prone aSynchronous systems, proposing a distributed algorithm building a sequentially consistent shared snapshot memory on top of an aSynchronous Message-passing system where less than half of the processes may crash. We prove that waiting is needed only when a process invokes a read/snapshot right after a write. We also show that sequential consistency is composable in some cases commonly encountered: 1) objects that would be linearizable if they were implemented on top of a linearizable memory become sequentially consistent when implemented on top of a sequential memory while remaining composable and 2) in round-based algorithms, where each object is only accessed within one round.
-
On Composition and Implementation of Sequential Consistency (Extended Version)
2016Co-Authors: Matthieu Perrin, Achour Mostefaoui, Matoula Petrolia, Claude JardAbstract:It has been proved that to implement a linearizable shared memory in Synchronous Message-passing systems it is necessary to wait for a time proportional to the uncertainty in the latency of the network for both read and write operations, while waiting during read or during write operations is sufficient for sequential consistency. This paper extends this result to crash-prone aSynchronous systems. We propose a distributed algorithm that builds a sequentially consistent shared memory abstraction with snapshot on top of an aSynchronous Message-passing system where less than half of the processes may crash. We prove that it is only necessary to wait when a read/snapshot is immediately preceded by a write on the same process. We also show that sequential consistency is composable in some cases commonly encountered: 1) objects that would be linearizable if they were implemented on top of a linearizable memory become sequentially consistent when implemented on top of a sequential memory while remaining composable and 2) in round-based algorithms, where each object is only accessed within one round.
-
modular randomized byzantine k set agreement in aSynchronous Message passing systems
International Conference of Distributed Computing and Networking, 2016Co-Authors: Achour Mostefaoui, Hamouma Moumen, Michel RaynalAbstract:k-Set agreement is a central problem of fault-tolerant distributed computing. Considering a set of n processes, where up to t may commit failures, let us assume that each process proposes a value. The problem consists in defining an algorithm such that each non-faulty process decides a value, at most k different values are decided, and the decided values satisfy some context-depending validity condition. Synchronous Message-passing algorithms solving k-set agreement have been proposed for different failure models (mainly process crashes, and process Byzantine failures). Differently, k-set agreement cannot be solved in failure-prone aSynchronous Message-passing systems when t ≥ k. To circumvent this impossibility an aSynchronous system must be enriched with additional computational power.Assuming t ≥ k, this paper presents a distributed algorithm that solves k-set agreement in an aSynchronous Message-passing system where up to t processes may commit Byzantine failures. To that end, each process is enriched with randomization power. While randomized k-set agreement algorithms exist for the aSynchronous process crash failure model where t ≥ k, to our knowledge the proposed algorithm is the first that solves k-set agreement in the presence of up to t ≥ k Byzantine processes. Interestingly, this algorithm is signature-free, and ensures that no value proposed only by Byzantine processes can be decided by a non-faulty process. Its design is based on a modular construction which rests on a "no-duplicity" one-to-all broadcast abstraction, and two all-to-all communication abstractions.
G. Agrawal - One of the best experts on this subject based on the ideXlab platform.
-
guaranteeing Synchronous Message deadlines with the timed token medium access control protocol
IEEE Transactions on Computers, 1994Co-Authors: G. Agrawal, B. Chen, W. Zhao, S. DavariAbstract:We study the problem of guaranteeing Synchronous Message deadlines in token ring networks where the timed token medium access control protocol is employed. Synchronous bandwidth, defined as the maximum time for which a node can transmit its Synchronous Messages every time it receives the token, is a key parameter in the control of Synchronous Message transmission. To ensure the transmission of Synchronous Messages before their deadlines, Synchronous capacities must be properly allocated to individual nodes. We address the issue of appropriate allocation of the Synchronous capacities. Several Synchronous bandwidth allocation schemes are analyzed in terms of their ability to satisfy deadline constraints of Synchronous Messages. We show that an inappropriate allocation of the Synchronous capacities could cause Message deadlines to be missed, even if the Synchronous traffic is extremely low. We propose a scheme, called the normalized proportional allocation scheme, which can guarantee the Synchronous Message deadlines for Synchronous traffic of up to 33% of available utilization. >
-
local Synchronous capacity allocation schemes for guaranteeing Message deadlines with the timed token protocol
International Conference on Computer Communications, 1993Co-Authors: G. Agrawal, B. Chen, W. ZhaoAbstract:The problem of guaranteeing Synchronous Message deadlines in communication networks using the timed token medium access control protocol is studied. To ensure the transmission of Synchronous Messages before their deadlines, Synchronous capacities must be properly allocated to individual nodes. A class of local Synchronous capacity allocation schemes, which allocate the Synchronous capacity to a node without using information about Messages on the other nodes, is developed, analyzed, and evaluated in terms of the ability of the schemes to guarantee Message deadlines. It is shown that one of the local allocation schemes proposed can achieve the same performance as that of the best global allocation scheme known to date. >
-
optimal Synchronous capacity allocation for hard real time communications with the timed token protocol
Real-Time Systems Symposium, 1992Co-Authors: B. Chen, G. Agrawal, W. ZhaoAbstract:The authors study the problem of transmitting Synchronous Messages before their deadlines in communication networks where the timed token medium access control protocol is employed. Synchronous capacity, defined as the maximum time for which a node can transmit its Synchronous Message every time it receives the token, is a key parameter in the control of Synchronous Message transmission. To ensure the transmission of Synchronous Messages before their deadlines, Synchronous capacities must be property allocated to individual nodes. The authors develop and analyze an optimal Synchronous capacity allocation scheme. An optimal scheme can allocate the Synchronous capacities in such a way that the Synchronous Message deadlines are guaranteed if there exists any allocation scheme that can do so. The optimality of the allocation scheme proposed here is formally proved, and the bounds for its worst case achievable utilization are derived. >
-
Guaranteeing Synchronous Message deadlines with the timed token protocol
[1992] Proceedings of the 12th International Conference on Distributed Computing Systems, 1992Co-Authors: G. Agrawal, B. Chen, W. Zhao, S. DavariAbstract:The problem of guaranteeing Synchronous Message deadlines in token ring networks in which the timed token medium access control protocol is used is discussed. Synchronous capacity, defined as the maximum time for which a node can transmit its Synchronous Messages every time it receives the token, is a key parameter in the control of Synchronous Message transmission. To ensure the transmission of Synchronous Messages before their deadlines, Synchronous capacities must be properly allocated to individual nodes. Several Synchronous capacity allocation schemes are analyzed in terms of their ability to satisfy deadline constraints of Synchronous Messages. It is shown that an inappropriate allocation of the Synchronous capacities could cause Message deadlines to be missed, even if the Synchronous traffic is extremely low. The normalized proportional allocation scheme, which can guarantee the Synchronous Message deadlines for Synchronous traffic of up to 33% of available utilization is proposed.
Claude Jard - One of the best experts on this subject based on the ideXlab platform.
-
on composition and implementation of sequential consistency
International Symposium on Distributed Computing, 2016Co-Authors: Matthieu Perrin, Achour Mostefaoui, Matoula Petrolia, Claude JardAbstract:It has been proved that to implement a linearizable shared memory in Synchronous Message-passing systems it is necessary to wait for a time proportional to the uncertainty in the latency of the network for both read and write operations, while waiting during read or during write operations is sufficient for sequential consistency. This paper extends this result to crash-prone aSynchronous systems. We propose a distributed algorithm that builds a sequentially consistent shared memory abstraction with snapshot on top of an aSynchronous Message-passing system where less than half of the processes may crash. We prove that it is only necessary to wait when a read/snapshot is immediately preceded by a write on the same process. We also show that sequential consistency is composable in some cases commonly encountered: 1) objects that would be linearizable if they were implemented on top of a linearizable memory become sequentially consistent when implemented on top of a sequential memory while remaining composable and 2) in round-based algorithms, where each object is only accessed within one round.
-
on composition and implementation of sequential consistency
arXiv: Distributed Parallel and Cluster Computing, 2016Co-Authors: Matthieu Perrin, Achour Mostefaoui, Matoula Petrolia, Claude JardAbstract:To implement a linearizable shared memory in Synchronous Message-passing systems it is necessary to wait for a time linear to the uncertainty in the latency of the network for both read and write operations. Waiting only for one of them suffices for sequential consistency. This paper extends this result to crash-prone aSynchronous systems, proposing a distributed algorithm building a sequentially consistent shared snapshot memory on top of an aSynchronous Message-passing system where less than half of the processes may crash. We prove that waiting is needed only when a process invokes a read/snapshot right after a write. We also show that sequential consistency is composable in some cases commonly encountered: 1) objects that would be linearizable if they were implemented on top of a linearizable memory become sequentially consistent when implemented on top of a sequential memory while remaining composable and 2) in round-based algorithms, where each object is only accessed within one round.
-
On Composition and Implementation of Sequential Consistency (Extended Version)
2016Co-Authors: Matthieu Perrin, Achour Mostefaoui, Matoula Petrolia, Claude JardAbstract:It has been proved that to implement a linearizable shared memory in Synchronous Message-passing systems it is necessary to wait for a time proportional to the uncertainty in the latency of the network for both read and write operations, while waiting during read or during write operations is sufficient for sequential consistency. This paper extends this result to crash-prone aSynchronous systems. We propose a distributed algorithm that builds a sequentially consistent shared memory abstraction with snapshot on top of an aSynchronous Message-passing system where less than half of the processes may crash. We prove that it is only necessary to wait when a read/snapshot is immediately preceded by a write on the same process. We also show that sequential consistency is composable in some cases commonly encountered: 1) objects that would be linearizable if they were implemented on top of a linearizable memory become sequentially consistent when implemented on top of a sequential memory while remaining composable and 2) in round-based algorithms, where each object is only accessed within one round.
