Ad hoc wireless networks are constructed by several mobile hosts and have a property that its topology is changed as mobile hosts moved. There is no stationary infrastructure or based station to coordinate packets transmissions and advertise the information of network topology or something important. The special networks are used in temporal wireless networks, such as battlefield, disease rescue place, and so on. So without any stationary infrastructure supported, mobile hosts can communicate with others immediately or indirectly. Because topology is often changed while mobile hosts moving, mobile hosts must exchange information to deal with the changed conditions. Mobile hosts often utilize broadcasting to exchange information with their neighbor hosts, but there is high bit error ratio in wireless networks, packet corruption occurs frequently, so that mobile host might lost some important information sent from its neighboring host. In 802.11 standard, lack of acknowledgement, broadcasting is an unreliable transmission, because sender host do not know whether all of it neighboring hosts received broadcasting packets correctly or no. Many proposed papers of reliable broadcast assumed that links between mobile hosts are bidirectional links, but bidirectional link is an ideal assumption. In real environment, links are unidirectional, so host A could send packets to host B immediately, but host B could not because of their transmission range are different. In this paper, we propose a new reliable broadcast scheme, Highly Reliable Broadcast Scheme with Directional Antennas (HRBSDA). HRBSDA can reduce the influence of unidirectional links and reach for highly reliable broadcasting. HRBSDA uses directional antennas and concept of Time Division Multiple Access (TDMA)-like. HRBSDA divide DCF Inter-Frame Space (DIFS) into several minislots, and mobile hosts use these minislots to ask sender for retransmission of lost packets. By the way, HRBSDA can not only reach for highly reliable broadcasting, but also reduce Packet Loss Recovery Time, and avoid causing extra overhead. Using directional antennas HRBSDA can reduce collision, so that improving throughput and channel utilization.

How much damage can a malicious tiny device cause in a single-hopwireless network? Imagine two players, Alice and Bob, who want toexchange information. Collin, a malicious adversary, wants to preventthem from communicating. By broadcasting at the same time as Alice orBob, Collin can destroy their messages or overwhelm them with his ownmalicious data. Being a tiny device, however, Collin can onlybroadcast up to B times. Given that Alice and Bob do not knowB, and cannot distinguish honest from malicious messages, howlong can Collin prevent them from communicating? We show the answerto be 2B + Theta(lg|V|) communication rounds, where V is theset of values that Alice and Bob may transmit. We prove this resultto be optimal by deriving an algorithm that matches our lowerbound---even in the stronger case where Alice and Bob do not start thegame at the same time.We then argue that this specific 3-player game captures the generalextent to which a malicious adversary can disrupt coordination in asingle-hop wireless network. We support this claim by deriving---via reduction from the 3-player game---round complexity lower boundsfor several classical n-player problems: 2B + Theta(lg|V|) for reliable broadcast,2B + Omega(lg(n/k)) for leader election among k contenders,and 2B + Omega(k*lg(|V|/k)) for static k-selection. We then consider an extension of our adversary model that also includes up to t crash failures. We study binary consensus as the archetypal problem for this environment and show a bound of 2B + Theta(t) rounds. We conclude by providing tight, or nearly tight, upper bounds for all four problems. The new upper and lower bounds in this paper represent the first such results for a wireless network in which the adversary has the ability to disrupt communication.

Uma tendência recente em sistemas de computação é distribuir a computação entre diversos processadores físicos. Isto conduz a dois tipos de sistemas: sistemas fortemente acoplados e sistemas fracamente acoplados. Este trabalho enfoca os sistemas de computação classificados como fracamente acoplados, ou sistemas distribuídos, como são popularmente conhecidos. Um sistema distribuído, segundo [BAB 86], pode ser definido como um conjunto de processadores autônomos que não compartilham memória, não tem acesso a clocks' globais e cuja comunicação é realizada somente por troca de mensagens. As exigências intrínsecas de sistemas distribuídos compreendem a confiabilidade e a disponibilidade. Estas exigências tem levado a um crescente interesse em técnicas de tolerância a falhas, cujo objetivo é manter a consistência do sistema distribuído, mesmo na ocorrência de falhas. Uma técnica de tolerância a falhas amplamente utilizada em sistemas distribuídos é a técnica de difusão confiável. A difusão confiável é uma técnica de redundância de software, onde um processador dissemina um valor para os demais processadores em um sistema distribuído, o qual esta sujeito a falhas [BAB 85]. Por ser uma técnica básica de comunicação, diversos procedimentos de tolerância a falhas baseiam-se em difusão confiável. Este trabalho descreve a implementação de um ambiente de apoio a sistemas distribuídos intitulado Ambiente para Experimentação e Avaliação de Protocolos de Difusão Confiável (ADC). Neste ambiente são utilizados os recursos da difusão confiável para a obtenção de uma concordância entre todos os membros do sistema livres de falha. Esta concordância, conhecida como consenso, é obtida através de algoritmos de consenso, os quais visam introduzir o grau de confiabilidade exigido pelos sistemas distribuídos. O ADC (Ambiente para Experimentação e Avaliação de Protocolos de Difusão Confiável) foi desenvolvido em estações de trabalho SUN (SunOS) utilizando o sistema operacional de rede heterogêneo HetNOS [BAA 93] desenvolvido na UFRGS. O ambiente foi implementado com base em um estudo realizado sobre protocolos de difusão confiável [BAR 94]. Através da implementação do ADC e possível simular a execução de protocolos de difusão confiável aplicando modelos propostos para os mesmos. Desta execução são extraídos resultados, sobre os quais pode-se realizar uma analise. Esta análise tem sua fundamentação principalmente nos parâmetros de desempenho, confiabilidade e complexidade. Tanto a implementação do ADC como a realização da analise do modelo proposto foram realizados tendo como suporte alguns dos protocolos de difusão confiável disponíveis na literatura. O principal objetivo deste ambiente consiste na experimentação, ou seja, na verificação da relação teórico-prática dos sistemas distribuídos perante a utilização de uma técnica de redundância de software, a difusão confiável. Através deste ambiente torna-se possível a determinação de parâmetros tais como o número de mensagens de difusão trocadas entre os processos, o número de mensagens de retransmissão enviadas, o número de mensagens emitidas durante todo o processamento do modelo, etc. Estes parâmetros resultam numa analise consistente de protocolos de difusão confiável. / A recent trend in computing systems is to distribute the computation between several physical processors. This leads to two different systems: closely coupled systems and loosely coupled systems. This work focuses on computing systems classified as loosely coupled or distributed systems, as they are commonly known. According to [BAB 86], a distributed system can be defined as a set of autonomous processors with no shared memory, no global clocks and whose comunication is performed only by message exchange. The inherent requirements of distributed systems include reliability and availability. These have caused an increasing interest in fault tolerance techniques, whose goal is to keep the distributed system consistent despite failures. A fault tolerance technique largely used in distributed systems is reliable broadcast. Reliable broadcast is a software redundancy technique, where a processor disseminates a value to other processors in a distributed system, in which failures can occur [BAB85]. Because it is a basic communication technique, several fault tolerance procedures are based on reliable broadcast. This work describes the implementation of a support environment for distributed systems called Reliable Broadcast Protocols Experimentation and Evaluation Environment (ADC). Reliable broadcast resources are used in this environment to obtain an agreement among all off-failure system components. This agreement, called consensus, has been obtained through consensus algorithms, which aim to introduce the reliability degree required in distributed systems. The ADC has been developed in Sun workstation (SunOS) using the heterogeneous operating system HetNOS [BAA 93] which was developed at UFRGS. The environment has been implemented based on a research about reliable broadcast protocols [BAR 94]. Through the ADC it is possible to simulate the execution of reliable broadcast protocols applying proposed models to them. From this execution results are extracted, and over them analysis can be done. This analysis has been based essentialy in parameters such as performance, reliability and complexity. Some classical reliable broadcast protocols were used as a support to ADC implementation and model analysis. The main goal of this environment consists in validating diffusion protocols in a practical distributed systems environment, facing reliable broadcast. Through this environment it can be possible the analysis of important parameters resolution such as the number of messages exchanged between process, the number of retransmission of messages sent, the number of messages sent during the whole model processing, others. These parameters result in a consistent analysis of reliable broadcast protocols.

Uma tendência recente em sistemas de computação é distribuir a computação entre diversos processadores físicos. Isto conduz a dois tipos de sistemas: sistemas fortemente acoplados e sistemas fracamente acoplados. Este trabalho enfoca os sistemas de computação classificados como fracamente acoplados, ou sistemas distribuídos, como são popularmente conhecidos. Um sistema distribuído, segundo [BAB 86], pode ser definido como um conjunto de processadores autônomos que não compartilham memória, não tem acesso a clocks' globais e cuja comunicação é realizada somente por troca de mensagens. As exigências intrínsecas de sistemas distribuídos compreendem a confiabilidade e a disponibilidade. Estas exigências tem levado a um crescente interesse em técnicas de tolerância a falhas, cujo objetivo é manter a consistência do sistema distribuído, mesmo na ocorrência de falhas. Uma técnica de tolerância a falhas amplamente utilizada em sistemas distribuídos é a técnica de difusão confiável. A difusão confiável é uma técnica de redundância de software, onde um processador dissemina um valor para os demais processadores em um sistema distribuído, o qual esta sujeito a falhas [BAB 85]. Por ser uma técnica básica de comunicação, diversos procedimentos de tolerância a falhas baseiam-se em difusão confiável. Este trabalho descreve a implementação de um ambiente de apoio a sistemas distribuídos intitulado Ambiente para Experimentação e Avaliação de Protocolos de Difusão Confiável (ADC). Neste ambiente são utilizados os recursos da difusão confiável para a obtenção de uma concordância entre todos os membros do sistema livres de falha. Esta concordância, conhecida como consenso, é obtida através de algoritmos de consenso, os quais visam introduzir o grau de confiabilidade exigido pelos sistemas distribuídos. O ADC (Ambiente para Experimentação e Avaliação de Protocolos de Difusão Confiável) foi desenvolvido em estações de trabalho SUN (SunOS) utilizando o sistema operacional de rede heterogêneo HetNOS [BAA 93] desenvolvido na UFRGS. O ambiente foi implementado com base em um estudo realizado sobre protocolos de difusão confiável [BAR 94]. Através da implementação do ADC e possível simular a execução de protocolos de difusão confiável aplicando modelos propostos para os mesmos. Desta execução são extraídos resultados, sobre os quais pode-se realizar uma analise. Esta análise tem sua fundamentação principalmente nos parâmetros de desempenho, confiabilidade e complexidade. Tanto a implementação do ADC como a realização da analise do modelo proposto foram realizados tendo como suporte alguns dos protocolos de difusão confiável disponíveis na literatura. O principal objetivo deste ambiente consiste na experimentação, ou seja, na verificação da relação teórico-prática dos sistemas distribuídos perante a utilização de uma técnica de redundância de software, a difusão confiável. Através deste ambiente torna-se possível a determinação de parâmetros tais como o número de mensagens de difusão trocadas entre os processos, o número de mensagens de retransmissão enviadas, o número de mensagens emitidas durante todo o processamento do modelo, etc. Estes parâmetros resultam numa analise consistente de protocolos de difusão confiável. / A recent trend in computing systems is to distribute the computation between several physical processors. This leads to two different systems: closely coupled systems and loosely coupled systems. This work focuses on computing systems classified as loosely coupled or distributed systems, as they are commonly known. According to [BAB 86], a distributed system can be defined as a set of autonomous processors with no shared memory, no global clocks and whose comunication is performed only by message exchange. The inherent requirements of distributed systems include reliability and availability. These have caused an increasing interest in fault tolerance techniques, whose goal is to keep the distributed system consistent despite failures. A fault tolerance technique largely used in distributed systems is reliable broadcast. Reliable broadcast is a software redundancy technique, where a processor disseminates a value to other processors in a distributed system, in which failures can occur [BAB85]. Because it is a basic communication technique, several fault tolerance procedures are based on reliable broadcast. This work describes the implementation of a support environment for distributed systems called Reliable Broadcast Protocols Experimentation and Evaluation Environment (ADC). Reliable broadcast resources are used in this environment to obtain an agreement among all off-failure system components. This agreement, called consensus, has been obtained through consensus algorithms, which aim to introduce the reliability degree required in distributed systems. The ADC has been developed in Sun workstation (SunOS) using the heterogeneous operating system HetNOS [BAA 93] which was developed at UFRGS. The environment has been implemented based on a research about reliable broadcast protocols [BAR 94]. Through the ADC it is possible to simulate the execution of reliable broadcast protocols applying proposed models to them. From this execution results are extracted, and over them analysis can be done. This analysis has been based essentialy in parameters such as performance, reliability and complexity. Some classical reliable broadcast protocols were used as a support to ADC implementation and model analysis. The main goal of this environment consists in validating diffusion protocols in a practical distributed systems environment, facing reliable broadcast. Through this environment it can be possible the analysis of important parameters resolution such as the number of messages exchanged between process, the number of retransmission of messages sent, the number of messages sent during the whole model processing, others. These parameters result in a consistent analysis of reliable broadcast protocols.

Uma tendência recente em sistemas de computação é distribuir a computação entre diversos processadores físicos. Isto conduz a dois tipos de sistemas: sistemas fortemente acoplados e sistemas fracamente acoplados. Este trabalho enfoca os sistemas de computação classificados como fracamente acoplados, ou sistemas distribuídos, como são popularmente conhecidos. Um sistema distribuído, segundo [BAB 86], pode ser definido como um conjunto de processadores autônomos que não compartilham memória, não tem acesso a clocks' globais e cuja comunicação é realizada somente por troca de mensagens. As exigências intrínsecas de sistemas distribuídos compreendem a confiabilidade e a disponibilidade. Estas exigências tem levado a um crescente interesse em técnicas de tolerância a falhas, cujo objetivo é manter a consistência do sistema distribuído, mesmo na ocorrência de falhas. Uma técnica de tolerância a falhas amplamente utilizada em sistemas distribuídos é a técnica de difusão confiável. A difusão confiável é uma técnica de redundância de software, onde um processador dissemina um valor para os demais processadores em um sistema distribuído, o qual esta sujeito a falhas [BAB 85]. Por ser uma técnica básica de comunicação, diversos procedimentos de tolerância a falhas baseiam-se em difusão confiável. Este trabalho descreve a implementação de um ambiente de apoio a sistemas distribuídos intitulado Ambiente para Experimentação e Avaliação de Protocolos de Difusão Confiável (ADC). Neste ambiente são utilizados os recursos da difusão confiável para a obtenção de uma concordância entre todos os membros do sistema livres de falha. Esta concordância, conhecida como consenso, é obtida através de algoritmos de consenso, os quais visam introduzir o grau de confiabilidade exigido pelos sistemas distribuídos. O ADC (Ambiente para Experimentação e Avaliação de Protocolos de Difusão Confiável) foi desenvolvido em estações de trabalho SUN (SunOS) utilizando o sistema operacional de rede heterogêneo HetNOS [BAA 93] desenvolvido na UFRGS. O ambiente foi implementado com base em um estudo realizado sobre protocolos de difusão confiável [BAR 94]. Através da implementação do ADC e possível simular a execução de protocolos de difusão confiável aplicando modelos propostos para os mesmos. Desta execução são extraídos resultados, sobre os quais pode-se realizar uma analise. Esta análise tem sua fundamentação principalmente nos parâmetros de desempenho, confiabilidade e complexidade. Tanto a implementação do ADC como a realização da analise do modelo proposto foram realizados tendo como suporte alguns dos protocolos de difusão confiável disponíveis na literatura. O principal objetivo deste ambiente consiste na experimentação, ou seja, na verificação da relação teórico-prática dos sistemas distribuídos perante a utilização de uma técnica de redundância de software, a difusão confiável. Através deste ambiente torna-se possível a determinação de parâmetros tais como o número de mensagens de difusão trocadas entre os processos, o número de mensagens de retransmissão enviadas, o número de mensagens emitidas durante todo o processamento do modelo, etc. Estes parâmetros resultam numa analise consistente de protocolos de difusão confiável. / A recent trend in computing systems is to distribute the computation between several physical processors. This leads to two different systems: closely coupled systems and loosely coupled systems. This work focuses on computing systems classified as loosely coupled or distributed systems, as they are commonly known. According to [BAB 86], a distributed system can be defined as a set of autonomous processors with no shared memory, no global clocks and whose comunication is performed only by message exchange. The inherent requirements of distributed systems include reliability and availability. These have caused an increasing interest in fault tolerance techniques, whose goal is to keep the distributed system consistent despite failures. A fault tolerance technique largely used in distributed systems is reliable broadcast. Reliable broadcast is a software redundancy technique, where a processor disseminates a value to other processors in a distributed system, in which failures can occur [BAB85]. Because it is a basic communication technique, several fault tolerance procedures are based on reliable broadcast. This work describes the implementation of a support environment for distributed systems called Reliable Broadcast Protocols Experimentation and Evaluation Environment (ADC). Reliable broadcast resources are used in this environment to obtain an agreement among all off-failure system components. This agreement, called consensus, has been obtained through consensus algorithms, which aim to introduce the reliability degree required in distributed systems. The ADC has been developed in Sun workstation (SunOS) using the heterogeneous operating system HetNOS [BAA 93] which was developed at UFRGS. The environment has been implemented based on a research about reliable broadcast protocols [BAR 94]. Through the ADC it is possible to simulate the execution of reliable broadcast protocols applying proposed models to them. From this execution results are extracted, and over them analysis can be done. This analysis has been based essentialy in parameters such as performance, reliability and complexity. Some classical reliable broadcast protocols were used as a support to ADC implementation and model analysis. The main goal of this environment consists in validating diffusion protocols in a practical distributed systems environment, facing reliable broadcast. Through this environment it can be possible the analysis of important parameters resolution such as the number of messages exchanged between process, the number of retransmission of messages sent, the number of messages sent during the whole model processing, others. These parameters result in a consistent analysis of reliable broadcast protocols.

Road accidents represent a serious social problem and are one of the leading causes of human death and disability on a global scale. To reduce the risk and severity of a road accident, a variety of new safety applications can be realized through wireless communications among vehicles driving nearby each other, or among vehicles and especially deployed road side units (RSUs), a technology known as a vehicular ad hoc network (VANET). Most of the VANET-enabled safety applications are based on broadcasting of safety messages by vehicles or RSUs, either periodically or in case of an unexpected event, such as a hard brake or dangerous road condition detection. Each broadcast safety message should be successfully delivered to the surrounding vehicles and RSUs without any excess delay, which is one of the main functions of a medium access control (MAC) protocol proposed for VANETs. This thesis presents VeMAC, a new multichannel time division multiple access (TDMA) protocol specifically designed to support the high priority safety applications in a VANET scenario. The ability of the VeMAC protocol to deliver periodic and event-driven safety messages in VANETs is demonstrated by a detailed delivery delay analysis, including queueing and service delays, for both types of safety messages. As well, computer simulations are conducted by using MATLAB, the network simulator ns-2, and the microscopic vehicle traffic simulator VISSIM, in order to evaluate the performance of the VeMAC protocol, in comparison with the IEEE 802.11p standard and the ADHOC MAC protocol (another TDMA protocol proposed for ad hoc networks). A real city scenario is simulated and different performance metrics are evaluated, including the network goodput, protocol overhead, channel utilization, protocol fairness, probability of a transmission collision, and safety message delivery delay. It is shown that the VeMAC protocol considerably outperforms the existing MAC schemes, which have significant limitations in supporting VANET safety applications. In addition to enhancing road safety, in-vehicle Internet access is one of the main applications of VANETs, which aims at providing the vehicle passengers with a low-cost access to the Internet via on-road gateways. This thesis presents a new strategy for deploying Internet gateways on the roads, in order to minimize the total cost of gateway deployment, while ensuring that a vehicle can connect to an Internet gateway (using multihop communications) with a probability greater than a specified threshold. This cost minimization problem is formulated by using binary integer programming, and applied for optimal gateway placement in a real city scenario. To the best of our knowledge, no previous strategy for gateway deployment has considered the probability of multihop connectivity among the vehicles and the deployed gateways. In order to allow a vehicle to discover the existence of an Internet gateway and to communicate with the gateway via multihops, a novel data packet routing scheme is proposed based on the VeMAC protocol. The performance of this cross-layer design is evaluated for a multichannel VANET in a highway scenario, mainly in terms of the end-to-end packet delivery delay. The packet queueing at each relay vehicle is considered in the end-to-end delay analysis, and numerical results are presented to study the effect of various parameters, such as the vehicle density and the packet arrival rate, on the performance metrics. The proposed VeMAC protocol is a promising candidate for MAC in VANETs, which can realize many advanced safety applications to enhance the public safety standards and improve the safety level of drivers/passengers and pedestrians on roads. On the other hand, the proposed gateway placement strategy and packet routing scheme represent a strong step toward providing reliable and ubiquitous in-vehicle Internet connectivity.

We present a partial implementation of King and Saia 2016’s expected polyno- mial time byzantine agreement algorithm, which which greatly speeds up Bracha’s Byzantine agreement algorithm by introducing a shared coin flip subroutine and a method for detecting adversarially controlled nodes. In addition to implementing the King-Saia algorithm, we detail a new version of the “blackboard” abstraction used to implement the shared coin flip, which improves the subroutine’s resilience from t < n/4 to t < n/3 and leads to an improvement of the resilience of the King-Saia Byzantine agreement algorithm overall. We test the King-Saia algorithm, and detail a series of adversarial attacks against it; we also create a Monte Carlo simulation to further test one particular attack’s level of success at biasing the shared coin flip / Graduate