Bluetooth utilizes fast frequency hopping to mitigate interference from other wireless devices and other Bluetooth piconets that share the same frequency range. However, it still can not avoid the interference between piconets entirely. In our simulation, we observed that the inter-piconet interference can significantly degrade the system throughput by more than 30%. The system throughput within a piconet can be improved by a proper arrangement of the segmentation/reassembling (SAR) policy and a good selection of MAC scheduling protocols. Many SAR policies and MAC scheduling protocols were proposed, but none of them takes the inter-piconet interference into consideration. In this paper, we study the impact of the interference on the performance of TCP traffic over a Bluetooth scatternet with multiple overlapping piconets. To alleviate the impact, we propose interference-aware SAR policies as well as the interference-aware MAC scheduling protocols. The simulation results show that our schemes help reduce the impact of the inter-piconet interference by more than 50%.

Consideration is given to a system of n competitors, where if a competitor selects its bids equally likely from a given set of bid values, its probability of winning is guaranteed to be 1/n, regardless of the bid values selected by other competitors in the system. A discussion is presented of several variations of this basic scheme, namely, bidding with unequal weights, bidding with more than one winner, and bidding with an unknown number of competitors. Two economical, but approximate, bidding schemes are discussed. In the first scheme, the competitors select their bids from a set with a constant size, and in the second, each competitor selects only one bid even though the total number of competitors is not known a priori. It is shown how to use these bidding schemes to construct solutions to several problems in distributed systems, including the mutual exclusion problem and the dining philosophers problem.>

Consider a network of communicating finite state machines that exchange messages over unbounded FIFO channels. Each machine in the network can be defined by a directed graph whose nodes represent the machine states and whose edges represent its transitions. In general, for a node in one of the machines to be live (i.e., encountered infinitely often during the course of communication), each machine in the network should progress in some fair fashion. We define three graduated notions of fair progress (namely, node fairness, edge fairness, and network fairness), and on this basis we define three corresponding degrees of node liveness. We discuss techniques to verify that a given node is live under each of these fairness assumptions. These techniques can be automated; and they are effective even if the network under consideration has an infinite number of reachable states. We use our techniques to establish the liveness of some practical communication protocols; these include an unbounded start-stop protocol, an unbounded alternating bit protocol, and a simplified version of the CSMA/CD protocol for local area networks.

Consider a network of communicating finite state machines that exchange messages over unbounded, FIFO channels. Each machine in this network has a finite number of states (called nodes), and state transitions (called edges), and can be defined by a labelled directed graph. A node in one of the machines is said to be “live” iff it is reached by its machine infinitely often during the course of communication, provided that the machines behave in some “fair” fashion. We discuss a technique to verify that a given node is live in such a network. This technique can be automated, and is effective even if the network under consideration is unbounded (i.e. has an infinite number of reachable states). We use our technique to establish the liveness of three distributed solutions to the mutual exclusion problem.